On odd integers mod $2q$

Question

Take an odd prime $q$.

Take an odd integer $m$ with $\gcd(m, q) = 1$.

Consider $a$ in $[0, 2q - 1]$ with $am \equiv b \bmod 2q$ where $b$ is odd.

Is $a$ always odd?

Answer 1

Yes, it is, and this has nothing to do with $m$ being coprime with $q$, nor with the range of $a$: we have $$am=b+2kq\quad\text{for some }k\in\mathbf Z$$ so, reducing mod. $2$, we obtain $$a\cdot 1=a\equiv 1 \mod 2.$$

Answer 2

Think it out:

Let $m= 2k+1$

Let $b = 2j+1$

$am \equiv b \mod 2q$ means

$am = b + z*2q$ for some integer $z$.

$a(2k + 1) = 2j + 1 + 2zq$

$a = 2j + 1 + 2zq - 2ak = 2(j+2zq - ak) + 1$.

That ... is always odd.

Note: we did not have to assume $q$ was prime or that $m$ and $q$ where co-prime.