Wednesday, March 6, 2019

elementary number theory - Solving the congruence 7xequiv41mod13




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...