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

109 Views Asked by At

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$).

1

There are 1 best solutions below

3
On BEST ANSWER

$$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$$