# 欧几里得定理

其实就是求 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 互质时。

更新于

请我喝[茶]~( ̄▽ ̄)~*

PocketCat 微信支付

微信支付

PocketCat 支付宝

支付宝