欧拉定理证明疑问：如何推导n | (a^φ(n)-1)？

嘿，这个问题问得特别好——很多人第一次接触群论视角下的欧拉定理时，都会在这里卡一下，因为群里的“等于1”和整数里的“模n同余1”确实是两个层面的概念，得把它们的对应关系理清楚才行。

先明确U(n)的本质 #

U(n)是模n的既约剩余类乘法群，这里的每个元素不是整数本身，而是一个剩余类：当整数a满足gcd(a,n)=1时，它对应的剩余类是：

[a] = { ..., a-2n, a-n, a, a+n, a+2n, ... }

也就是所有和a模n同余的整数构成的集合。

群里的运算与单位元 #

这个群的乘法规则是剩余类的乘法：[a] * [b] = [a*b mod n]，简单说就是把两个整数相乘后取模n，得到的结果所在的剩余类就是乘积。
群的单位元是[1]——也就是所有模n余1的整数构成的剩余类，因为任何剩余类乘[1]都等于它自己：[a] * [1] = [a*1 mod n] = [a]。

群论结论到整数同余的翻译 #

课堂里提到的a^{|U(n)|}=1，准确表述其实是：群中的元素[a]的φ(n)次幂等于群的单位元[1]，也就是[a]^φ(n) = [1]（这里的幂是群里乘法运算重复φ(n)次）。

那这个群论结论怎么转化为整数层面的关系呢？

• 群里的[a]^φ(n)展开就是[a] * [a] * ... * [a]（共φ(n)次），按照群乘法规则，这个结果等于[a^φ(n) mod n]，也就是[a^φ(n)]（因为a^φ(n)和它模n的结果属于同一个剩余类）。
• 剩余类相等的定义是：[x] = [y]当且仅当**n整除x - y**，也就是x ≡ y mod n。

所以把[a^φ(n)] = [1]翻译到整数层面，就是n | (a^φ(n) - 1)，进一步写成同余式就是a^{φ(n)} ≡ 1 (mod n)——这正是欧拉定理的结论。

核心逻辑就是：群里的“等于单位元”是剩余类层面的相等，而剩余类相等的定义直接对应了整数的整除/同余关系，这就是两者之间的关键关联。

内容的提问来源于stack exchange，提问作者user482939