欧拉定理 —— 数论四大定理之手

前言

在了解完欧拉函数以后，我们就仔细来看下 欧拉定理 的概念、证明 和 应用。

一、欧拉定理

n 和 a 为正整数，且 n, a 互素，即 gcd(a,n) = 1，则：a^{\phi(n)} \equiv 1 (mod \ n)\\

    证明过程如下：
    1、令 1 \to n 中与 n 互素的数（总共 \phi(n) 个）按顺序排列为：

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

    2、将这些数分别乘上a，得到如下序列： y_i = ax_i \ (1 \le i \le \phi(n))\\

    3、取其中任意两个数相减，得到： \begin{aligned} y_i - y_j &= ax_i - ax_j \\ &= a(x_i - x_j) \\ &= ab\end{aligned}\\

    上面的式子中 gcd(a, n)=1，且 |b| = |x_i - x_j| \lt n，所以 ab 不可能是 n 的倍数。从而得知 y_i 和 y_j 模 n 不同余。即 y_i \ mod \ n 有 \phi(n) 种余数。

    4、由欧几里得算法 (辗转相除法)，可以得到： \begin{aligned} gcd(n, y_i \ mod \ n) &= gcd(y_i, n) \\ &= gcd(ax_i, n) \\ &= 1\end {aligned}\\

    所以得出，y_i \ mod \ n 与 n 互素；

    5、综合 1、3 和 4，x_i 和 y_i \ mod \ n 必然是一一映射。所以将所有的 x_i 连乘，y_i \ mod \ n 连乘，两者必然模 n 同余。即： \begin{aligned} x_1 \times x_2 \times ... \times x_{\phi(n)} &\equiv y_1 \times y_2 \times ... \times y_{\phi(n)} \ mod \ n \\ &\equiv ax_1 \times ax_2 \times ... \times ax_{\phi(n)} \ mod \ n \\ &\equiv a^{\phi(n)} \times x_1 \times x_2 \times ... \times x_{\phi(n)} \ mod \ n \end{aligned} \\

    令 X = x_1 \times x_2 \times ... \times x_{\phi(n)}，原式可以简化为： X \equiv a^{\phi(n)} X \ mod \ n\\

表示成更加直观的等式为：

( a^{\phi(n)} - 1 )X= kn\\

    由于 gcd(X, n) = 1，则 a^{\phi(n)} - 1 必然得是 n 的倍数，才能满足等式条件。所以 a^{\phi(n)} 和 1 模 n 同余，即： a^{\phi(n)} \equiv 1 (mod \ n)\\

欧拉定理，得证。

二、欧拉定理的应用

求十进制表示都是 8，且是 L (1 \le L \le 2 * 10^9) 倍数的数的最小的长度，不存在则输出 0；

    我们假设这个最小长度为 x，则可以把这个数表示成如下形式：

n = 8 * \frac {10^x - 1}{9}\\

    由于是 L 的倍数，则有： n = kL\\

    等式联立如下： kL = 8 * \frac {10^x - 1}{9}\\

    等式两边同时乘上 9，可得： 9kL = 8 * (10^x - 1)\\

    等式两边同时除上 gcd(L, 8), 得到： \frac {9kL}{gcd(L,8)} = \frac {8} {gcd(L, 8)} (10^x - 1)\\

    我们发现等式右边的 \frac {8} {gcd(L, 8)} 部分，如果不为 1，肯定是能用 左边的 k 来抵消的，因为他是任意正整数。所以进一步化简等式如下： \frac {9k'L}{gcd(L,8)} = 10^x - 1\\

    从而转换成同余式有： 10^x \equiv 1(\ mod \ \frac {9L}{gcd(L,8)}) \\

    转化成了欧拉定理的形式，这时候，如果 gcd(10, \frac {9L}{gcd(L,8)}) \neq 1，则无解，否则通过求 \frac {9L}{gcd(L,8)} 的欧拉函数，就能得到 x 的一个可行解，然后再枚举 x 的因子，套入上面的等式，利用二分快速幂判定，求得最小的满足等式成立的 x 的值即可。

三、思考题

    求十进制表示都是 7，且是 L (1 \le L \le 2 * 10^9) 倍数的数的最小的长度，不存在则输出 0。