# incongruent solutions to (mod n)

• Jun 2nd 2008, 05:38 PM
duggaboy
incongruent solutions to (mod n)
7x = = 3 (mod 15)
take the gcd (7,15) = 1 therefore 1 and 1/3 are 2 incongruent solutions??

6x = = 5 (mod 15)
gcd = 3 but 3 isn't a divisor of 5 therefore there are no solutions??

x^2 = = 1 (mod8) I get 4 and 1 as two incongruent solutions??

I just want to see if my working is accurate...

THANK YOU
• Jun 2nd 2008, 09:46 PM
Moo
Hello,

Quote:

Originally Posted by duggaboy
7x = = 3 (mod 15)
take the gcd (7,15) = 1 therefore 1 and 1/3 are 2 incongruent solutions??

Since gcd(7,15)=1, you can find y such that 7y=1 mod 15. After that, multiply the whole by 3 in order to get x.

Euclidian algorithm, to find y :

15=7x2+1 --> -7x2=1-15=1 mod 15 (remember, i told you you could add as many times as you want 15).

-2 mod 15=-2+15 mod 15=13 mod 15

Therefore, y=13

Multiplying by 3 : x=39=9 mod 15

Quote:

6x = = 5 (mod 15)
gcd = 3 but 3 isn't a divisor of 5 therefore there are no solutions??
(Clapping)

Quote:

x^2 = = 1 (mod8) I get 4 and 1 as two incongruent solutions??
Hmmm what is "incongruent" ?

1²=1 mod 8

whereas 4²=0 mod 8
• Jun 3rd 2008, 04:03 AM
duggaboy
-2 mod 15=-2+15 mod 15=13 mod 15

I don't know where this line came from?

x^2 = = 1 (mod8) I get 4 and 1 as two incongruent solutions??

Should I be setting x = to an actual integer or just giving a generalization?
• Jun 3rd 2008, 09:37 AM
Moo
Quote:

Originally Posted by duggaboy
-2 mod 15=-2+15 mod 15=13 mod 15

I don't know where this line came from?

Remember ? When dealing with mods, you can add as many times 15 as you want.
So you can add 15, it'll just be the same.
By convention, we often write a positive number, inferior to n (here, 15) in the congruence. That's what I did for -2.

Quote:

x^2 = = 1 (mod8) I get 4 and 1 as two incongruent solutions??

Should I be setting x = to an actual integer or just giving a generalization?
You know that every number is either $=0,1,2,3,4,5,6 \ or \ 7 \mod 8$, so you can try them out.
But 1 verify the equation, while 2 and 6 don't

When you find that for example 2 is not a solution, you can say that "any number in the form 2+8k, k in Z, is not solution of the equation"
• Jun 4th 2008, 03:28 PM
duggaboy
Thank You So Much