Difference between revisions of "Quadratic residues"
Line 24: | Line 24: | ||
Second supplementary rule: <math>\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}</math>, so <math>\left(\frac{2}{p}\right)=1 \iff p \equiv \pm 1 \mod 8</math> | Second supplementary rule: <math>\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}</math>, so <math>\left(\frac{2}{p}\right)=1 \iff p \equiv \pm 1 \mod 8</math> | ||
− | It's also | + | It's also useful not to forget that the symbols are only properties <math>\mod p</math>, so <math>a \equiv b \mod p \implies \left(\frac{a}{p}\right)=\left(\frac{b}{p}\right) </math> |
== Jacobi Symbol == | == Jacobi Symbol == | ||
Line 38: | Line 38: | ||
Example: | Example: | ||
− | <math>\left(\frac{12345}{13337}\right) = \left(\frac{13337}{12345}\right) = \left(\frac{992}{12345}\right) = \left(\frac{2^5}{12345}\right)\left(\frac{31}{12345}\right)=\left(\frac{2}{12345}\right)^5 \left(\frac{12345}{31}\right) = 1^5 \left(\frac{7}{31}\right) = -\left(\frac{31}{7}\right) = -\left(\frac{3}{7}\right) = \left(\frac{7}{3}\right) = \left(\frac{1}{3}\right)=1</math> | + | |
− | Thus we know that <math>12345</math> is a quadratic residue modulo the prime <math>13337</math>. Indeed: <math>2425^2 \equiv 12345 \mod 13337</math> | + | <math>\left(\frac{12345}{13337}\right) =</math> |
+ | |||
+ | <math>=\left(\frac{13337}{12345}\right) = \left(\frac{992}{12345}\right) = \left(\frac{2^5}{12345}\right)\left(\frac{31}{12345}\right)=\left(\frac{2}{12345}\right)^5 \left(\frac{12345}{31}\right)=</math> | ||
+ | |||
+ | <math>= 1^5 \left(\frac{7}{31}\right) = -\left(\frac{31}{7}\right) = -\left(\frac{3}{7}\right) = \left(\frac{7}{3}\right) = \left(\frac{1}{3}\right)=</math> | ||
+ | |||
+ | <math>=1</math> | ||
+ | |||
+ | Thus we know that <math>12345</math> is a quadratic residue [[modulo]] the prime <math>13337</math>. Indeed: <math>2425^2 \equiv 12345 \mod 13337</math> | ||
+ | |||
+ | In a more general manner, one for for example also gets: | ||
+ | |||
+ | <math>\left(\frac{-2}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{2}{p}\right) = (-1)^{\frac{(p-2)^2-1}{8}}</math>, so <math>\left(\frac{-2}{p}\right)=1 \iff p \equiv 1,3 \mod 8</math>. | ||
+ | |||
+ | <math>\left(\frac{3}{p}\right) = (-1)^{\frac{p-1}{2}} \left(\frac{p}{3}\right)</math>, so <math>\left(\frac{3}{p}\right)=1 \iff p \equiv \pm 1 \mod 12</math>. | ||
+ | |||
+ | <math>\left(\frac{-3}{p}\right) = \left(\frac{p}{3}\right)</math>, so <math>\left(\frac{-3}{p}\right)=1 \iff p \equiv 1 \mod 3</math>. |
Revision as of 06:49, 27 June 2006
Let and
be integers, with
. We say that
is a quadratic residue modulo
if there is some number
so that
is divisible by
.
Contents
[hide]Legendre Symbol
Determining whether is a quadratic residue modulo
is easiest if
is a prime. In this case we write
The symbol is called the Legendre symbol.
Quadratic Reciprocity
Let and
be distinct odd primes. Then
. This is known as the Quadratic Reciprocity Theorem.
Whereas the above are properties of the Legendre symbol, they still hold for any odd integers
and
when using the Jacobi symbol defined below.
Additional properties
We have for any odd prime also the following rules:
Multiplicaticity:
Euler's criterion:
First supplementary rule: , so
Second supplementary rule: , so
It's also useful not to forget that the symbols are only properties , so
Jacobi Symbol
Now suppose that is odd, and let
. Then we write
. This symbol is called the Jacobi symbol.
All properties mentioned above except Euler's criterion are also true for Jacobi symbols with odd (positive) integers
and
instead.
Note that does not mean that
is a quadratic residue
(but is necassary for it to be).
Calculation and examples
With the rules and properties already mentioned it's eays to calculate Jacobi symbols. Since they are for primes identical to the Legendre symbol, this gives a fast way to decide if an integer is a quadratic residue
or not.
Example:
Thus we know that is a quadratic residue modulo the prime
. Indeed:
In a more general manner, one for for example also gets:
, so
.
, so
.
, so
.