Quadratic reciprocity

The quadratic reciprocity law gives, together with the two below mentioned supplementary sets, a method to to calculate the Legendre symbol, and thus to decide whether a number is a quadratic residue or a quadratic non-residue. The discovery of the quadratic reciprocity law by Euler and the proof by Gauss were the point of the development of modern number theory. Although there are elementary proofs of the reciprocity law, the real reason of the reciprocity law is hidden in the prime factorization in the body of the nth roots of unity.

The quadratic reciprocity law states that for two distinct odd primes p and q is true:

1 Extension Set: For any odd prime p:

2 Extension Set: For any odd prime p:

Calculation rules

Let p and q be two different odd primes, then:

Namely, since the following

Examples

• One would like to determine if the equation

Has a solution. To this end, we calculate

The first factor can be determined to -1 by the second supplementary rate. To calculate a second factor which is used in the reciprocity law:

Here equal sign was used at the second that. Analogously, in the penultimate equality sign.

If we now both factors together, we obtain

And thus we know that the above equation has a solution. ( The two resolutions are 6 and 7 )

• One would like to determine if the equation

Has a solution. For this purpose, we calculate again

And can simplify the above two factors with the reciprocity law continues:

And

Putting everything together, we obtain

And thus the recognition that the above equation has no solution.

Efficient computation of the Legendre symbol

The method shown here calculation method has the disadvantage of having to determine the prime factorization of the numerator of the Legendre symbol. There is a more efficient process that runs similar to the Euclidean algorithm and requires no prime factorization. Here is the Jacobi symbol is a generalization of the Legendre symbol, used for the quadratic reciprocity law is still valid.