关于同余式$39x+14y \equiv 3\pmod{18}$求解步骤的疑问

咱们一步步把这个问题拆明白，你困惑的点其实是从模6的解扩展到模18的解的逻辑，以及u的取值范围的原因：

1. 模6解的本质 #

你得到的$x - 4v \equiv 1 \pmod{6}$，翻译成整数等式就是：存在任意整数u，使得$x = 1 + 4v + 6u$。这是因为模6同余的定义就是两个数的差是6的整数倍，所以u可以是任何整数，但我们需要的是模18下的不同解（剩余类），所以不需要考虑所有整数u，只需要找出能让x产生不同模18剩余类的u值。

2. 为什么u的取值是${0,1,2}$ #

我们要的是x在模18下的不同剩余类，而6和18的关系是$18 = 6 \times 3$：

• 当u取0时，$6u = 0$，对应x的剩余类是$1+4v \pmod{18}$
• 当u取1时，$6u = 6$，对应x的剩余类是$1+4v+6 \pmod{18}$
• 当u取2时，$6u = 12$，对应x的剩余类是$1+4v+12 \pmod{18}$

这三个剩余类在模18下完全不同。如果u取3，$6 \times 3 = 18 \equiv 0 \pmod{18}$，就和u=0的剩余类重复了；u取4的话$6 \times4=24≡6 \pmod{18}$，和u=1重复。所以u只需要取0、1、2，就能覆盖模18下所有满足条件的x的不同剩余类，没有重复也没有遗漏。

3. 从模6推导到模18的式子 #

把$x = 1 + 4v + 6u$写成同余式形式，就是$x \equiv 1 + 4v + 6u \pmod{18}$（u∈{0,1,2}）。这个式子：

• 完全满足原模6的条件：因为$6u \equiv0 \pmod{6}$，所以$x \equiv1+4v \pmod{6}$，和之前的结论一致；
• 精准给出了模18下的所有解：每一个u对应x在模18下的一个独特剩余类，结合v∈{0,…,5}（覆盖y=3v在模18下的所有可能剩余类），就能得到原同余式的所有解。

举个例子验证：取v=0，那么x的解是$x≡1+6u \pmod{18}$，u=0时x=1，u=1时x=7，u=2时x=13，这三个数代入$x≡1 \pmod{6}$都成立，且在模18下是不同的解，完全符合要求。

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