请证明欧拉定理

欧拉定理（Euler’s Theorem）是数论中的一个重要结果，它描述了模运算下的幂的性质。具体来说，欧拉定理表述如下：

对于任何互质的整数 $a$ 和 $n$，即 $\gcd(a, n) = 1$，有：
$ a^{\phi(n)} \equiv 1 \pmod{n} $
其中，$\phi(n)$ 是欧拉函数，表示小于 $n$ 且与 $n$ 互质的正整数的个数。

证明步骤

步骤 1：理解欧拉函数 $\phi(n)$

$\phi(n)$ 表示小于 $n$ 且与 $n$ 互质的正整数的个数。例如：
- $\phi(1) = 1$
- $\phi(2) = 1$
- $\phi(3) = 2$

作者注：$\phi(1) = 0$

如果 $n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}$ 是 $n$ 的素因子分解形式，则：
$ \phi(n) = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_m}\right) $

步骤 2：构造一组与 $n$ 互质的整数

设 $a_1, a_2, \ldots, a_{\phi(n)}$ 是小于 $n$ 且与 $n$ 互质的所有整数。

步骤 3：乘积与模运算性质

考虑这些互质整数的乘积：
$ P = a_1 a_2 \cdots a_{\phi(n)} $

我们将 $a \cdot a_1, a \cdot a_2, \ldots, a \cdot a_{\phi(n)}$ 按模 $n$ 计算，形成新的数列：
$ a a_1, a a_2, \ldots, a a_{\phi(n)} $

因为 $a$ 与 $n$ 互质，乘以 $a$ 后的数列仍然是小于 $n$ 且与 $n$ 互质的整数，只是顺序可能不同。因此，新的数列是 $a_1, a_2, \ldots, a_{\phi(n)}$ 的一个排列。即这两个数列模 $n$ 同余：

$ \{a a_1, a a_2, \ldots, a a_{\phi(n)}\} \equiv \{a_1, a_2, \ldots, a_{\phi(n)}\} \pmod{n} $

步骤 4：比较乘积

比较这两个数列的乘积：
$ (a a_1) (a a_2) \cdots (a a_{\phi(n)}) \equiv a_1 a_2 \cdots a_{\phi(n)} \pmod{n} $

即：
$ a^{\phi(n)} (a_1 a_2 \cdots a_{\phi(n)}) \equiv a_1 a_2 \cdots a_{\phi(n)} \pmod{n} $

步骤 5：利用互质性质

因为 $a_1, a_2, \ldots, a_{\phi(n)}$ 都与 $n$ 互质，所以它们的乘积 $a_1 a_2 \cdots a_{\phi(n)}$ 也与 $n$ 互质。设 $d = a_1 a_2 \cdots a_{\phi(n)}$，则有 $\gcd(d, n) = 1$，所以我们可以消掉 $d$：

$ a^{\phi(n)} d \equiv d \pmod{n} $

因为 $\gcd(d, n) = 1$，可以两边同除 $d$：

$ a^{\phi(n)} \equiv 1 \pmod{n} $

这就证明了欧拉定理。

请证明 $a \cdot a_i \bmod n$ 与 $n$ 互质

为了证明 $ a \cdot a_i \mod n $ 与 $ n $ 互质，我们需要一些数论的基本性质。以下是详细的证明过程：

定义和性质

• $ n $ 是一个正整数。
• $ a $ 是一个与 $ n $ 互质的整数，即 $\gcd(a, n) = 1$。
• $ a_i $ 是小于 $ n $ 且与 $ n $ 互质的整数之一，即 $\gcd(a_i, n) = 1$。

我们要证明 $ (a \cdot a_i) \mod n $ 与 $ n $ 互质。

证明过程

步骤 1：定义 $ b $
设 $ b = a \cdot a_i \mod n $，即 $ b $ 是 $ a \cdot a_i $ 除以 $ n $ 的余数。

步骤 2：引入性质
我们需要证明 $ b $ 与 $ n $ 互质，即 $\gcd(b, n) = 1$。

步骤 3：运用模运算的性质
由于 $ b = a \cdot a_i \mod n $，我们有：
$ b = a \cdot a_i - k \cdot n $
其中 $ k $ 是某个整数，使得 $ b $ 满足上述等式。

步骤 4：利用 $\gcd$ 的性质
我们知道：
$ \gcd(a, n) = 1 $
$ \gcd(a_i, n) = 1 $

这意味着 $ a $ 和 $ a_i $ 都没有与 $ n $ 的公因子，除了 1。

步骤 5：证明 $\gcd(b, n) = 1$
我们要证明 $ \gcd(b, n) = 1 $。假设 $\gcd(b, n) = d > 1$，那么 $ d $ 必须同时整除 $ b $ 和 $ n $。由 $ b = a \cdot a_i - k \cdot n $，我们知道 $ d $ 也整除 $ a \cdot a_i $。

因此，$ d $ 必须整除 $ a $ 和 $ a_i $ 中至少一个。

但是，由于：
$ \gcd(a, n) = 1 $
$ \gcd(a_i, n) = 1 $
这意味着 $ a $ 和 $ a_i $ 都与 $ n $ 互质，$ d $ 不可能是 $ a $ 和 $ a_i $ 的公因子，除非 $ d = 1 $。

作者注：$d$ 能整除 $a \cdot a_i$ 并不代表 $ d $ 必须整除 $ a $ 和 $ a_i $ 中至少一个。例如 $40$ 能整除 $6 \times 20$，并不代表 $40$ 能整除 $6$ 或 $20$。这部分证明可改为：

由于：
$ \gcd(a, n) = 1 $
$ \gcd(a_i, n) = 1 $
因此 $a \cdot a_i$ 与 $n$ 不含公共质因子。又因为 $\gcd(b, n) = d > 1$，所以 $d$ 的质因子都在 $n$ 中。假设 $d$ 能整除 $a \cdot a_i$，则 $d$ 与 $a \cdot a_i$ 至少存在一个公共质因子 $p^*$，它也是 $n$ 的质因子，这与 $a \cdot a_i$ 和 $n$ 不含公共质因子矛盾。

步骤 6：结论
由于假设 $ \gcd(b, n) = d > 1$ 导致矛盾，我们得出结论：
$ \gcd(b, n) = 1 $

因此，$ b = a \cdot a_i \mod n $ 与 $ n $ 互质。

请证明 $a \cdot a_i, a \cdot a_j$ 模 $n$ 不同余

为了证明对于与 $n$ 互质的整数 $a$ 和两个与 $n$ 互质的小于 $n$ 的整数 $a_i$ 和 $a_j$（且 $a_i \neq a_j$），$a \cdot a_i \not\equiv a \cdot a_j \pmod{n}$，我们需要展示如果 $a \cdot a_i \equiv a \cdot a_j \pmod{n}$，则会导致 $a_i \equiv a_j \pmod{n}$ 的矛盾。

证明过程

假设：
假设 $a \cdot a_i \equiv a \cdot a_j \pmod{n}$，我们有：
$ a \cdot a_i \equiv a \cdot a_j \pmod{n} $

步骤 1：消去 $a$

由于 $a$ 与 $n$ 互质，即 $\gcd(a, n) = 1$，我们可以在模 $n$ 的意义下对等式两边同时除以 $a$。这相当于乘以 $a$ 在模 $n$ 下的逆元。记 $a^{-1}$ 为 $a$ 在模 $n$ 下的逆元，即 $a \cdot a^{-1} \equiv 1 \pmod{n}$。

因此，我们可以将等式两边乘以 $a^{-1}$：
$ a^{-1} \cdot (a \cdot a_i) \equiv a^{-1} \cdot (a \cdot a_j) \pmod{n} $

根据模运算的性质：
$ (a^{-1} \cdot a) \cdot a_i \equiv (a^{-1} \cdot a) \cdot a_j \pmod{n} $

由于 $a^{-1} \cdot a \equiv 1 \pmod{n}$：
$ 1 \cdot a_i \equiv 1 \cdot a_j \pmod{n} $

简化后得到：
$ a_i \equiv a_j \pmod{n} $

步骤 2：得出矛盾

我们假设 $a_i$ 和 $a_j$ 是小于 $n$ 且与 $n$ 互质的整数，且 $a_i \neq a_j$。如果 $a_i \equiv a_j \pmod{n}$，这意味着：
$ a_i = a_j + k \cdot n $

其中 $k$ 是某个整数。但由于 $a_i$ 和 $a_j$ 都小于 $n$，且 $0 \leq a_i, a_j < n$，我们知道 $k$ 必须为 0 才能满足此条件。因此，$a_i = a_j$，这与假设 $a_i \neq a_j$ 矛盾。

结论：

由于假设 $a \cdot a_i \equiv a \cdot a_j \pmod{n}$ 导致 $a_i \equiv a_j \pmod{n}$ 的矛盾，我们可以得出结论：
$ a \cdot a_i \not\equiv a \cdot a_j \pmod{n} $

因此，对于与 $n$ 互质的整数 $a$ 和两个不同的与 $n$ 互质的小于 $n$ 的整数 $a_i$ 和 $a_j$，我们证明了 $a \cdot a_i$ 和 $a \cdot a_j$ 在模 $n$ 下不同余。

我的补充

记 $A = \lbrace a_1, a_2, \cdots, a_{\phi(n)} \rbrace,\ B = \lbrace a \cdot a_i \bmod n \mid a_i \in A \rbrace$。由于 $B$ 中无重复元素，所以它的大小等于 $A$，又因为 $B$ 中元素都小于 $n$ 且与 $n$ 互质，所以它是所有小于 $n$ 且与 $n$ 互质的正整数的集合，因此 $A = B$。