[Math] Solving the congruence $7x \equiv 41 \mod{13}$

diophantine equationselementary-number-theorymodular arithmetic

I have to solve the following linear congruence:

$$7x \equiv 41 \mod{13}$$

The question where I got this from comes in two parts. The first is that it asks to find the set of the inverses of $7 \mod 13$, which turns out to be $[2]_{13}$ but, I found that solution by solving the linear diophantine equation $$7x – 13k – 41$$ which is just the original equation in disguise i.e. $7x \equiv 41 \mod{13}$.

Now, I'm terribly confused as to the solution of the congruence equation. Where am I going wrong and how should I proceed?

Thanks!

EDIT: From @Bill's hint

\begin{align}
7x &\equiv 41 \mod{13} \\
x &\equiv \frac{41}{7} \mod{13} \\
x &\equiv \frac{28}{7} \mod{13} \quad (?) \\
x &\equiv 4 \mod{13} \\
\end{align}

Then, this gives me the solution $[4]_{13}$.

Best Answer

Reduce the congruence to $7x \equiv 2$. Since $\gcd(7,13) = 1$, there exists a unique inverse of $7$ modulo $13$. Note that the inverse is just $2$ since $7 \cdot 2 \equiv 1 \pmod {13}$. Then it follows that $(7)(7^{-1})x \equiv x \equiv 2(7^{-1}) \equiv 4 \pmod {13}$ and that is the solution set.

Related Question