设m=aⁿ-1，如果n不整除φ(m)，设φ(m)=kn+r，其中k, r为整数且0<r<n
因为a与m互素，由欧拉定理，a^φ(m)≡1(mod m)
又因为aⁿ≡1(mod m)，所以a^r≡a^(kn+r)≡a^φ(m)≡1(mod m)
可知m整除a^r-1，a≥2时a^r-1是正整数，则m≤a^r-1< aⁿ-1 =m，矛盾
所以φ(m)一定是n的倍数
因为a与m互素，由欧拉定理，a^φ(m)≡1(mod m)
又因为aⁿ≡1(mod m)，所以a^r≡a^(kn+r)≡a^φ(m)≡1(mod m)
可知m整除a^r-1，a≥2时a^r-1是正整数，则m≤a^r-1< aⁿ-1 =m，矛盾
所以φ(m)一定是n的倍数
