关于模680下$x^2 \equiv 1$的解计数中负数解选择性取舍的疑问

原问题与初始解答 #

问：$x^2 \equiv 1 \pmod{680}$有多少个解？

根据中国剩余定理，我们可以将模数分解为$680 = 8 \times 5 \times 17$，分别求解每个小模数下的同余式，再通过组合得到总解数：

• $x^2 \equiv 1 \pmod{8}$的解为：$1, 3, 5, 7$
• $x^2 \equiv 1 \pmod{5}$的解为：$1, -1$
• $x^2 \equiv 1 \pmod{17}$的解为：$1, -1$

总解数为各模数解数的乘积：$4 \times 2 \times 2 = 16$个。

疑问点 #

为什么在模8的情况下我们没算$-1, -3, -5, -7$这些负数解，而模5和模17的时候却把$\pm1$都算进去了？

解答 #

其实这里的核心是模运算里的等价类概念——我们计数的是不同的剩余类，不是单纯的整数。两个整数如果模n同余，就属于同一个解，没必要重复计数。

咱们拆开来看：

• 模8的情况：你可以算一下，$-1 \equiv 7 \pmod{8}$，$-3 \equiv 5 \pmod{8}$，$-5 \equiv 3 \pmod{8}$，$-7 \equiv 1 \pmod{8}$。这些所谓的“负数解”其实和我们已经列出来的1、3、5、7完全是同一个等价类，根本没新增不同的解，所以重复列出来毫无意义。
• 模5的情况：$-1 \equiv 4 \pmod{5}$，这个数和1在模5下不同余，是一个全新的剩余类，所以必须算进去；模17同理，$-1 \equiv 16 \pmod{17}$，和1不同余，是另一个独立的解，自然要计入总数。

总结一下：模8时负数解和正数解是重复的等价类，所以不用额外加；模5、17时负数解是独立的新等价类，所以必须算进去才能得到完整的解数。

备注：内容来源于stack exchange，提问作者FriedSpies