Results 1 to 9 of 9
Like Tree3Thanks
  • 1 Post By Sylvia104
  • 1 Post By Sylvia104
  • 1 Post By Deveno

Math Help - Proof p=1 mod 4 if p|x^2+1

  1. #1
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Proof p=1 mod 4 if p|x^2+1

    Problem statement

    Let n be a whole number of the form n=x^2+1 with x \in Z, and p an odd prime that divides n.
    Proof: p \equiv 1 \pmod 4.


    Attempt at a solution

    The only relevant case is if p=3 (mod 4).

    If I try to calculate mod 3, or mod 4, or mod p, I'm not getting anywhere.

    Help?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Sylvia104's Avatar
    Joined
    Mar 2012
    From
    London, UK
    Posts
    107
    Thanks
    37

    Re: Proof of p=1 mod 4 if p|(x^2+1)

    Use Euler's criterion. p\mid x^2+1 \implies -1 is a quadratic residue \mod p \implies 1=\left(\frac{-1}p\right)=(-1)^{\frac{p-1}2} \implies \frac{p-1}2 is even \implies p\equiv1\mod4.
    Thanks from ILikeSerena
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: Proof of p=1 mod 4 if p|(x^2+1)

    Thanks!
    I was not aware of Euler's criterion yet.
    Now I am!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Apr 2012
    From
    Netherlands
    Posts
    8
    Thanks
    1

    Re: Proof p=1 mod 4 if p|x^2+1

    Sylvia, sorry, I donít get your advice. Whatís Eulerís criterion?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member Sylvia104's Avatar
    Joined
    Mar 2012
    From
    London, UK
    Posts
    107
    Thanks
    37

    Re: Proof of p=1 mod 4 if p|(x^2+1)

    Thanks from TDA120
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: Proof p=1 mod 4 if p|x^2+1

    Quote Originally Posted by TDA120 View Post
    Sylvia, sorry, I donít get your advice. Whatís Eulerís criterion?
    Welcome to MHF, TDA120!

    @Sylvia: Not bad, a response time of 6 minutes!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: Proof p=1 mod 4 if p|x^2+1

    Let me make an attempt to explain in a little more detail.
    (Burn me down if I'm wrong.)

    From Fermat's little theorem we know that a^{p-1} \equiv 1 \pmod p, if p is prime and is not a multiple of p.
    The question becomes, what about a^{p-1 \over 2}, assuming p is odd?

    That would be either -1 or +1.
    And that is basically what Euler's criterion says.
    The notation \left({a \over p}\right) is just a fancy way of writing a^{p-1 \over 2}.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,383
    Thanks
    750

    Re: Proof p=1 mod 4 if p|x^2+1

    here is the way i look at it:

    odd primes come in two flavors, 4n+3 and 4n+1 (since all odd numbers only come in these two flavors).

    saying p|(x2+1) is another way of saying that we have a square root of -1 in Zp.

    so if we can show that if p = 4n + 3 there is no such root, we are done.

    now, since p is prime U(Zp) is a multiplicative group of order p - 1. if p = 4n + 3, then p - 1 = 4n + 2.

    this is not divisible by 4, so in this case, U(Zp) can have no element a of order 4, or else |<a>| = 4 would divide |U(Zp)| = 4n + 2, by Lagrange's theorem.

    note that in Zp[x], x4 - 1 = (x2 + 1)(x2 - 1). since 1 and -1 account for the roots of x2 - 1, we are left with the roots of x2 + 1. but if a2 = -1, then a is of order 4, and we have no such elements.
    Thanks from ILikeSerena
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: Proof p=1 mod 4 if p|x^2+1

    Thanks!

    Actually, I recently got the hint: what is the order of x in Z/pZx?

    When I thought about it (for a long while!), I realized that if p|x2+1, that means that x2=-1 mod p.
    In turn that means that |x|=4 in Z/pZx.

    Since |x| must divide the order of Z/pZx (Lagrange), it follows that 4|p-1.
    Therefore p=1 mod 4.
    Last edited by ILikeSerena; April 23rd 2012 at 02:20 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 15
    Last Post: June 8th 2011, 11:13 AM
  2. Replies: 5
    Last Post: October 19th 2010, 10:50 AM
  3. Replies: 0
    Last Post: June 29th 2010, 08:48 AM
  4. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 10:07 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum