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?
Best Answer
When you divide through by 3, the resulting congruence should be $$15x\equiv 5\pmod{26},$$ not $$15x\equiv 3\pmod{26}.$$