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