Results 1 to 5 of 5

Math Help - A proof with primes and quadratic residues

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    15

    A proof with primes and quadratic residues

    Let q = 4^n + 1 \mbox{ where } n is a positive integer. Prove that q is a prime if and only if 3^{\frac{q-1}{2}} \equiv -1 \mbox{ (mod q)}.

    I have no clue on how to start.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
     (3,q)=1 since  q \equiv 1 \not\equiv 3 \mod{4} .

    Therefore for a fixed  x , there exists a unique  y such that  xy \equiv 3 \mod{q} .

    Hence if we partition  \{1,...,q-1\} into  \{c,d\} such that  cd \equiv 3 \mod{q} , we get  (q-1)! \equiv 3^{\frac{q-1}{2}} \mod{q} .

    By Wilson's Theorem we have  (q-1)! \equiv -1 \mod{q} \Longleftrightarrow q is prime.

    I'm not exactly sure this is right so if someone wants to confirm this, that would be great.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by chiph588@ View Post

    Therefore for a fixed  x , there exists a unique  y such that  xy \equiv 3 \mod{q} .
    your idea is good but the above conclusion is unfortunately not true at least when q is not prime (choose x to be any divisor of q). you probably meant 3y \equiv 1 \mod q has a unique solution

    modulo q, which is correct but not very useful here.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Well one way is easy. If  q is prime then  \left(\frac{3}{q}\right) \equiv 3^{\frac{q-1}{2}} \mod{q} by Euler's Criterion.

     \left(\frac{3}{q}\right) = \left(\frac{3}{4^n+1}\right) = \left(\frac{4^n+1}{3}\right) = \left(\frac{1^n+1}{3}\right) = \left(\frac{2}{3}\right) = -1 .
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2009
    Posts
    15
    Thank you so much. By the way, how did you get from
    \left(\frac{4^n+1}{3}\right) = \left(\frac{1^n+1}{3}\right) ?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Primes that are quadratic residues another prime.
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: December 16th 2011, 03:10 PM
  2. Proof of a subgroup of quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 15th 2011, 01:13 PM
  3. Quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 4th 2009, 03:19 PM
  4. Quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 17th 2009, 05:13 PM
  5. quadratic residues
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: September 13th 2006, 12:34 PM

Search Tags


/mathhelpforum @mathhelpforum