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}$.
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.
No comments:
Post a Comment