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, 07: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, 08:15 PMAmer

$\displaystyle x^2 -1 \equiv 0 (mod pq) $

$\displaystyle pq \mid x^2-1 $

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

so

$\displaystyle p\mid x^2-1 $ and $\displaystyle q\mid x^2-1 $

$\displaystyle x^2 -1 \equiv 0 (mod p) \Rightarrow x^2\equiv 1 (mod p) $

$\displaystyle x \equiv \mp 1 (mod p) $

this is two solutions

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

$\displaystyle x^2-1 \equiv 0 (mod 15) $

can you solve it now - Apr 7th 2010, 08: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, 09:08 PMchiph588@
Here are your four solutions, and this is where CRT comes into play

$\displaystyle \begin{cases} x\equiv1\bmod{3}\\ x\equiv1\bmod{5} \end{cases}$

$\displaystyle \begin{cases} x\equiv-1\bmod{3}\\ x\equiv1\bmod{5} \end{cases}$

$\displaystyle \begin{cases} x\equiv1\bmod{3}\\ x\equiv-1\bmod{5} \end{cases}$

$\displaystyle \begin{cases} x\equiv-1\bmod{3}\\ x\equiv-1\bmod{5} \end{cases}$

So applying CRT to these four systems will give you your solutions. - Apr 7th 2010, 09:10 PMAmer
I made a mistake the correct answer as above sorry

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

- Apr 7th 2010, 11:19 PMAmer
ok since nobody answered until now

$\displaystyle x \equiv 1 (mod 3) $

$\displaystyle x \equiv 1 (mod 5) $

first let

$\displaystyle x \equiv 0 (mod 3) $

$\displaystyle x \equiv 1 (mod 5) $

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

then let

$\displaystyle x \equiv 1 (mod 3) $

$\displaystyle x \equiv 0 (mod 5) $

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 7th 2010, 11:29 PMAmer
second solution

$\displaystyle x \equiv -1 (mod 3) $

$\displaystyle x \equiv 1 (mod 5) $

now let

$\displaystyle x \equiv 0 (mod 3) $

$\displaystyle x \equiv 1 (mod 5) $

it is 6 , 6=1 (mod 5)

then let

$\displaystyle x \equiv -1 (mod 3) $

$\displaystyle x \equiv 0 (mod 5) $

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

now 20+6 = 26

but

$\displaystyle 26 \equiv 11 (mod 15) $

so it is 11

third solution

$\displaystyle x \equiv -1 (mod 3) $

$\displaystyle x \equiv -1 (mod 5) $

let

$\displaystyle x \equiv 0 (mod 3) $

$\displaystyle x \equiv -1 (mod 5) $

multiple of 3 and -1 (mod 5) it is 9

let

$\displaystyle x \equiv -1 (mod 3) $

$\displaystyle x \equiv 0 (mod 5) $

multiple of 5 and -1 (mod 3)

it is 10

so 10+9 = 19

but

$\displaystyle 19 \equiv 14 (mod 15) $

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, 12:37 PMchiph588@