非素数n存在非零元m∈ℤ/nℤ满足mⁿ⁻¹≢1 mod n的证明方法

咱们可以通过分情况讨论来搞定这个证明，正好对应非素数的两种核心类型：素数幂、有多个不同素因子的合数，另外再提一下n=1的特殊情况：

情况1：n=1 #

ℤ/1ℤ里只有0元素，不存在题目要求的m∈ℤ/nℤ{0}。不过通常数论问题里讨论这类命题时，默认n≥2，所以咱们重点看下面两种情况。

情况2：n是素数幂（即n=p^k，k≥2，p为素数） #

咱们选m=p，显然m∈ℤ/nℤ{0}（因为p < p^k，所以p mod p^{k≠0）。计算m}(n-1) = p^(pk -1)：

• 因为k≥2，p≥2，所以p^k -1 ≥ 2^2 -1 = 3 > k，也就是说p的指数远大于p^k里p的次数k。
• 因此p^(pk -1) ≡ 0 mod p^k，而0显然不等于1 mod p^k，所以m(n-1)≢1 mod n，满足条件。

举个例子：n=4（2^{2），选m=2，2}(4-1)=8≡0 mod4≠1，完美符合。

情况3：n有至少两个不同的素因子（即n=ab，a,b>1且gcd(a,b)=1） #

这里用中国剩余定理来构造m：找一个整数m满足

• m ≡1 mod a
• m ≡0 mod b

这样的m肯定存在（比如m=b），而且m∈ℤ/nℤ{0}（因为m≡0 mod b，但b<n，所以m modn≠0）。现在看m^(n-1) modn的结果：

• 根据中国剩余定理，只要分别看moda和modb的结果：
  • moda时，m≡1，所以1^(n-1)=1 mod a；
  • modb时，m≡0，所以0^(n-1)=0 mod b；
• 如果m^(n-1)≡1 modn，那必须同时满足1 mod a和1 modb，但0≡1 modb是不可能的，矛盾！因此m^(n-1)≢1 modn，满足条件。

再举个例子：n=6=2×3，选m=3（满足3≡1 mod2，3≡0 mod3），3^(6-1)=243，243 mod6=3≠1，符合要求。

总结 #

所有n≥2的非素数，要么是素数幂，要么是多素因子合数，咱们都找到了对应的m满足条件。结合你已经证明的逆命题（素数时所有非零m都满足m^(n-1)≡1 modn），就完成了整个逻辑链的闭环~

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