這個要用二次剩余理論, 包括二次互反律.
對質(zhì)數(shù)p, 以及p互質(zhì)的整數(shù)a, 用(a|p)表示Legendre符號:
即當(dāng)x² ≡ a (mod p)有解時, (a|p) = 1, 無解時(a|p) = -1.
(1) x(x+1) ≡ -1 (mod 17)等價于(2x+1)² = 4x(x+1)+1 ≡ -3 (mod 17).
只需要說明-3不是mod 17的二次剩余即可, 即(-3|17) = -1.
由17 ≡ 1 (mod 4), 可知(-1|17) = 1.
而(-3|17) = (-1|17)·(3|17), 于是只需說明(3|17) = -1.
這里由二次互反律, (3|17)·(17|3) = (-1)^((3-1)(17-1)/4) = 1,
得(3|17) = (17|3) = (2|3) = -1.
(2) x(x+1) ≡ -1 (mod 59)等價于(2x+1)² = 4x(x+1)+1 ≡ -3 (mod 59).
由59 ≡ 3 (mod 4), 可知(-1|59) = -1.
又由二次互反律, (3|59)·(59|3) = (-1)^((3-1)(59-1)/4) = -1.
故(3|59) = -(59|3) = -(2|3) = 1.
因此(-3|59) = (-1|59)·(3|59) = -1.
-3不是mod 59的二次剩余, 方程無解.
至于x(x+1) ≡ -1 (mod 31)有解, 可同樣化為證明(-3|31) = 1.
類似上面過程有(-1|31) = -1, (3|31) = -(31|3) = -(1|3) = -1, 因此(-3|31) = (-1|31)·(3|31) = 1.
實(shí)際上, 述過程可以證明一般結(jié)果:
對于質(zhì)數(shù)p > 3, x(x+1) ≡ -1 (mod p)有解當(dāng)且僅當(dāng)p ≡ 1 (mod 3).