Purchase Solution

The Distribution of Quadratic Residues

Not what you're looking for?

Ask Custom Question

Theory of Numbers
The Distribution of Quadratic Residues
Sums of Squares
Sums of Four Squares

1. Let N1(p) denote the number of pairs of integers in [1, p - 1] in which the first is a quadratic residue
and the second is a quadratic nonresidue modulo p. Prove that
N1(p) = (1/4) (p - ( - 1)^((p - 1)/2))

2. Let N2(p) denote the number of pairs of integers in [1, p - 1] in which the first is a quadratic nonresidue
and the second is a quadratic residue modulo p. Prove that
N2(p) = (1/4) (p - 2 + ( - 1)^((p - 1)/2))

3. Let N3(p) denote the number of pairs of integers in [1, p - 1] in which the first is a quadratic nonresidue
and the second is a quadratic nonresidue modulo p. Prove that
N3(p) = (1/4) (p - 2 + ( - 1)^((p - 1)/2))

4. Use the results of theorem 10-4 and corollary 10-1 to construct solutions of x^2 + y^2 =29.

5. Prove ( without assuming corollary 10-1) that, if p is a prime ≡ 1 (mod 4), then there exists positive
integers m, x, and y such that x^2 + y^2 =mp, with p &#9532; x, p &#9532; y, 0 < m < p [ Hint: use the proof of
Theorem 11-2].

Theorem 10-4: If p is an odd prime, then &#957;(p) = (1/8)p + Ep where | Ep| < (1/4)(p)^(1/2) +2.

Corollary 10-1: Every prime p &#8801; 1(mod 4) is representable as a sum of two squares.

Theorem 11-2: For each prime p there exist integers A,B and C, not all zero, such that
A^2 + B^2 + C^2 &#8801; 0 (mod p).

See the attached file.

Attachments
Purchase this Solution
Solution Summary

This solution is comprised of a detailed explanation of the Distribution of Quadratic Residues
and Sums of Four Squares.

It contains step-by-step explanation for the following problem:

1. Let N1(p) denote the number of pairs of integers in [1, p - 1] in which the first is a quadratic residue
and the second is a quadratic nonresidue modulo p. Prove that
N1(p) = (1/4) (p - ( - 1)^((p - 1)/2))

2. Let N2(p) denote the number of pairs of integers in [1, p - 1] in which the first is a quadratic nonresidue
and the second is a quadratic residue modulo p. Prove that
N2(p) = (1/4) (p - 2 + ( - 1)^((p - 1)/2))

3. Let N3(p) denote the number of pairs of integers in [1, p - 1] in which the first is a quadratic nonresidue
and the second is a quadratic nonresidue modulo p. Prove that
N3(p) = (1/4) (p - 2 + ( - 1)^((p - 1)/2))

4. Use the results of theorem 10-4 and corollary 10-1 to construct solutions of x^2 + y^2 =29.

5. Prove ( without assuming corollary 10-1) that, if p is a prime &#8801; 1 (mod 4), then there exists positive
integers m, x, and y such that x^2 + y^2 =mp, with p &#9532; x, p &#9532; y, 0 < m < p [ Hint: use the proof of
Theorem 11-2].

Theorem 10-4: If p is an odd prime, then &#957;(p) = (1/8)p + Ep where | Ep| < (1/4)(p)^(1/2) +2.

Corollary 10-1: Every prime p &#8801; 1(mod 4) is representable as a sum of two squares.

Theorem 11-2: For each prime p there exist integers A,B and C, not all zero, such that
A^2 + B^2 + C^2 &#8801; 0 (mod p).

Solution contains detailed step-by-step explanation.

Solution Preview

Theory of Numbers
The Distribution of Quadratic Residues
Sums of Squares
Sums of Four Squares

1. Let N1(p) denote the number of pairs of integers in [1, p - ...

Solution provided by:
Thokchom Sarojkumar Sinha, MSc
Education
  • BSc, Manipur University
  • MSc, Kanpur University
Recent Feedback
  • "Thanks this really helped."
  • "Sorry for the delay, I was unable to be online during the holiday. The post is very helpful."
  • "Very nice thank you"
  • "Thank you a million!!! Would happen to understand any of the other tensor problems i have posted???"
  • "You are awesome. Thank you"
Purchase this Solution
Free BrainMass Quizzes
Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.

Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

View More Free Quizzes
Related BrainMass Solutions

  • Quadratic residues

    So, the quadratic residues modulo 19 are q=1, 4, 5, 6, 7, 9, 11, 16, 17. This solution is comprised of a detailed explanation to answer what are the quadratic residues modulo 19.

  • Quadratic Residues

    Quadratic residues are investigated. The solution is detailed and well presented. The response received a rating of "5" from the student who posted the question.

  • Pythagorean Triangles

    Then the even powers of g, i.e. g^2,〖 g〗^4,...,g^(p-3),〖 g〗^(p-1)≡1 ("mod" p) are distinct nonzero quadratic residues of p. Since there are ((p-1))⁄2 even powers of g, these are all the nonzero quadratic residues modulo p.

  • Number Theory : Quadratic Residues

    Please see the attached file for the complete solution. Thanks for using BrainMass. Quadratic residues are examined using number theory.

  • Quadratic Congruence and Primitive Roots

    387635 Quadratic Congruence and Primitive Roots 1. If g is a primitive root of p, show that two consecutive powers of g have consecutive least residues.

  • Theory of numbers

    = By the last part of theorem 1 , we get (using Thm 1) Hence by Euler's criterion and definition of quadratic residue, 1009 is quadratic residue modulo 5.

  • Cryptography, congruences, and primes

    Therefore, the solutions for the original equation are in . Problem #57 Proof: Since is an odd prime, then . Then has exactly non-zero quadratic residues. They are .

  • Deciphering the information provided in gene annotations

    In the alignment I used, I chose residues L57, D81, and N113 as examples of three residues that are identical across all of the sequences.

  • Amino acids produced using fixed proportions of nucleotide residues

    see attachment 'Identifying amino acids produced using fixed proportions of nucleotide residues' Identifying amino acids produced using fixed proportions of nucleotide residues Sol: The ratio of proline, serine, leucine and phenylalanine would be

View More Related Solutions