まず、以下を示す。
命題※
xを整数、pを素数、s,tを正の整数とする。
このとき、x^(p^s・t)-x^(p^{s-1}・t)はp^sで割り切れる。
証明
x^(p^s・t)-x^(p^{s-1}・t)=x^(p^{s-1}・t){(x^{(p-1)p^(s-1)})^t-1}

xがpで割り切れるとき
p^(s-1)・t≧2^(s-1)≧sだから、x^(p^{s-1}・t)がp^sで割り切れる。

xがpで割り切れないとき
フェルマー・オイラーの定理より
{x^{(p-1)p^(s-1)}^t-1≡1^t-1≡0 (mod p^s)だからx^{(p-1)p^(s-1)})^t-1
がp^sで割り切れる。

以上より命題※は示された。□