Results 1 to 7 of 7

Math Help - Prime number problem

  1. #1
    Junior Member
    Joined
    Oct 2010
    From
    Zulu-5
    Posts
    60

    Prime number problem

    Hi

    I need direction with the following problem.

    p<>2 is a prime number, suppose the equation x^2=-1(modp) has a solution.
    Show that p=1(mod4).

    SK
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    You could use complex numbers to prove this.

    First note that if p\equiv 3\pmod{4}, then p\in \mathbb{Z}[i] is prime. Now it will suffice to show that if x^2\equiv -1\pmod{p} has a solution, then p\in \mathbb{Z}[i] is not prime. (This will force p\equiv 1\pmod{4}.

    If the equation is satisfied, then there exists an integer m such that pm=x^2+1. We can factor the right hand side to receive pm=(x+i)(x-i). If p were prime, then p|(x+i) or p|(x-i), but this would mean that (1/p)x+(1/p)i\in \mathbb{Z}[i], which is absurd. Therefore, p is not prime.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2010
    From
    Zulu-5
    Posts
    60
    For this class I need to show this without complex numbers. We could use Fermat's litlle theoreme though but I can't see how
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    This can also be done using the Euler criterion. Do you have it?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2010
    From
    Zulu-5
    Posts
    60
    can't use it yet
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    Quote Originally Posted by skyking View Post
    Hi

    I need direction with the following problem.

    p<>2 is a prime number, suppose the equation x^2=-1(modp) has a solution.
    Show that p=1(mod4).

    SK
    Let a be a solution of x^2+1\equiv0(\text{mod}p). Therefor p\nmid a, from Fermat's theorem:

    1\equiv a^{p-1}\equiv(a^2)^{\frac{p-1}{2}}\equiv(-1)^{\frac{p-1}{2}}(\text{mod}p)

    There is impossible that p=4k+3, because if p=4k+3 then:
    (-1)^{\frac{p-1}{2}}=(-1)^{2k+1}=-1, and therefore 1\equiv -1(\text{mod}p), and the conclusion has p|2, which is not true. Hence p is from the form of p=4k+1.

    The end!

    By the way...

    It also true that:

    Let p>2 is a prime number, the equation x^2 \equiv -1(modp) has a solution if and only if p=4k+1
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Nov 2010
    Posts
    1
    In math subject there are many problems occur in numeric theory....This forum is very helpful for students because it solve the problems of math students...Thanks a lot for this help..

    http://fruition.com.au/
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prime number problem
    Posted in the Algebra Forum
    Replies: 6
    Last Post: June 12th 2010, 12:49 PM
  2. [SOLVED] prime number problem
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: November 27th 2009, 04:11 PM
  3. A prime number problem
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: September 28th 2009, 03:13 PM
  4. Prime number problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 12th 2009, 08:34 AM
  5. Prime number problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 1st 2007, 06:28 AM

Search Tags


/mathhelpforum @mathhelpforum