利用给定提示证明素数n=4k+3下a²+b²≡0(mod n)则a≡b≡0(mod n)

咱们一步步来用题目给的提示完成这个证明，全程不用二次剩余的知识～

已知条件 #

• n 是形如 4k+3 的素数
• 整数 a, b 满足 a² + b² ≡ 0 (mod n)

证明思路：反证法 + 提示应用 #

假设结论不成立，也就是 a ≢ 0 (mod n)（如果假设b≢0也一样，逻辑完全对称），那根据题目给的提示：

若a≢0(mod n)，则存在整数c使得ac ≡ 1 (mod n)

我们先把这个c找出来，接下来对原同余式做变形：

1. 给 a² + b² ≡ 0 (mod n) 两边同时乘以 c²，得到：
   a²c² + b²c² ≡ 0 (mod n)
2. 因为 ac ≡ 1 (mod n)，所以 (ac)² ≡ 1² ≡ 1 (mod n)，代入上式就变成：
   1 + (bc)² ≡ 0 (mod n)
   整理一下就是：(bc)² ≡ -1 (mod n)

利用费马小定理导出矛盾 #

因为 n 是素数，根据费马小定理：对于任何不被n整除的整数x，都有 x^(n-1) ≡ 1 (mod n)。

现在看 (bc) 这个数：如果 bc ≡ 0 (mod n)，那因为 c 和 n 互质（毕竟ac≡1，c的逆元是a），所以b≡0(mod n)，但原式子a² + b²≡0就变成a²≡0，和a≢0矛盾，所以bc ≢ 0 (mod n)，可以用费马小定理。

对 (bc)² ≡ -1 (mod n) 两边同时取 (n-1)/2 次方：

• 左边：[(bc)²]^((n-1)/2) = (bc)^(n-1) ≡ 1 (mod n)（费马小定理直接应用）
• 右边：(-1)^((n-1)/2)，因为n=4k+3，所以(n-1)/2 = 2k+1，是奇数，所以(-1)^(2k+1) = -1

这就得到了 1 ≡ -1 (mod n)，也就是 n | 2，但n是4k+3型素数，最小都是3，不可能整除2，矛盾！

结论 #

所以假设a≢0(mod n)不成立，即a≡0(mod n)，代入原式子a² + b²≡0(mod n)，得到b²≡0(mod n)，因为n是素数，所以b≡0(mod n)。完美得证～

内容的提问来源于stack exchange，提问作者saisanjeev