关于求解二次同余式$x^2\equiv x\pmod{1000}$及三位数自再生数的两处疑问

嘿，我来帮你把这两个疑问拆解清楚，一步步来：

疑问1：为什么一开始用$n^2 \equiv n \pmod{1000}$？ #

核心原因和自再生数的定义+三位数的位数直接相关：

• 自再生数要求$n$的十进制数字出现在$n^2$的末尾，且顺序完全一致；
• 我们要找的是三位数（$100 < n < 999$），这意味着$n$本身就是一个三位数字，所以$n^2$的最后三位必须和$n$完全相等。
• 数学上，“$n^{2$的最后三位等于$n$”等价于$n}2 - n$能被1000整除，也就是$n^2 \equiv n \pmod{1000}$。这就是1000的由来——它是$10^3$，对应三位数的位数，用来保证末尾三位的一致性。

疑问2：怎么得到$n \equiv 0,1 \pmod{8}$和$n \equiv 0,1 \pmod{125}$的解？ #

我们可以把两个同余式分别拆解分析：

对于$n^2 \equiv n \pmod{8}$ #

先把同余式变形：
$$n^2 - n \equiv 0 \pmod{8} \implies n(n-1) \equiv 0 \pmod{8}$$
这里有个关键观察：$n$和$n-1$是连续整数，它们一定互质（相邻两个数的最大公约数是1）。
因为互质的两个数不可能共享任何素因子，所以8（即$2^3$）必须完整地整除其中一个数：

• 如果8整除$n$，那么$n \equiv 0 \pmod{8}$；
• 如果8整除$n-1$，那么$n \equiv 1 \pmod{8}$。
  你可以验证其他余数（比如$n\equiv2\pmod{8}$时，$2\times1=2$，无法被8整除），只有0和1满足条件。

对于$n^2 \equiv n \pmod{125}$ #

同样先变形：
$$n^2 - n \equiv 0 \pmod{125} \implies n(n-1) \equiv 0 \pmod{125}$$
还是利用“$n$和$n-1$互质”的结论：
125（即$5^3$）是一个素数的三次方，它必须完整地整除$n$或者$n-1$，因为互质的两个数不可能同时有因子5：

• 如果125整除$n$，那么$n \equiv 0 \pmod{125}$；
• 如果125整除$n-1$，那么$n \equiv 1 \pmod{125}$。
  同样，其他余数代入都无法让$n(n-1)$被125整除，所以只有这两个解。

补充：后续筛选的逻辑 #

我们列出100到999之间满足$n\equiv0$或$1\pmod{125}$的数：125、126、250、251、375、376、500、501、625、626、750、751、875、876。
再从这些数里筛选出满足$n\equiv0$或$1\pmod{8}$的：

• 376：$376\div8=47$，即$376\equiv0\pmod{8}$，满足；
• 625：$625-1=624$，$624\div8=78$，即$625\equiv1\pmod{8}$，满足。
  这两个就是我们要找的三位数自再生数。

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