Saturday, June 23, 2018

elementary number theory - Solving linear congruences $12x equiv 1pmod {77}$



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