Saturday, June 23, 2018

elementary number theory - Solving linear congruences 12xequiv1pmod77



I am having some repeated trouble getting the correct answer on linear congruences. Consider the following



12x \equiv 1 \pmod {77}




12 and 77 are relatively prime so this congruence has a solution. We search for a linear combination of 12 and 77 using the extended Euclidean algorithm.



77=12(6)+5\\ 12=5(2)+2\\ 5=2(2)+1



We now solve for the remainders



1=5-2(2)\\ 2=12-5(2)\\ 5=77-12(6)



Back substituting we find



1=77(5)+12(-32)



The solution to this congruence is 45 and -32 \equiv 45 (mod 77). What am I failing to do properly as to get the first positive solution?


Answer



Your answer is completely correct. More generally, the solution is 45+77k: k\in \mathbb{Z} as stated above, because

45+77k\equiv 45\mod 77.
If you're concerned about getting the negative answer first, it is simple to just add 77 as you did to find the first positive value.


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