2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Thomas Andrews Dec 7 '15 at 2:13
  • $\begingroup$ 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. $\endgroup$ – Aaron Zolotor Dec 7 '15 at 2:14
  • 2
    $\begingroup$ 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. $\endgroup$ – Thomas Andrews Dec 7 '15 at 2:16
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.