1 1.gcd(a,b)=gcd(b,a-nb);默认a>=b;
2 设gcd(a,b)=d,gcd(b,a-nb)=k;
3 k|b,k|a-nb;-->k|a
4 即k为a,b的公因数则k|d;
5 又因为d|b,d|a ,所以d|a-nb;所以 d|k-->k=d;
6 又因为当n=q时,a-nb=r;即gcd(a,b)=gcd(b,a%b);
7
8 证明裴蜀定理;
9 ax+by=d;存在x,y使得等式成立;
10 想求两个数的公因数,一个简单的想法是r=0时gcd(a,b)=b;
11 由上式的gcd替换
12 a=bq1+r1;
13 b=r1q2+r2;
14 ...这些减号下标
15 rx-1=rkqx+rx
16 直到rx=0;
17 即rk|rx-1...rk|a, rk|b所以gcd(a,b)=rk;但是ax+by不一定是a,b,最大公因数,只能说是最大公因数的倍数;即d|ax+by;
18 因为a=k1d,b=k2d,ax+by=d(ak1+bk2);
19
20 上式子可知
21 rx-2=rx-1qkx+rk 即rk为rx-2,rx-1的线性表达;
22 同理rk为rx-2,rx-3 的线性表达
23 ...
24 rk为a,b线性表达;
25 即rk=ax+by;
26
27 拓展欧几里得(利用gcd(a,b)=gcd(b,a%b),其中a%b=a-[a/b]*b)
28 ax+by=bx'+(a-(a/b)*b)y';
29 右边整理 ax+by=b(x'-(a/b)*y')+ay';
30 对比系数
31 x=y' y=x'-(a/b)*y' ;
32
33 对于最后一个时刻ax'+by'=a,(此时b等于0,y'随便取值不影响,这里取0)所以存在x'=1,y'=0;现在往前推就可以推出真正的x,y
34
35 往后拓展一些信息;
36 逆元存在的必要条件 ax≡1(modb)-->等价于ax+by=1即 gcd(a,b)|1所以gcd(a,b)只能是1,即a,b互质
37 所以逆元存在的条件是 a,b互质,只有当b为质数,加上默认条件 a,b,互质才能用费马小定理求逆元
38 费马小定理求逆元 a^(p-1)≡1(modp)所以逆元是 a^(p-2) 这时候可以用快速幂来求逆元
39
40 先来证明逆元的唯一性吧;
41 反证法;不妨设存在两个逆元x1 ,x2;
42 ax1≡1(modb);
43 ax2≡1(modb);
44 ax1-ax2 ≡0(mod b)
45 即b|a(x1-x2) 上面已经说过逆元存在 a,b互质所以 b|(x1-x2) 即x1≡x2(modb)在模b意义下x1=x2;证毕;
46
47 来用完全剩余系的知识证明费马小定理和欧拉定理
48 先用逆元证威尔逊定理 (p-1)! ≡-1(mod p) p为质数
49 a*a≡1(mod p)--> p|(a+1)(a-1)-->a=1或a=p-1 ;所以在模p意义下只有1和p-1的逆元是他们本身
50 则除去1,(p-1),而p-1≡-1(mod p) 剩下是偶数对且均与p互质,由逆元唯一性 证毕;如果不是两两配对则至少存在一对产生两对逆元,则逆元个数>p,矛盾
51
52 完系,缩系
53 数字系≡0.1.2...n-1(mod n)
54 例如(0,1,2,3,4,5,6,7,8,9,)是mod6的一个完系
55 缩系
56 数字系有与p互质的所有同余
57 例如(1,5,7)mod6
58 证明一些性质 若a1.a2...ak为模n的完系;则当 (a,n)=1 ;aa1.aa2...aak仍为完系
59 证明:
60 a1...ak两两模n不同余
61 对于n不整除ax-ay ,若(a,n)互质则n不整除a(ax-ay);证毕;
62 对于缩系同理
63 若a1.a2...ak为模n的缩系;则当 (a,n)=1 ;aa1.aa2...aak仍为缩系
64 欧拉函数:φ(n):1-n中与n互质的个数称为欧拉函数
65 考察 a1...a φ(n)为模n的缩系
66 则aa1*aa2*...*a a φ(n)≡a1*a2...*a φ(n) mod(n)
67
68 这里要说的是,在同余意义下加减乘是跟普通运算等价的,但是除法不是,两边要约去一个数即做除法)
69 两边能约去一个数的条件是(a,n)=1,互质才能约
70 假设ax ≡ay(mod n) gcd(a,n)=1可以推 x ≡y(mod n) 因为 n|a(x-y)若 (a,n)=1,则n|(x-y);
71 若不互质直接约去 不能保证n|(x-y);
72
73 接着证明整理 a^(φ(n))*a1*a2...*a φ(n)≡a1*a2...*a φ(n) mod(n);这里a1..a φ(n)与n均互质
74 所以 a^(φ(n))≡1(mod n);
75 特别的当n为质数时,φ(n)=n-1;
76 即 a^(n-1)≡1(mod n) 费马小定理
77 所以说费马小定理是欧拉定理的一个特例,当然用上面的方法证明费马小定理也是同理的
78 1...n-1≡a1*a2...*a(n-1) (mod n)
79 a^(p-1)≡1(mod n)
80
81 这也就是为什么费马小定理需要n为质数,以及逆元为什么需要互质条件
82
83 欧拉函数:φ(n):1-n中与n互质的个数称为欧拉函数
84 用分解定理来解释欧拉函数
85 对于任意大于1的数n,均有n=p1^(a1)*p2^(a2)*...*pn^(an),其中pi为质数,ai为该质数的次数
86 则一个数的因数个数由乘法原理=(a1+1)*(a2+1)*...*(an+1)个每个质因数次数可取的幂,包括0次;
87 则所有质因数之和=(0+1..+a1)*(0+1+...+a2)*...*(0+1+...+..an)对于上式的展开;
88 组合(1-1)^n=c(n,0)-c(n,1)+...+(-1)^(n)c(n,n);
89 即c(n,0)+c(n,2)+..+c(n,n-2)=c(n,1)+..+c(n,n) n为奇数
90 现在回来欧拉函数;
91 1-n中与n不互质的数 n/p1 n/p2...n/pn;
92 这里面要用容斥原理,因为有些数包含几种属性
93 那么与n不互质的数就是n-((∑n/(pi))-(∑n/(pi*pj))+...+((-1)^(n+1)∑(n/(pi*..*pn))) )
94 整理后 n(1-(∑1/pi) + (∑1/(pipj)) +..+(-1)^(n)(∑1/(pi*..*pn)) )
95 观察后 即 n(1-1/p1)*(1-1/p2)*...*(1-1/pn)
96 因为上式由2^n项 c(n,0)+c(n,1)+...+c(n,n)=2^n(算上1,所以观察后n个括号构造两项恰好是2^n项)
97
98
99 const int mod=p;
100 ll quimul(int a,int n)
101 {
102 ll ans=1;//例如a^k 写出k的二进制a^(2^k+...+2^1+2^0) =a^(2^k)*...*a^(2^1)*a^(2^0) 此时我们利用
103 while(n)// 用换元思想,令a^(2^0)=t;a^(2^1)=t*t--> 同理一直用整体思想 a^(2^2)= a^(2^1)*a^(2^1)
104 {// a^(2^k)=a^(2*2^(k-1)) =a^(2^(k-1)+2^(k-1))=a^(2^(k-1))*(2^(k-1));
105 if(n&1)ans=ans*a%mod;
106 n>>=1;
107 a=a*a%mod;
108 }
109 return ans;
110 }
111 调用时候调用quimul(a,p-2);