Thread: Chinese 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...

Originally Posted by jzellt

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

p,q are primes that means (p,q)=1

so

and





this is two solutions

same for q you will have two solutions so in total you have four



can you solve it now

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 ?

Originally Posted by jzellt

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 ?

Here are your four solutions, and this is where CRT comes into play









So applying CRT to these four systems will give you your solutions.

I made a mistake the correct answer as above sorry

Can you show how to apply the Chinese Remainder Thm on the first set for me? Thanks.

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

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

Originally Posted by chiph588@

Here are your four solutions, and this is where CRT comes into play









So applying CRT to these four systems will give you your solutions.

Here's how to solve CRT.