Wednesday, March 6, 2019

elementary number theory - Solving the congruence $7x equiv 41 mod{13}$




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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...