# Solving linear congruences $12x \equiv 1\pmod {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?

• You weren't, technically, asked to find the positive solution If $x$ is a solution, then $x+77k$ is a solution, Not clear what your question is. – Thomas Andrews Dec 7 '15 at 2:13
• Is there a way to solve for the positive solution similar to what I am doing? I am curious why, doing something similar to my compatriots I get a different answer. – RhythmInk Dec 7 '15 at 2:14
• It's not a different answer, modulo $77$. If you were specifically asked to find a positive solution, I suppose you got the wrong answer. – Thomas Andrews Dec 7 '15 at 2:16

## 3 Answers

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.

Your solution is correct. What you have determined is that your solution is an element in the equivalence class of $-32$ mod $77$. Since these are just elements of the form $77k-32$, for $k\in \mathbb {Z}$, we can just let $k=1$ and obtain the smallest positive solution, namely $45$.

Note that typically when we denote the equivalence classes mod $n$, we use the positive numbers $0,1, 2, ..., n-1$. If we added on another $77$, this still gives us a multiple of $77$ but just with a remainder of $45$, and so we can also think of this as the equivalence class of $77k+45$.

You must to find the inverse of 12 in $Z$/77$Z$ and for that you can use Euclid'S algorithm .That is a general way to find the solutions.