欧几里得定理

其实就是求gcd的辗转相除法,gcd(a,b)==gcd(a-b,b),由此可以把a中的b全部拿掉,gcd(a,b)==gcd(a%b,b), a是大于b的
gcd(a,b)==gcd(b,a%b)

欧拉函数

具体证明点击我
X(N)==N * (1/p1) * (1/p2) * (1/p3) *… *(1/pn)(pi为N的质因子)

性质

  1. 对于任意一个质数 p ,φ(n)=n−1
    因为n为质数,与他互质的个数就是 n-1

  2. 当 gcd(n,m)=1时,φ(nm)=φ(n)φ(m)
    因为φ(n)是积性函数。 积性函数指对于所有互质的整数a和b有性质f(ab)=f(a)f(b)的数论函数。

  3. 若 n=pk 其中p为质数,则φ(n)=pk−pk−1=(p−1)pk−1
    1→n中除了p的倍数,都与pk互质,1→n中p倍数的个数为 pk÷p=pk−1

  4. 所有小于n与n互质个数的和sum=n × φ(n)/2

    推导点击我

  5. 如果 i mod p=0,其中p为质数,则 φ(i ∗ p)=p ∗ φ(i),否则φ(i ∗ p)=(p−1)φ(i)

  6. n=∑d|nφ(d) (d|n)指n是d的倍数

  7. 当 N > 2 时,φ( N )是偶数

欧拉定理

对于互质的整数a,m,有 aφ(m)≡1 (mod m)。

费马小定理

费马小定理(Fermat’s little theorem)是数论中的一个重要定理,在1636年提出。如果p是一个质数,而整数a不是p的倍数,则有a^(p-1)≡1(mod p)

主要应用于求高阶次幂对某个数求余数,点击我

逆元

a(m-1)=1(mod m), a * a(m-2)=1(mod m),所以a的逆元是:a(m-2) ,当m与a互质时。


一个好奇的人