将 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。