>>642
x²≡a
±x₀, ±x₀+2ⁿ⁻¹
x=2y+1とおくと
x²=4y²+4y+1=1+4y(y+1)
a≡1 mod8
はxが奇数であるための条件である
n=3の時, x≡1, 3, 5, 7の4つ。
±1、±1+2⁽ ³⁻¹⁾。
nの時, ±x₀、±x₀+2ⁿ⁻¹で成り立つと仮定すると
x≡±x₀+2ⁿy、±x₀+2⁽ⁿ⁻¹⁾+2ⁿy
xₙ₊₁≡±x₀, ±x₀+2ⁿとなることを示す
(2ⁿでは消え、2⁽ⁿ⁺¹⁾で残る形)
x²=x₀²、x₀²+2ⁿy₀
x₀²+2⁽ⁿ⁺¹⁾x₀y+2²ⁿy²
=x₀²+2ⁿy(2ⁿy+2x₀)≡a
y=0, 1で解を持つ。
x₀²+2²ⁿ⁻²+2²ⁿy²±2ⁿx₀+2²ⁿy±2ⁿ⁺¹x₀y
≡x₀²±2ⁿx₀
x₀は奇数なので解を持たない。
n≧3の時,
2n-2, 2nはn+1以上である。
よってx≡±x₀、±x₀+2ⁿ m od2ⁿ⁺¹
{±x₀+2⁽ⁿ⁻¹⁾(1+2y)}²
=x₀²±2ⁿx₀(2y+1) mod 2ⁿ⁺¹
±1, ±1+4 mod8
±1+8y、±1+4+8y
≡±1, 9, 7, 5、3、13、11 mod16
±1、9、7だけ。