如何证明欧拉定理？

如何证明欧拉定理？

关注问题

写回答

6 个回答

群论里的欧拉定理是一个很著名的定理，在前面的内容中，讲过费马定理，而欧拉定理就是费马定理的一个推广。欧拉定理里面有一个函数叫做欧拉函数，欧拉函数的一个定义是，n的欧拉函数表示从1到n的正整数中与n互质的数的个数。比如3的欧拉函数是2，因为1,2这两个数与3互质。易知对于素数p，它的欧拉函数是p-1。现在我们来看欧拉定理的表述。

欧拉定理：若（r , m）=1,则 $r^{\phi(m)}\equiv 1$ mod m

$\phi(m)$ 表示m的欧拉函数。

如果m是一个素数，它马上就退化成费马定理了。因为若m是一个素数，则任意的r都能使（r , m）=1，且m的欧拉函数就是m-1,这样同余方程就变为

$r^{m-1}\equiv 1$ mod m ,两边同时乘以r,就得到

$r^m\equiv r$ mod m,这不就是费马定理吗？

我们先用初等数论的方法来证明欧拉定理。

把1到m中与m互质的数列出来，从小到大记为 $X_1,X_2,...,X_{\phi(m)}$ ,

现在来看 $rX_1,rX_2,...,rX_{\phi(m)}$ ，我们断定 $rX_1,rX_2,...,rX_{\phi(m)}$

模m之后两两不同，且模m之后余数与m互质。

现在来证明这两个结论，先证明它们模m后两两不同。用反证法。

假设存在 $1\leq i<j\leq \phi(m)$ ,使得 $rX_i\equiv rX_j$ mod m,

那么有m | $rX_j- rX_i$ ,即 m | $r(X_j- X_i)$ ,

由于r与m互质，所以m | $（X_j- X_i）$ ，而由假设 $0<X_j- X_i<m$ ,

矛盾。

然后证明它们模m之后余数与m互质。仍然用反证法。

设 $rX_i$ 是这 $\phi（m）$ 个数中任意一个，假设 $rX_i\equiv x$ , $(x,m)\ne 1$ ,

所以 $rX_i=km+x$ ，设d=(x,m),则d | x , d | m,所以d | $rX_i$ ,

存在素数p | d,使 p| $rX_i$ ,由于 $(X_i，m)=1$ ,则p | r，与（m,r)=1 矛盾。

由这两个结论，可知 $rX_1rX_2...rX_{\phi(m)} \equiv X_1X_2...X_{\phi(m)}$ mod m

推出 $r^{\phi(m)}\equiv 1$ mod m

这样就用初等数论的方法证明了欧拉定理。若用群论的方法来证明，则是非常简洁而清晰的。

前面说到过 $I_m$ ，它是所有模m的同余类构成的簇。

$I_m$ 在加法下作成加法循环群，而在乘法下不作成群。

欧拉定理 $r^{\phi(m)}\equiv 1$ mod m ，我们从同余类的角度看，那么

1和 $r^{\phi(m)}$ 属于同一同余类，即 $\left[ r^{\phi(m)} \right]=\left[ 1 \right]$ ，根据同余类的乘法定义，

$\left[ r \right]^{\phi(m)} =\left[ 1 \right]$ ，这样要证明欧拉定理，就转化成证明

若(r,m)=1, $\left[ r \right]$ 的阶是 $\phi(m)$ 。

实际上在 $I_m$ 中所有满足(r,m)=1的构成 $\left[ r \right]$ 乘法阿贝尔群。

设 $E=\left\{ {\left[ r \right]\in I_m} | (r,m)=1 \right\}$ ,为了说明E是一个群，现在证明

同余类乘法在E中封闭，且E中任意元素在E中都有逆。

设 $[r],[r']\in E$ ,则 $r,r'$ 与m互质，于是 $rr'$ 与m互质，

所以 $[r][r']=[rr']\in E$ ,这样就证明了乘法在E中封闭。

对任意的 $[r]\in E$ ,由于(r,m)=1,于是存在整数s,t,使得rs+mt=1,

所以 $[r][s]=[rs]=[1-mt]=[1]$ ,即 $[s]$ 是 $[r]$ 的逆，

由于rs+mt=1,可知（s,m）=1，所以 $[s]\in E$ ,这样就证明了

E在同余类乘法下作成阿贝尔群，有了这个结论，欧拉定理就很显然了。

由于E这个群的元素个数是 $\phi(m)$ ,所以 $[r]^{ϕ(m)}=[1]$

编辑于 2022-10-27 · 著作权归作者所有

赞同 8

评论 0

更多回答