Page 1 of 2 12 LastLast
Results 1 to 15 of 18

Math Help - Modular solutions question

  1. #1
    Junior Member
    Joined
    Apr 2008
    Posts
    26

    Modular solutions question

    Which of the following equations have a solution?

    (a) x^2 \equiv 17 ( mod 29)

    (b) 3x^2 \equiv 12 ( mod 31)

    (c) 2x^2 \equiv 27 ( mod 41)

    (d) x^2 +5x \equiv 12 ( mod 31)

    Could anyone show me how to solve these step by step? I can't just submit my answers as 'has a solution', 'has no solution.' Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by Proof_of_life View Post
    Which of the following equations have a solution?

    (a) x^2 \equiv 17 ( mod 29)

    (b) 3x^2 \equiv 12 ( mod 31)

    (c) 2x^2 \equiv 27 ( mod 41)

    (d) x^2 +5x \equiv 12 ( mod 31)

    Could anyone show me how to solve these step by step? I can't just submit my answers as 'has a solution', 'has no solution.' Thanks!
    These are problems based on quadratic residues.I hope you are familiar with the legendre symbol. For reference, if p is an odd prime...



    (a) Compute \left(\frac{17}{29}\right)

    (b) Since (31,3) = 1, compute \left(\frac{4}{31}\right)

    (c) 2x^2 \equiv 27 ( mod 41) is same as 2x^2 \equiv -14 ( mod 41). Again we have (2,41) = 1. Therefore compute \left(\frac{34}{41}\right)

    (d)This one is interesting. You have to transform this quadratic congruence to linear by completing the squares and then find the quadratic residue
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,920
    Thanks
    332
    Awards
    1
    Quote Originally Posted by Proof_of_life View Post
    Which of the following equations have a solution?

    (a) x^2 \equiv 17 ( mod 29)

    (b) 3x^2 \equiv 12 ( mod 31)

    (c) 2x^2 \equiv 27 ( mod 41)

    (d) x^2 +5x \equiv 12 ( mod 31)

    Could anyone show me how to solve these step by step? I can't just submit my answers as 'has a solution', 'has no solution.' Thanks!
    There are probably theorems involved there that I don't know, but here goes:
    a) You can get this simply by a listing. No number a modulo 29 has 17 as its square. There is no solution.

    b)
    3x^2 \equiv 12~\text{(mod 31)}

    3x^2 - 12 \equiv~0\text{(mod 31)}

    3(x^2 - 4) \equiv~0\text{(mod 31)}

    x^2 - 4 \equiv~0\text{(mod 31)}

    x^2 \equiv 4 \text{(mod 31)}

    x \equiv 2, 29

    c)
    2x^2 \equiv 27~\text{(mod 41)}

    21 \cdot 2x^2 \equiv 21 \cdot 27~\text{(mod 41)}

    x^2 \equiv 34~\text{(mod 41)}
    and this has no solution.

    d)
    x^2 + 5x \equiv 12~\text{(mod 31)}

    Complete the square:
    x^2 + 5x + 14 \equiv 26~\text{(mod 31)}
    (Just as a note:
    \frac{5}{2} \to 16 \cdot 5 \equiv 18
    So add 18^2 \equiv 14
    to both sides.)

    (x + 13)^2 = 26~\text{(mod 31)}
    and this has no solution for x + 13, so there is no solution for x.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    and this has no solution.
    and this has no solution for x + 13, so there is no solution for x.
    So how do you know for it ?
    Testing for all the congruences ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,920
    Thanks
    332
    Awards
    1
    Quote Originally Posted by Moo View Post
    Hello,





    So how do you know for it ?
    Testing for all the congruences ?
    Yup. I'm taking the "uneducated lout" method and working through the possibilities one by one. I haven't learned how to evaluate Legendre symbols. (And couldn't even remember the name for them until Isomorphism posted it.)

    -Dan
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by topsquark View Post
    Yup. I'm taking the "uneducated lout" method and working through the possibilities one by one. I haven't learned how to evaluate Legendre symbols. (And couldn't even remember the name for them until Isomorphism posted it.)

    -Dan
    I don't know either ~
    But it's quite a tough job to do this way
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Apr 2008
    Posts
    26
    Thanks guys! That helps a lot.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    You can kill these problems with the Golden theorem.
    Quote Originally Posted by Proof_of_life View Post
    (a) x^2 \equiv 17 ( mod 29
    (17/29) = (29/17) = (12/17) = (3/17) = (17/3) = (2/3) = (-1)^{(3^2-1)/8} = -1.

    (b) 3x^2 \equiv 12 ( mod 31)
    First 3^{-1} \equiv 21 so we get x^2 \equiv 4(\bmod 31). That is definitely solvable.

    (c) 2x^2 \equiv 27 ( mod 41)
    Note 2^{-1}\equiv 21 so x^2\equiv -7(\bmod 41).
    (-7/41) = (-1/41)(7/41) = (-1)^{(41-1)/2}(7/41)  = (41/7) = (-1/7) = (-1)^{(7-1)/2} = -1.

    (d) x^2 +5x \equiv 12 ( mod 31)
    5\equiv 36(\bmod 31) thus x^2 + 36x\equiv 12(\bmod 31). Add 324 to both sides to get (x+18)^2\equiv -5(\bmod 31).
    (-5/31) = (-1/31)(5/31) = -(31/5)=-(1/5) = -1
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member flyingsquirrel's Avatar
    Joined
    Apr 2008
    Posts
    802
    Hi

    Quote Originally Posted by topsquark View Post
    c)
    2x^2 \equiv 27~\text{(mod 41)}

    21 \cdot 2x^2 \equiv 21 \cdot 27~\text{(mod 41)}

    x^2 \equiv 34~\text{(mod 41)}
    and this has no solution.
    Shouldn't the second line be 21 \cdot 2x^2 \equiv 21 \cdot 27~\text{(mod} \,41{ \color{red}\cdot 21}\text{)} ?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,920
    Thanks
    332
    Awards
    1
    Quote Originally Posted by Moo View Post
    I don't know either ~
    But it's quite a tough job to do this way
    I have a nice calculator.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,920
    Thanks
    332
    Awards
    1
    Quote Originally Posted by flyingsquirrel View Post
    Hi


    Shouldn't the second line be 21 \cdot 2x^2 \equiv 21 \cdot 27~\text{(mod} \,41{ \color{red}\cdot 21}\text{)} ?
    No. 21 is the multiplicative inverse of 2 a modulo 41, so all I am doing here is "dividing" both sides by 2.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Hi

    Quote Originally Posted by topsquark View Post
    c)
    2x^2 \equiv 27~\text{(mod 41)}

    21 \cdot 2x^2 \equiv 21 \cdot 27~\text{(mod 41)}

    x^2 \equiv 34~\text{(mod 41)}
    and this has no solution.
    Shouldn't the second line be 21 \cdot 2x^2 \equiv 21 \cdot 27~\text{(mod} \,41{ \color{red}\cdot 21}\text{)} ?
    Why? One is allowed to multiply congruences by the same number without changing the modulos of the congruence?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Super Member flyingsquirrel's Avatar
    Joined
    Apr 2008
    Posts
    802
    Quote Originally Posted by topsquark View Post
    No. 21 is the multiplicative inverse of 2 a modulo 41, so all I am doing here is "dividing" both sides by 2.
    OK
    Quote Originally Posted by ThePerfectHacker View Post
    Why? One is allowed to multiply congruences by the same number without changing the modulos of the congruence?
    Yes, that's right that it doesn't change anything as long as one works with implications. I never thought about this and I always multiplied the modulos each time I multiplied the congruences.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by flyingsquirrel View Post
    Yes, that's right that it doesn't change anything as long as one works with implications.
    Hmm... where does it not work?
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Super Member flyingsquirrel's Avatar
    Joined
    Apr 2008
    Posts
    802
    For example : x \equiv 0\,[2] \Rightarrow 2x \equiv 0\,[2] but the other way is wrong : 2x \equiv 0\,[2] \not \Rightarrow x \equiv 0\,[2]

    If we multiply the modulo and the congruence by 2, both ways are correct : x \equiv 0\,[2] \Leftrightarrow 2x \equiv 0\,[4]
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: November 11th 2011, 08:50 PM
  2. Modular arithmetic ; Solutions to 6x = 9 (mod 15)
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: August 20th 2011, 04:05 PM
  3. A question on modular arithmetic
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: November 19th 2010, 04:25 AM
  4. Modular Question
    Posted in the Algebra Forum
    Replies: 3
    Last Post: June 3rd 2009, 09:00 AM
  5. Quick modular solutions question
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 2nd 2008, 11:11 AM

Search Tags


/mathhelpforum @mathhelpforum