模2q的同余问题：满足am≡b(mod2q)的a是否必为奇数？

咱们可以通过拆解模2q的同余条件来证明这个结论，思路很清晰：

首先，因为q是奇素数，所以2和q互质，根据中国剩余定理，同余式 am ≡ b (mod 2q) 等价于同时满足以下两个同余式：

• am ≡ b (mod 2)
• am ≡ b (mod q)

先看第一个模2的条件：
已知b是奇数，也就是 b ≡ 1 (mod 2)；m是和q互质的奇整数，所以 m ≡ 1 (mod 2)。代入第一个式子得到：
a * 1 ≡ 1 (mod 2)，也就是 a ≡ 1 (mod 2)，这直接说明a必须是奇数——毕竟只有奇数乘奇数才会得到奇数，偶数乘任何数都是偶数，不可能等于奇数b。

再看第二个模q的条件：
因为m和q互质，所以m在模q下存在逆元，也就是说存在整数k使得 m*k ≡ 1 (mod q)，因此 a ≡ b*k (mod q)。不过这个条件只限制了a在模q下的取值，并不会影响a的奇偶性——毕竟第一个条件已经把a的奇偶性锁死为奇数了。

哪怕结合区间[0,2q-1]的限制，满足条件的a只能是奇数，因为区间里的偶数代入第一个同余式都会得到偶数，不可能等于奇数b。

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