欧拉定理存在性的直观双向证明问询（不借助简化剩余系置换性质）

嗨，我懂你现在的困惑——已经顺利搞定了定理的一个方向，但反过来不想用简化剩余系置换性质的话，就不知道从哪下手了对吧？先帮你再理清楚你已经完成的部分，然后给你一个超直观的反向证明思路，完全不用那些置换相关的概念~

首先，你已经证明的正向推导是完全没问题的：

如果存在整数k使得 (a^k \equiv 1 \pmod{m})，那意味着 (a^k = pm + 1)（p是某个整数）。因为连续整数是互质的，所以(a^{k)和(pm)互质，这直接就能推出a和m也必须互质——毕竟如果a和m有公共的质因数，那这个质因数肯定也会整除(a}k)和pm，就矛盾了。

接下来重点说反向的证明，也就是当a和m互质时，一定存在某个正整数k使得(a^k \equiv 1 \pmod{m})，这里用鸽巢原理来解释就特别直观：

• 首先，考虑无穷序列：(a^1 \bmod m)，(a^2 \bmod m)，(a^3 \bmod m)，…… 因为a和m互质，所以a的任何幂次都和m互质，所以这个序列里的每一项都是与m互质的余数。
• 但模m下，与m互质的余数总共只有有限个（比如模m的余数从0到m-1，其中只有那些和m没有公共质因数的数才符合，数量是有限的）。
• 根据鸽巢原理，无穷多个元素放进有限个“盒子”（也就是有限个互质余数）里，必然有两个不同的指数i和j（假设i > j），使得(a^i \equiv a^j \pmod{m})。
• 这时候，因为a和m互质，所以(a^{j)也和m互质，那么(a}j)在模m下是有逆元的（简单说就是存在某个整数x，使得(a^j \cdot x \equiv 1 \pmod{m})）。我们给等式(a^i \equiv a^j \pmod{m})的两边同时乘以这个逆元：
  [
  a^i \cdot x \equiv a^j \cdot x \pmod{m}
  ]
  左边化简后是(a^{i-j})，右边是1，所以最终得到：
  [
  a^{i-j} \equiv 1 \pmod{m}
  ]
• 取k = i - j（这显然是个正整数），就找到了我们要的那个k！

这个思路完全没用到简化剩余系的置换性质，用最基础的鸽巢原理和逆元存在性（而逆元存在性本身也是a和m互质的直接推论）就搞定了，是不是很直观？

备注：内容来源于stack exchange，提问作者elcocodrilotito