Results 1 to 2 of 2
Like Tree2Thanks
  • 2 Post By Petek

Math Help - Quadratic Residues of Primes

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    United States
    Posts
    14

    Exclamation Quadratic Residues of Primes

    Use induction to show that, for all n, there exists a set of n distinct odd primes {p1,...,pn} such that every prime in the list is a quadratic residue modulo anyother prime in the list.

    I'm confused as to how we can construct the pk+1 prime such that it is a quadratic residue for {p1,...,pn} and that {p1,...,pn} are quadratic residues of pk+1. Any help solving this problem would be appreciated. Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Nov 2010
    Posts
    58
    Thanks
    18

    Re: Quadratic Residues of Primes

    Here's a sketch of a solution:

    Assume that the set of primes {p_1, p_2, \dots, p_k} satisfies the conditions of the problem. It suffices to find a prime p_{k+1} \equiv 1 \pmod{4} such that p_{k+1} is a quadratic residue mod p_i for i=1, \dots, p_k. That's because the law of quadratic reciprocity implies that each p_i is then a quadratic residue mod p_{k+1}.

    Consider the set of congruences

     \\x \equiv 1 \pmod{p_1} \\x \equiv 1 \pmod{p_2} \\. \\. \\.\\x \equiv 1 \pmod{p_k} \\x \equiv 1 \pmod{4}

    Any solution is a quadratic residue mod p_i for all i=1, 2, \dots, k. By the Chinese Remainder Theorem, a solution x_0 exists and all solutions are of the form x_0 + rm, where r \in \mathbb{Z} and m=4p_1p_2\cdots p_k. By Dirichlet's theorem, this arithmetic progression contains a prime p_{k+1} \equiv 1 \pmod{4}, as required.
    Thanks from clintonh0610 and johng
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 12th 2012, 02:01 AM
  2. Primes that are quadratic residues another prime.
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: December 16th 2011, 03:10 PM
  3. A proof with primes and quadratic residues
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: November 16th 2009, 07:55 PM
  4. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: July 23rd 2009, 12:25 PM
  5. Quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 4th 2009, 03:19 PM

Search Tags


/mathhelpforum @mathhelpforum