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

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

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

$pq \mid x^2-1$

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

so

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

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

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

this is two solutions

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

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

can you solve it now

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

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

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

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

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

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

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

7. ok since nobody answered until now

$x \equiv 1 (mod 3)$

$x \equiv 1 (mod 5)$

first let

$x \equiv 0 (mod 3)$
$x \equiv 1 (mod 5)$

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

then let

$x \equiv 1 (mod 3)$
$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

8. second solution

$x \equiv -1 (mod 3)$

$x \equiv 1 (mod 5)$

now let

$x \equiv 0 (mod 3)$
$x \equiv 1 (mod 5)$

it is 6 , 6=1 (mod 5)

then let

$x \equiv -1 (mod 3)$
$x \equiv 0 (mod 5)$

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

now 20+6 = 26
but
$26 \equiv 11 (mod 15)$

so it is 11

third solution

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

let
$x \equiv 0 (mod 3)$
$x \equiv -1 (mod 5)$

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

let

$x \equiv -1 (mod 3)$
$x \equiv 0 (mod 5)$

multiple of 5 and -1 (mod 3)

it is 10

so 10+9 = 19

but

$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

9. Originally Posted by chiph588@
Here are your four solutions, and this is where CRT comes into play

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

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

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

$\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.
Here's how to solve CRT.