Results 1 to 5 of 5

Thread: A proof with primes and quadratic residues

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    15

    A proof with primes and quadratic residues

    Let $\displaystyle q = 4^n + 1 \mbox{ where } n$ is a positive integer. Prove that $\displaystyle q$ is a prime if and only if $\displaystyle 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
    $\displaystyle (3,q)=1 $ since $\displaystyle q \equiv 1 \not\equiv 3 \mod{4} $.

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

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

    By Wilson's Theorem we have $\displaystyle (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 $\displaystyle x $, there exists a unique $\displaystyle y $ such that $\displaystyle xy \equiv 3 \mod{q} $.
    your idea is good but the above conclusion is unfortunately not true at least when $\displaystyle q$ is not prime (choose $\displaystyle x$ to be any divisor of $\displaystyle q$). you probably meant $\displaystyle 3y \equiv 1 \mod q$ has a unique solution

    modulo $\displaystyle 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 $\displaystyle q $ is prime then $\displaystyle \left(\frac{3}{q}\right) \equiv 3^{\frac{q-1}{2}} \mod{q} $ by Euler's Criterion.

    $\displaystyle \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
    $\displaystyle \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: Dec 16th 2011, 02:10 PM
  2. Proof of a subgroup of quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Nov 15th 2011, 12:13 PM
  3. Quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jul 4th 2009, 02:19 PM
  4. Quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Feb 17th 2009, 04:13 PM
  5. quadratic residues
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Sep 13th 2006, 11:34 AM

Search Tags


/mathhelpforum @mathhelpforum