Results 1 to 9 of 9

Math Help - Chinese Remainder Thm

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    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...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    Quote Originally Posted by jzellt View Post
    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
    Last edited by Amer; April 7th 2010 at 08:25 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Feb 2008
    Posts
    535
    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 ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by jzellt View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    I made a mistake the correct answer as above sorry
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Feb 2008
    Posts
    535
    Can you show how to apply the Chinese Remainder Thm on the first set for me? Thanks.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    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
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    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
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by chiph588@ View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 10th 2010, 01:24 PM
  2. Chinese remainder theorem
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 20th 2009, 12:57 PM
  3. Chinese remainder theorem 2
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 19th 2009, 10:38 AM
  4. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 23rd 2009, 08:26 PM
  5. chinese remainder
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 29th 2008, 09:20 AM

Search Tags


/mathhelpforum @mathhelpforum