# Thread: incongruent solutions to (mod n)

1. ## 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

2. Hello,

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

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??
Hmmm what is "incongruent" ?

1²=1 mod 8

whereas 4²=0 mod 8

3. -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?

4. 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.

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"

5. Thank You So Much