Question about solving congruence. I've worked out how to solve them for the most part except for the following problem I'm having: $$45x \equiv 15 \pmod{78}$$ By the euclidean algorithm, I work out that the gcd of 45 and 78 = 3 which means there exists 3 solutions.

I divide through the congruence by the gcd, 3, to get a new congruence: $$15x \equiv 3 \pmod{26}$$

The gcd of this is 1, which means there exists 1 unique solution. By extended euclidean algorithm I work out that the solution is $21 \pmod{26}$

But now I'm asked to find the solution in terms of the original modulus, mod 78.

In my understanding to do this all you need to do is take the solution of the new congruence, which is 21, and keep adding 26 two more times to get 3 different solutions (which works for other problems I've done), which gets me solutions: 21, 47 and 73 (mod 78) but this is incorrect.

The correct solutions are 9, 35, 61.

What am I doing wrong?

  • 4
    $\begingroup$ This is a huge +1 for showing your work!! This should be the model question of why showing your work is important! If you hadn't, most likely the answers would of explained the process you already know all over again, likely without leading to finding out where you went wrong. $\endgroup$ Jun 13, 2011 at 18:15
  • $\begingroup$ Thanks Eric, I try to put as much information whenever I ask any questions. As I was writing I actually thought it wasn't clear enough and considered changing the whole thing to a more line by line point-form style, haha :) $\endgroup$
    – Arvin
    Jun 13, 2011 at 22:26

2 Answers 2


When you divide through by 3, the resulting congruence should be $$15x\equiv 5\pmod{26},$$ not $$15x\equiv 3\pmod{26}.$$

  • $\begingroup$ Wow, I can't believe it was something so stupid. Thanks! $\endgroup$
    – Arvin
    Jun 13, 2011 at 18:03
  • $\begingroup$ No problem, happens to all of us sometimes :) $\endgroup$ Jun 13, 2011 at 18:04
  • 2
    $\begingroup$ And definitely +1 for showing your work in the question! Not only did it demonstrate you'd put effort into trying to solve it, it made it easier to figure out where you'd gone wrong. $\endgroup$ Jun 13, 2011 at 18:09
  • 2
    $\begingroup$ Thanks =) I try and write my questions in the perspective of the people reading them, makes my life and the people reading's life easier! $\endgroup$
    – Arvin
    Jun 13, 2011 at 18:13

Everything you did is perfectly correct, except one small thing:



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.