Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
4  
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

2 Answers 2

up vote 7 down vote accepted

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

share|improve this answer
    
Wow, I can't believe it was something so stupid. Thanks! –  Arvin Jun 13 '11 at 18:03
    
No problem, happens to all of us sometimes :) –  Zev Chonoles Jun 13 '11 at 18:04
2  
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. –  Zev Chonoles Jun 13 '11 at 18:09
2  
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! –  Arvin Jun 13 '11 at 18:13

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

$$15/3=5.$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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