欧拉定理

概念：\(a^{\phi(n)} mod n = 1\), 其中a与n互质

证明过程：

先定义这么一组数{\(x_1\), \(x_2\), \(x_3\)….., \(x_{\phi(n)}\)}, 这些数就是欧拉函数里所有小于n而且互质的数，作为第一个集合。

然后将里面每一个元素乘以a, 得到{\(a * x_1\), \(a * x_2\), \(a * x_3\)….., \(a * x_{\phi(n)}\)}

因为任意的\(x_i\)都是和n互质的，那么\(a * x_i\)也应该和n互质，所以：

{\(x_1 mod n\), \(x_2 mod n\), \(x_3 mod n\)….., \(x_{\phi(n)} mod n\)}

与

\(a * x_1 mod n\), \(a * x_2 mod n\), \(a * x_3 mod n\)….., \(a * x_{\phi(n)} mod\)}

两个集合互为置换集，置换集就是两个集合元素全部一样，但是顺序不同。

所以将两个集合里的所有元素乘起来，结果应该一样，即：

\(x_1 * x_2 * x_3 * x_{\phi(n)} mod n\)

\(a^{\phi(n)} * x_1 * x_2 * x_3 * x_{\phi(n)} mod n\)

由消去律，得到：

\(a^{\phi(n)} mod n = 1\)

得证。

费马定理

概念：若p是质数，\(a^{p-1} mod p = 1\), a是不能被质数p整除的数，换句话说就是a不能是p的整数倍

证明过程：

由欧拉定理得：\(a^{\phi(n)} mod n = 1\)，令n为p，因为p是质数，所以\(\phi(p) = p - 1\)

所以\(a^{p-1} mod p = 1\)，得证。

概念：如果有这样的式子:

其中\(m_1, …, m_n\)互质, x有解，并且可以求出通解的形式。

通解形式：

先求M = \(m_1* …* m_n\)，得到\(M_i = M / m_i\)

然后得到所有的\(y_i\)使得\(M_i * y_i mod 1\)

就可以得到通解X = \(\sum_{i=1}^{K}(M_iY_ia_i)\)

证明也非常的简单：

将得到的通解X代入到这个方程组，比如代入到第一个方程组：

\( \sum_{i=1}^{K}(M_iY_ia_i) mod m_1 = a_1 mod m_1 \)

由于除了i=1的其他累加项mod m_1都是0，因为每一项都含有一个累成，是它的倍数，所有消去累加，只留一项i=1的：

\(M_1Y_1a_1) mod m_1 = a_1 mod m_1\)

等于：

\((M_1*Y_1 mod m_1) * (a_1 mod m_1) = a_1 mod m_1\)

由于M_1和Y_1是对m_1的乘法逆元，所以前面一项为1，删掉。

\((a_1 mod m_1) = a_1 mod m_1\)

恒等，同理可以证明i不等于1的其他情况，所以这个就是他的通解。

很简单的证明，就是先求出来通解，再代回方程组，发现就是通解，于是就证明完毕了。

概念：gcd(a, b) = gcd(b, a mod b)

证明:

令 c = gcd(a, b), 则可令a = mc, b = nc, 其中m和n必然互质，不然c就不是最大公因数

令 r = a - kb = mc - nck = (m - nk)*c，其中(m-nk)必然与n互质，因为m与n互质，nk整除n

r = (m - nk) * c

b = n * c

c前面的因数是互质的，那么r和b 的最大公因数自然也只能是c了，证明完毕