# Modulo Arithmetic

• Jan 8th 2009, 04:15 PM
mitch_nufc
Modulo Arithmetic
Consider the following:

-x+2 = 3 (mod 5)
4x = 1 (mod 5)
As the gcd(4,5) = 1 therefore there's one unique solution, namely x = 4 (mod 5)

Also...

-x + 2 = 3 (mod 8)
7x = 1 (mod 8)

Again there is a unique solution, namely x = 1 (mod 8)

Can anyone explain where these solutions come from? I understand how to get to 4x = 1 (mod 5) and 7x = 1 (mod 8) but I dont get how we get the 'unique solutions' at the end? I'd appreciate a clear explanation please. Thank you :)
• Jan 8th 2009, 05:03 PM
HallsofIvy
Quote:

Originally Posted by mitch_nufc
Consider the following:

-x+2 = 3 (mod 5)
4x = 1 (mod 5)
As the gcd(4,5) = 1 therefore there's one unique solution, namely x = 4 (mod 5)

4*4= 16= 1 (mod 5) so any number of the form 5j+ 4 satisfies 4x= 1 (mod 5). -x+ 2= 3 (mod 5) leads to -x= 1 (mod 5) and so x= -1= 4 (mod 5). Any number of the form 5j+ 4 also satisfies this. Of course, to call 4 a "unique" solution you have to call two numbers that are equal "mod 5" the same: 4, 9, 14, 19, etc. all satify those two equations but are the same "mod 5".

Quote:

Also...

-x + 2 = 3 (mod 8)
7x = 1 (mod 8)

Again there is a unique solution, namely x = 1 (mod 8)
No. 7(1)= 7 which is NOT equal to 1 (mod 8). -1+ 2= 1 which is NOT equal to 3 (mod 8). 7*7= 49= 1+ 6(8)= 1 (mod 8) so the any number of the form 7+ 8n satisfies 7x= 1 (mod 8). -x+ 2= 3 (mod 8) leads to -x= 1 (mod 8) so x= -1= 7 (mod 8).

Quote:

Can anyone explain where these solutions come from? I understand how to get to 4x = 1 (mod 5) and 7x = 1 (mod 8) but I dont get how we get the 'unique solutions' at the end? I'd appreciate a clear explanation please. Thank you :)
Are you asking why the solutions are unique? That is not unusual. Typically linear equations have only one solution. What is unusual is that there exist in each case, a number that satisfies both equations. And that is true because the two equations reduce to the same thing.
• Jan 9th 2009, 03:43 AM
mitch_nufc
so are you telling me the solution for the last part is wrong? "x = 1 (mod 8)". its not a solution i got my self its from my lecturers solution manual
• Jan 9th 2009, 03:56 AM
mr fantastic
Quote:

Originally Posted by mitch_nufc
so are you telling me the solution for the last part is wrong? "x = 1 (mod 8)". its not a solution i got my self its from my lecturers solution manual

Yes, that's what HallsofIvy is telling you. And he's correct.

Take a value of x that satisfies the 'solution' x = 1 mod(8). x = 9, say. Does x = 9 satisfy the equation 7x = 1 mod(8) ....? I don't think so.

Now take a value of x that satisfies the solution x = 7 mod(8). x = 7, say. Does x = 7 satisfy the equation 7x = 1 mod(8) ....?