an−1+ba^{n-1}+ban−1+b に aaa を掛けると ana^nan に ababab を加えたものになり、オイラーの定理により ana^nan は法 MMM のもとで 111 と合同なので、この積は MMM の倍数となる。もう一方でも同様であり、MMM が両者の最大公約数を割り切ることが強制される。
n≡0(modφ(M))n\equiv0\pmod{\varphi(M)}n≡0(modφ(M)) かつ gcd(a,M)=1\gcd(a,M)=1gcd(a,M)=1 なので、オイラーの定理より an≡1(modM)a^n\equiv1\pmod Man≡1(modM) となる。すると a(an−1+b)=an+ab≡1+(M−1)=M≡0(modM)a(a^{n-1}+b)=a^n+ab\equiv1+(M-1)=M\equiv0\pmod Ma(an−1+b)=an+ab≡1+(M−1)=M≡0(modM) であり、gcd(a,M)=1\gcd(a,M)=1gcd(a,M)=1 なのでこれより M∣an−1+bM\mid a^{n-1}+bM∣an−1+b が得られる。同様に bn≡1(modM)b^n\equiv1\pmod Mbn≡1(modM) から b(bn−1+a)=bn+ab≡0(modM)b(b^{n-1}+a)=b^n+ab\equiv0\pmod Mb(bn−1+a)=bn+ab≡0(modM) が得られ、M∣bn−1+aM\mid b^{n-1}+aM∣bn−1+a となる。したがって M∣gcd(an−1+b,bn−1+a)=xn−1M\mid\gcd(a^{n-1}+b,b^{n-1}+a)=x_{n-1}M∣gcd(an−1+b,bn−1+a)=xn−1 である。