Results 1 to 2 of 2

Thread: 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 $\displaystyle p|(x^2+1)$ for some $\displaystyle x\in \mathbb{Z}$ then $\displaystyle p|(x^4-1)$ since $\displaystyle x^4-1 = (x^2-1)\cdot (x^2+1)$ thus: if $\displaystyle o = \text{ord}_p(x)$ then $\displaystyle o|4$, but $\displaystyle o\not | 2$ since $\displaystyle x^2\equiv{-1}(\bmod.p)$ thus $\displaystyle o=4$.

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

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

    Suppose $\displaystyle p\equiv{1}(\bmod.4)$, then $\displaystyle (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 $\displaystyle (p-1)!\equiv{-1}(\bmod.p)$, and since $\displaystyle p\equiv{1}(\bmod.4)$ we have $\displaystyle (-1)^{\frac{p-1}{2}} = 1$, thus $\displaystyle \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 $\displaystyle x^2\equiv{-1}(\bmod.p)$ follows easily from the fact that if you have $\displaystyle x^2\equiv{y^2}(\bmod.p)$ then either $\displaystyle x\equiv_p y$ or $\displaystyle 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: Oct 10th 2010, 11:28 AM
  2. Prove(10)
    Posted in the Trigonometry Forum
    Replies: 5
    Last Post: Feb 26th 2010, 04:16 AM
  3. Replies: 2
    Last Post: Aug 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: Oct 25th 2008, 12:15 AM
  5. Prove:
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Oct 24th 2008, 11:45 PM

Search Tags


/mathhelpforum @mathhelpforum