Results 1 to 7 of 7

Math Help - Congruence Equations

  1. #1
    Member
    Joined
    Sep 2012
    From
    U.K.
    Posts
    88

    Congruence Equations

    Let p be a prime and k a positive integer.



    (a) Show that if x is an integer such that x^2=x mod p, then x= 0 or 1 mod p.


    (b) Show that if x is an integer such that x^2=x mod p^k, then x= 0 or 1 mod p^k.


    (c) Show that if p is odd and x is an integer such that x^2=1 mod p^k, then x= +/- 1 mod p^k.


    (d) Find the solutions of the congruence equation x^2=1 mod 2^k.


    Have looked at this for ages and can't get anywhere - any help would be much appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,615
    Thanks
    1582
    Awards
    1

    Re: Congruence Equations

    Quote Originally Posted by kinhew93 View Post
    Let p be a prime and k a positive integer.
    (a) Show that if x is an integer such that x^2=x mod p, then x= 0 or 1 mod p.
    Do you plan to show any of your efforts?

    If ${x^2} \equiv x\left( {\bmod \,p} \right)$ then $x^2=kp+x$ Is that correct?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2012
    From
    U.K.
    Posts
    88

    Re: Congruence Equations

    Quote Originally Posted by Plato View Post
    Do you plan to show any of your efforts?
    http://mathhelpforum.com/newreply.ph...reply&p=812447
    If ${x^2} \equiv x\left( {\bmod \,p} \right)$ then $x^2=kp+x$ Is that correct?
    Yeah that's right

    My attempts are non existent, I really have no idea what to do
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,615
    Thanks
    1582
    Awards
    1

    Re: Congruence Equations

    Quote Originally Posted by kinhew93 View Post
    Yeah that's right. My attempts are non existent, I really have no idea what to do
    So $x^2-x-kp=0$ Correct? Or $x=\dfrac{1\pm\sqrt{1+4kp}}{2}$

    How would that be possible if $x$ is an integer ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Sep 2012
    From
    U.K.
    Posts
    88

    Re: Congruence Equations

    Quote Originally Posted by Plato View Post
    So $x^2-x-kp=0$ Correct? Or $x=\dfrac{1\pm\sqrt{1+4kp}}{2}$

    How would that be possible if $x$ is an integer ?
    ]

    So this can only happen when 4kp= 0 which gives x = 0 and 1.

    How do you then get to 0 modp and 1 modp?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,386
    Thanks
    752

    Re: Congruence Equations

    Not it is NOT true that it can "only happen when 4kp = 0". For example suppose p = 3. We could take k = 2, so that 4kp = 24, and then 1 + 4kp = 25, which is a perfect odd square, so we get x = 3 (which is 0 mod 3) or x = -2 (which is 1 mod 3).

    Here is what I would do:

    The integers mod p form a field, so we can form the polynomial:

    x2 - x in the polynomial ring Zp[x].

    Since Zp is a field, we know it has no more than 2 roots in Zp.

    Now:

    x2 - x = 0 (mod p)

    is the same as:

    x(x - 1) = 0 (mod p)

    which makes it evident that the only integers in Zp that are solutions are 0 (mod p) and 1 (mod p).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    634
    Thanks
    256

    Re: Congruence Equations

    Hi,
    You need to know a few facts from elementary number theory. The attachments explicitly state these facts; you can prove them for yourself, look up the proofs or as a last resort ask me. Also shown are solutions to the first 3 problems. I give you the answer to number 4, but I've left the proof to you. If you have trouble, post again and I'll try and help.

    Congruence Equations-mhfnumbertheory8a.png

    Congruence Equations-mhfnumbertheory8b.png
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruence equations
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 11th 2013, 05:06 PM
  2. Congruence Equations
    Posted in the Number Theory Forum
    Replies: 12
    Last Post: October 15th 2011, 01:54 AM
  3. Prime numbers and congruence equations.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 21st 2010, 11:54 PM
  4. solving congruence equations
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 9th 2009, 02:17 PM
  5. Congruence Equations
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 15th 2006, 07:02 PM

Search Tags


/mathhelpforum @mathhelpforum