# Find all $x \in\mathbb Z$ such that $16x\equiv 26\pmod{42}$

I got stuck with this seemingly easy problem stated below:

Find all $x \in\mathbb Z$ such that $$16x\equiv 26\pmod{42}$$

I tried the following:

$$16x \equiv 26 \pmod{42}\Longleftrightarrow 42 \mid 26 - 16x \\ 42n = 26 - 16x \Longleftrightarrow x = \frac{13}{8} - \frac{21}{8}n \text{ for some } n\in\mathbb Z$$

Now the problem is reduced to finding a $n\in\mathbb Z$ such that $x\in\mathbb Z$.

I'm not sure if I'm on the right path here though, since according to the key the answer should be $x=20+21n$. I can't figure out how they got rid of the coefficient for $x$ and where they got the term $20$ from. (The second term $21n$ obviously comes from dividing $42n$ by $2$).

$$16x\equiv26\pmod{42}$$
Dividing each term by $(16,26,42)=2,$ $$\iff8x\equiv13\pmod{21}\equiv-8$$
As $(21,8)=1,$ $$\iff x\equiv-1\pmod{21}\equiv21-1$$
• Can you explain/prove why dividing each term (including the modulo) is valid in this case? Doesn't seem obvious to me. Also, I suppose by $(x,y)$ you mean gdc$(x,y)$? – Milosz Wielondek Oct 26 '14 at 12:37
• @MiloszWielondek, The answer of the last question is "Yes". $$16x\equiv26\pmod{42}\iff16x=26+42z\iff8x=13+21z$$ where $z$ is some integer – lab bhattacharjee Oct 26 '14 at 12:39