关于同余方程的解(1)证明x(x+1)≡-1(mod17)无解(2)证明x(x+1)≡-1(mod59)无解特别是第2个,除了把1,2,3,...,29代入计算还有什么方法?x(x+1)≡-1(mod31)就有解x≡5
来源:学生作业帮助网 编辑:作业帮 时间:2024/06/20 17:25:54
![关于同余方程的解(1)证明x(x+1)≡-1(mod17)无解(2)证明x(x+1)≡-1(mod59)无解特别是第2个,除了把1,2,3,...,29代入计算还有什么方法?x(x+1)≡-1(mod31)就有解x≡5](/uploads/image/z/11462096-56-6.jpg?t=%E5%85%B3%E4%BA%8E%E5%90%8C%E4%BD%99%E6%96%B9%E7%A8%8B%E7%9A%84%E8%A7%A3%281%29%E8%AF%81%E6%98%8Ex%28x%2B1%29%E2%89%A1-1%28mod17%29%E6%97%A0%E8%A7%A3%282%29%E8%AF%81%E6%98%8Ex%28x%2B1%29%E2%89%A1-1%28mod59%29%E6%97%A0%E8%A7%A3%E7%89%B9%E5%88%AB%E6%98%AF%E7%AC%AC2%E4%B8%AA%2C%E9%99%A4%E4%BA%86%E6%8A%8A1%2C2%2C3%2C...%2C29%E4%BB%A3%E5%85%A5%E8%AE%A1%E7%AE%97%E8%BF%98%E6%9C%89%E4%BB%80%E4%B9%88%E6%96%B9%E6%B3%95%3Fx%28x%2B1%29%E2%89%A1-1%28mod31%29%E5%B0%B1%E6%9C%89%E8%A7%A3x%E2%89%A15)
关于同余方程的解(1)证明x(x+1)≡-1(mod17)无解(2)证明x(x+1)≡-1(mod59)无解特别是第2个,除了把1,2,3,...,29代入计算还有什么方法?x(x+1)≡-1(mod31)就有解x≡5
关于同余方程的解
(1)证明x(x+1)≡-1(mod17)无解
(2)证明x(x+1)≡-1(mod59)无解
特别是第2个,除了把1,2,3,...,29代入计算还有什么方法?
x(x+1)≡-1(mod31)就有解x≡5
关于同余方程的解(1)证明x(x+1)≡-1(mod17)无解(2)证明x(x+1)≡-1(mod59)无解特别是第2个,除了把1,2,3,...,29代入计算还有什么方法?x(x+1)≡-1(mod31)就有解x≡5
这个要用二次剩余理论, 包括二次互反律.
对质数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).