目录

若a,m互质，则
\[
a^{\varphi\left ( m \right )}\equiv 1\left ( mod \ m \right )
\]

令a = 3，n = 5，这两个数是互素的。比5小的正整数中与5互素的数有1、2、3和4，所以\varphi(5)=4。计算：a^{\varphi(n)} = 3^4 = 81，而81 \equiv 80 + 1 \equiv 1 \pmod{5}。与定理结果相符。

计算7^{222}的个位数，实际是求7^{222}被10除的余数。7和10互素，且\varphi(10)=4。由欧拉定理知7^4\equiv 1\pmod {10}。所以7^{222}= 7^{4\cdot 55+2}= (7^4)^{55}\cdot 7^2\equiv 1^{55}\cdot 7^2\equiv 49\equiv 9\pmod{10}。

若p是质数，则对于任意整数a，都有
\[
a^{p}\equiv a\left ( mod \ p \right )
\]

\[
a^{b}\ mod \ m,若 b>=\varphi\left ( m \right ),则
\]

\[
a^{b} \equiv a^{b\ mod\ \varphi \left ( m \right )+\varphi\left ( m \right )}\left ( mod \ m \right )
\]

贝祖定理对于任意整数a,b，存在一对整数x,y,满足ax+by=gcd(a,b)

用欧几里得算法计算一组x,y的方法，称作“扩展欧几里得”算法

假设a>b
\[
(1) b=0:gcd(a,b)=a,ax+by=a,则x=1,y=0;
\]

\[
(2)b\neq0，如图
\]

求解扩展欧几里得

  1. int exgcd(int a,int b,int &x,int &y){//求解ax+by=gcd(a,b)x,y 并返回 最大公约数 
  2.     if(b==0){
  3.         x=1,y=0;
  4.         return a;
  5.     }
  6.     int d=exgcd(b,a%b,x,y);
  7.     int tmp=x;x=y;y=tmp-(a/b)*y;
  8.     return d;
  9. }

对于ax+by=c 该方程有解当且仅当

gcd(a,b)|c

此时可先求ax+by=gcd(a,b)的解x’,y’,即ax’+by’=gcd(a,b),令d=gcd(a,b),等式两边同时乘以c/d可得原方程的一组解为：
\[
\left\{\begin{matrix}x={x}’\cdot c/d
\\
y={y}’\cdot c/d
\end{matrix}\right.
\]
Ps:通解
\[
\left\{\begin{matrix}x={x}’\cdot \frac{c}{d}+k\frac{b}{d}
\\
y={y}’\cdot \frac{c}{d}-k\frac{a}{d}
\end{matrix}\right.
\]
•通解说明：

•ax+by=c，令a(x+t1)+b(y+t2)=c，可得

•at1=-bt2，左右两边必须同时包含a,b的因子

•最小的满足上式的正整数为lcm(a,b)

•即at1=-bt2=k*lcm(a,b)

•则t1=klcm(a,b)/a=kb/gcd(a,b)

• t2=…=-k*a/gcd(a,b)

版权声明：本文为saitoasuka原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/saitoasuka/p/10335891.html