Let p and q be two odd primes. Show that x^2 - 1 = 0 mod pq has four solutions. Find four solutions modulo 15. (Hint: use the Chinese Remainder Thm and Lagrange's Thm)
The above = is congrence, not equality.
How do I show this? Thanks...
Let p and q be two odd primes. Show that x^2 - 1 = 0 mod pq has four solutions. Find four solutions modulo 15. (Hint: use the Chinese Remainder Thm and Lagrange's Thm)
The above = is congrence, not equality.
How do I show this? Thanks...
So, I would re-write it as x^2 - 1 = 3*5 (= is congruence)
3*5 | x^2 -1
So,
3 | x^2 -1 and 5 | x^2 - 1
x^2 - 1 = 0 (mod 3) -> x^2 = 1 (mod 3)
x = +-1 (mod 3) So two solutions are +-1 for mod 3.
Now I do the same for 5 to get two solutions: +-1 for mod 5.
So what are my FOUR solutions since I got +-1 for both mod3 and mod5 ?
second solution
now let
it is 6 , 6=1 (mod 5)
then let
want a multiple of 5 and equal -1 (mod 3) it is 20
now 20+6 = 26
but
so it is 11
third solution
let
multiple of 3 and -1 (mod 5) it is 9
let
multiple of 5 and -1 (mod 3)
it is 10
so 10+9 = 19
but
so it is 14
note first solution is 16 and it equal to 1 (mod 15)
the solutions are
1,4,11,14