假设 n 是最小的使得存在正整数a满足aⁿ≡1(nod n)且a+1, a²+2,…, aⁿ+n不构成模n完全剩余系的正整数
n=1时不存在这样的a，所以n≥2
设d是最小的使得a^d≡1(mod n)的正整数，由于a^n≡1(mod n)，所以a和n互素，由欧拉定理a^φ(n)≡1(mod n)，则d≤ φ(n)，所以d<n
并且 a^(n, d)≡1 (mod n)，由于d最小，所以只可能(a, d)=d，也就是 d ℓ n
所以 a^d ≡ 1(mod d)
假设存在1≤i<j≤n，使a^i + i ≡ a^j + j (mod n)
设1≤r, s≤d，使 i≡r(mod d)，j≡s(mod d)
如果r=s，则i ≡ j(mod d)，可得 0≡a^i - a^j ≡ j - i (mod n)，和 i<j 矛盾
所以 r≠s，j- i ≡ a^i - a^j ≡ a^r -a^s (mod n)，由 d ℓ n 可得 j- i ≡a^r - a^s (mod d)
而 j - i ≡ s -r (mod d)
所以 s - r ≡ a^r - a^s (mod d)，a^r + r ≡ a^s + s (mod d)
说明 a^d≡1(mod d)且 a+1, a²+2,…, a^d+d 不构成模d 的完全剩余系，但 d < n，和n最小的假设矛盾
所以这样的正整数n 其实是不存在的，就证明了原题