同余定理欧拉定理及费马小定理

Aisaka_Taiga · 2022-07-12 09:09:14 · 个人记录

同余定理

定义：如果两个数 a 和 b 除以一个数 m 的余数相同，则称 a 与 b 同余，记作 a\equiv b\pmod{m}。

基本性质：

1. 反身性：a\equiv a\pmod{n};

2. 对称性：若 a\equiv b\pmod{n},则 b\equiv a\pmod{n};

3. 传递性：若 a\equiv b\pmod{n},b\equiv c\pmod{n},则 a\equiv c\pmod{n};

4. 同余式相加：若 a\equiv b\pmod{n},c\equiv d\pmod{n},则a+c\equiv b+d\pmod{n};

5. 同余式相乘：若 a\equiv b\pmod{n},c\equiv d\pmod{n},则a\times c\equiv b\times d\pmod{n};

6. 同余式相减：若 a\equiv b\pmod{n},c\equiv d\pmod{n},则a-c\equiv b-d\pmod{n};

7. 若 a\equiv b\pmod{n},则a\times m\equiv b\times m\pmod{n}（其中 m 为自然数）

8. 若 a\times c\equiv b\times c\pmod{n},\gcd(c,n)=1,那么 a\equiv b\pmod{n};

9. 若 a\equiv b\pmod{n},则 a^{n}\equiv b^{n}\pmod{n};

10. 若 a\equiv b\pmod{n},c\equiv d\pmod{n},e\equiv f\pmod{n}.....x\equiv y\pmod{n},则 a+c+e+...+x\equiv b+d+f+...+y\pmod{n};

欧拉定理

内容：若正整数 a，n，互质，则 a^{\varphi (n)}\equiv 1 \pmod{n}。

证明：设 X_{1},X_{2}......X_{\varphi(n)} 是 1\sim n 与 n 互质的数。

首先我们来考虑一些数：aX_{1},aX_{2}.....aX_{\varphi(n)}。

这些数有如下两个性质：

（1）任意两个数模 n 的余数一定不同。

证明：若存在 aX_{1}\equiv aX_{2} \pmod{n} 则存在 n\mid (aX_{1}-aX_{2})，而 a，n 互质，并且 (aX_{1}-aX_{2})<n，所以 n 不可能整除 (aX_{1}-aX_{2}) ，也就是说不存在 aX_{1}\equiv aX_{2} \pmod{n}，所以对于任意的与 n 互质的 X_{i} 均成立。故得证。

那么因为有 \varphi(n) 个这样的数，X_{i}\pmod{n}(i=1 \sim \varphi(n)) 所以就有 \varphi(n) 个不同的余数，并且模数分别为 (0\sim n-1)。

（2） 对于任意的 aX_{i}\pmod{n} 都与 n 互质。这不难想，因为 a 与 n 互质是欧拉函数的条件，X_{i} 是 (1\sim n) 与 n 互质的数的集合中的元素。所以如果 aX_{i} 作为分子，n 作为分母，那么他们构成的显然是一个最简分数，也就是说 aX_{i} 和 n 互质。接下来就可以用欧几里得算法：因为 \gcd(aX_{i},n)=1 所以 \gcd(aX_{i},n)=\gcd(n,aX_{i}\bmod n)=1。

把上面两个性质结合一下来说，aX_{1}\pmod{n} ,aX_{2}\pmod{n}....aX_{\varphi(n)}\pmod{n} 构成了一个集合（性质1已经证明了所有元素的互异性），并且这些数是 1\sim n 与 n 互质的所有数构成的集合（性质1已经说明）。这样，上述集合经过一定的排序后和集合 \{X_{1},X_{2}....X_{\varphi(n)}\} 完全一一对应，那么：aX_{1}\pmod{n}\times aX_{2}\pmod{n}\times....\times aX_{\varphi(n)}\pmod{n}=X_{1}\times X_{2}\times.....\times X_{\varphi(n)}。

因此我们可以写出以下式子：