1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)$? $\endgroup$ – Milosz Wielondek Oct 26 '14 at 12:37
  • $\begingroup$ @MiloszWielondek, The answer of the last question is "Yes". $$16x\equiv26\pmod{42}\iff16x=26+42z\iff8x=13+21z$$ where $z$ is some integer $\endgroup$ – lab bhattacharjee Oct 26 '14 at 12:39
  • $\begingroup$ Right, makes sense. Thanks! $\endgroup$ – Milosz Wielondek Oct 26 '14 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.