n=p−xn=p-xn=p−x とおく。0<x<p0<x<p0<x<p より nnn は正の整数である。x≥p+h2x\ge\frac{p+h}2x≥2p+h より n=p−x≤p−p+h2=p−h2n=p-x\le p-\frac{p+h}2=\frac{p-h}2n=p−x≤p−2p+h=2p−h となり、これはステップ1で必要な上界である。さらに n≡−x(modp)n\equiv-x\pmod pn≡−x(modp) なので n2≡x2≡−1(modp)n^2\equiv x^2\equiv-1\pmod pn2≡x2≡−1(modp)、すなわち p∣n2+1p\mid n^2+1p∣n2+1 である。