How do I solve this linear congruence?

38 Views Asked by At

$2x \equiv 5 \pmod 9$

Is my way on how to do it correct?

$9 = 4\cdot 2 + 1$. Thus $1 = 9 - 4\cdot 2$. Now I multiply by 5.

$$\begin{align} 5 &= 45 - 20\cdot 2 \\ -20\cdot 2 &\equiv 5 \pmod 9 \\ 7\cdot 2 &\equiv 5 \pmod 9 \end{align}$$

so $x = 7$.

So that is my way of tackling the problem. Can you tell me if my way is correct or not? And if it is correct, can you explain why my procedure worked? I just copied the textbook's example (but with different numbers) but they do not explain anything at all, so I am kind of lost. Thank you.

1

There are 1 best solutions below

0
On BEST ANSWER

Your way is absolutely correct.

Essentially, modulo $9$, if you have a number $x$ from the options $\{1,2,4,5,7,8\}$, then you can always find two numbers $a$ and $b$ such that $1 = 9a + xb$. You took $x = 2$ and found $a = 1$ and $b = -4$. If you can create 1 from 9 and $x$, then of course you can create any other number, and your method works.

Do you notice something special about the numbers $\{1,2,4,5,7,8\}$? As a hint, have you learned about the 'greatest common divisor' or 'Euclid's algorithm'? If not, that would be a good place to start learning more about modular arithmetic. Eventually you will learn about 'inverses' in modular arithmetic, which means you can magically 'divide' both sides of $2x \equiv 5$ by 2 to get $x \equiv 5\cdot 2^{-1} \equiv 7$. Any good number theory textbook (e.g. David Burton's "Elementary Number Theory") will have this.