$\begingroup$

Solving $9x \equiv 21 \bmod 30$

My approach:
Finding $gcd(9,30)$:\begin{align} 30 &= 9 \cdot 3 + 3 \\ 9 &= 3 \cdot 3 + 0 \end{align}

So $gcd(9,30)=3$ and since $3 \mid 21$ so the congruence has $3$ incongruent solutions. Express $3$ as a linear combination of $9$ and $30$, we get: $$3 = 30-9 \cdot 3 \ \ \ \ \ \ (1)$$

We have to solve this equation to find $x_0$:$$9x-30y=21 \ \ \ \ \ \ (2)$$

Multiplying $(1)$ by $7$ we get:$$21=30 \cdot7-9 \cdot 21$$

Rewritten in form of $(2)$:$$-9 \cdot (21) + 30 \cdot (7) = 21 $$

So $x_0=21$, the incongruent solutions are:$$21 + 10n, \ \ \ \ \ n = 0,1,2$$

Then $x=21,31,41$. But my answer is wrong, the answer is: $x=9,19,29$. Can you tell me which step is wrong. Thanks for your help!

$\endgroup$ 7

3 Answers

$\begingroup$

$9x\equiv 21\pmod{30}$ means $9x=30k+21$ or $3x=10k+7$ or $3x\equiv 7\pmod{10}$ or $21x\equiv 49\pmod{10}$ or $\color{red}{x\equiv 9\pmod{10}}$.

$\endgroup$ 1 $\begingroup$

$$9x-30y=21$$to$$21=30 \cdot7-9 \cdot 21$$

is the issue, you reverse the terms, so you should get $x \equiv -21 \equiv 9 \pmod {30}$

In other words, when you are solving the initial equation, you are solving it for a positive x less than 30, but you got a negative value.

$\endgroup$ 1 $\begingroup$

if $9x = 21 + 30 t,$ we see that $3x = 7 + 10 t,$ the reverse also holding. Solve$$ 3x \equiv 7 \pmod {10} $$for which you need a reciprocal of $3.$ Since $21 \equiv 1 \pmod {10} $ we see that$$ \frac{1}{3} \equiv 7 \pmod {10} , $$

and.......

$\endgroup$ 2

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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