# Solve congruence: $45x \equiv 15 \pmod{78}$ (What am I doing wrong?)

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?

• 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. – Eric Naslund Jun 13 '11 at 18:15
• 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 :) – Arvin Jun 13 '11 at 22:26

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