数论的一些简单定理证明


  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    例如(0123456789,)是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); 

相关