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

Printable View

- Apr 7th 2010, 08:59 PMjzelltChinese Remainder Thm
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... - Apr 7th 2010, 09:15 PMAmer
- Apr 7th 2010, 09:48 PMjzellt
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 ? - Apr 7th 2010, 10:08 PMchiph588@
- Apr 7th 2010, 10:10 PMAmer
I made a mistake the correct answer as above sorry

- Apr 7th 2010, 10:34 PMjzellt
Can you show how to apply the Chinese Remainder Thm on the first set for me? Thanks.

- Apr 8th 2010, 12:19 AMAmer
ok since nobody answered until now

first let

want a multiple of 3 and equal 1 (mod 5) it is 6

then let

want a multiple of 5 and equal 1 (mod 3) it is 10

now 6+10 =16 ,

16 = 1 (mod 3)

16 = 1 (mod 5)

first solution - Apr 8th 2010, 12:29 AMAmer
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 - Apr 8th 2010, 01:37 PMchiph588@