关于同余方程的解(1)证明x(x+1)≡-1(mod17)无解(2)证明x(x+1)≡-1(mod59)无解特别是第2个,除了把1,2,3,...,29代入计算还有什么方法?x(x+1)≡-1(mod31)就有解x≡5

Question

关于同余方程的解
(1)证明x(x+1)≡-1(mod17)无解
(2)证明x(x+1)≡-1(mod59)无解
特别是第2个,除了把1,2,3,...,29代入计算还有什么方法?
x(x+1)≡-1(mod31)就有解x≡5

Answer 1

这个要用二次剩余理论, 包括二次互反律.
对质数p, 以及p互质的整数a, 用(a|p)表示Legendre符号:
即当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.
实际上, 述过程可以证明一般结果:
对于质数p > 3, x(x+1) ≡ -1 (mod p)有解当且仅当p ≡ 1 (mod 3).