Results 1 to 2 of 2

Math Help - Prove that.....

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    34

    Prove that.....

    Let p be an odd prime. Prove that the congruence x2 is congruent to -1 mod p has no solutions for p is congruent to 3 mod 4 and exactly two solutions when p is congruent to 1 mod 4. [Hint: Think of orders.]
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Suppose p|(x^2+1) for some x\in \mathbb{Z} then p|(x^4-1) since x^4-1 = (x^2-1)\cdot (x^2+1) thus: if o = \text{ord}_p(x) then o|4, but o\not | 2 since x^2\equiv{-1}(\bmod.p) thus o=4.

    By Fermat's Little Theorem: x^{p-1}\equiv{1}(\bmod.p) and hence o|(p-1) i.e. p\equiv{1}(\bmod.4).

    So there can be no solutions when p\equiv{3}(\bmod.4).

    Suppose p\equiv{1}(\bmod.4), then (p-1)!=(p-1)...\cdot \left(p - \frac{p-1}{2}\right)\cdot \left(\frac{p-1}{2}\right) ... 1 \equiv{(-1)^{\frac{p-1}{2}}\left(\left(\tfrac{p-1}{2}\right) ... 1\right)^2}(\bmod.p)

    Now, by Wilson's Theorem (p-1)!\equiv{-1}(\bmod.p), and since p\equiv{1}(\bmod.4) we have (-1)^{\frac{p-1}{2}} = 1, thus \left(\left(\tfrac{p-1}{2}\right) ... 1\right)^2\equiv{-1}(\bmod.p) and a solution exists.

    The fact that there are exactly 2 solutions to x^2\equiv{-1}(\bmod.p) follows easily from the fact that if you have x^2\equiv{y^2}(\bmod.p) then either x\equiv_p y or x\equiv_p -y

    - I suppose you have not gone over quadratics residues, just as a comment this will get much more generalised when you get there.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove
    Posted in the Calculus Forum
    Replies: 4
    Last Post: October 10th 2010, 11:28 AM
  2. Prove(10)
    Posted in the Trigonometry Forum
    Replies: 5
    Last Post: February 26th 2010, 04:16 AM
  3. Replies: 2
    Last Post: August 28th 2009, 02:59 AM
  4. How do I prove b^x * b^y = b ^ x + y on R?
    Posted in the Calculus Forum
    Replies: 2
    Last Post: October 25th 2008, 12:15 AM
  5. Prove:
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 24th 2008, 11:45 PM

Search Tags


/mathhelpforum @mathhelpforum