Solving $9x \equiv 21 \bmod 30$
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!
$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}}$.