费马小定理与欧拉定理

· · 个人记录

1.欧拉（Euler）定理

定理内容： ∀m∈N^{*} , 若 (a,m)=1 ,则有 a^{ φ(m)} ≡ 1 (mod m)

证明：

设a_{1}，a_{2}，······，a_{φ(m)}是模 m 的一个简系，则由 (a,m)=1 ，可知aa_{1}，aa_{2}，······，aa_{φ(m)} 也是模 m 的一个简系。

因此有 a_{1}a_{2}······a_{φ(m)} ≡ aa_{1}·aa_{2}······aa_{φ(m)} ≡ a^{φ(m)}·a_{1}a_{2}······a_{φ(m)} (mod m)

即 m|(a^{φ(m)}-1)(a_{1}a_{2}······a_{φ(m)}) 。

又 (a,m)=1 ，则 (a_{1}a_{2}······a_{φ(m)},m)=1

故可知 m|a^{φ(m)}-1 ，获证！

练习题：

  1. 求证： ∀n∈N^{*} ，有 ∑_{d|n} φ(d) =n （已结束悬赏）
  2. 设 a_{1}，a_{2}，······，a_{n} 是 n 个有理数。已知对任意 m ∈N^{*} ，数 a_{1}^{m}+ a_{2}^{m}+···+a_{n}^{m}都为整数。求证：a_{1}，a_{2}，······，a_{n}都是整数

注1：

当 m=p 时， p 为质数，有 φ(p)=p-1 ，此时，可推出费马小定理。

注2：

已知 m 的标准分解，则 φ(m)= p_{1}^{\alpha_{1}-1}(p_{1}-1)p_{2}^{\alpha_{2}-1}(p_{2}-1)···p_{t}^{\alpha_{t}-1}(p_{t}-1) = m(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})···(1-\frac{1}{p_{t}})

2.费马（Fermat）小定理

定理内容：一般的，设 p 是一个质数， ∀a∈Z ，有 a^p \equiv a\pmod p 。特别的，若 p \nmid a ，则 a^{p-1}\equiv 1 \pmod p

证明：

只须证 a 属于Z^{*}

下采用归纳证明：

当 a=1 时，命题显然成立。

假设 a=k 时成立，即有 p\mid(k^p-k)

当 a=k+1 时，则由 二项式定理 可得 (k+1)^p-(k+1)=k^p + C_{p}^{1}k^{p-1} + ···+C_{p}^{p-1}k+1-k-1 ≡ k^{p}-k \equiv 0 \pmod p

故 ∀a∈Z ，有 a^p\equiv a \pmod p 。

结合 p\nmid a 时， (p,a)=1 ，可知此时有 p\mid (a^{p-1}-1) 。

故命题成立！

注：

证明中用到了 1 \leq k \leq p-1 时，有 p|C_{p}^{k}

练习题：

设 p 为奇质数，求证： ∑_{i=1}^{p-1} 2^i·i^{p-2} ≡ ∑_{i=1}^{\frac{p-1}{2}} i^{p-2} (mod p)

练习题每题悬赏1RMB