Difference between revisions of "Quadratic residues"
m |
Qkrwpwns12 (talk | contribs) m (→Additional properties) |
||
(2 intermediate revisions by 2 users not shown) | |||
Line 16: | Line 16: | ||
Also, we have for any odd prime <math>p</math> the following rules: | Also, we have for any odd prime <math>p</math> the following rules: | ||
− | + | Multiplicativity: <math>\left(\frac{a}{p}\right) \left(\frac{b}{p}\right) = \left(\frac{ab}{p}\right)</math> | |
Euler's criterion: <math>\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \mod p</math> | Euler's criterion: <math>\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \mod p</math> | ||
Line 31: | Line 31: | ||
All properties mentioned above except Euler's criterion are also true for Jacobi symbols with odd (positive) integers <math>p</math> and <math>q</math> instead. | All properties mentioned above except Euler's criterion are also true for Jacobi symbols with odd (positive) integers <math>p</math> and <math>q</math> instead. | ||
− | Note that <math>\left(\frac{a}{m}\right)=1</math> does not mean that <math>a</math> is a quadratic residue <math>\mod m</math> (but is | + | Note that <math>\left(\frac{a}{m}\right)=1</math> does not mean that <math>a</math> is a quadratic residue <math>\mod m</math> (but is necessary for it to be). |
== Calculation and examples == | == Calculation and examples == | ||
Line 60: | Line 60: | ||
In general, to determine whether <math>a</math> is a quadratic residue modulo <math>n</math>, one has to check whether <math>a</math> is a quadratic residue modulo every odd prime <math>p</math> dividing <math>n</math>. This is enough if <math>n</math> is odd or <math>n=2m</math> and <math>m</math> is odd. If <math>n=4m</math> and <math>m</math> is odd, one also has to check that <math>a\equiv 0\mathrm{\ or\ }1\mod 4</math>. Finally, if <math>n</math> is divisible by <math>8</math>, one also has to check that <math>a\equiv 0,1,\mathrm{\ or\ }4\mod 8</math>. | In general, to determine whether <math>a</math> is a quadratic residue modulo <math>n</math>, one has to check whether <math>a</math> is a quadratic residue modulo every odd prime <math>p</math> dividing <math>n</math>. This is enough if <math>n</math> is odd or <math>n=2m</math> and <math>m</math> is odd. If <math>n=4m</math> and <math>m</math> is odd, one also has to check that <math>a\equiv 0\mathrm{\ or\ }1\mod 4</math>. Finally, if <math>n</math> is divisible by <math>8</math>, one also has to check that <math>a\equiv 0,1,\mathrm{\ or\ }4\mod 8</math>. | ||
+ | |||
+ | [[Category:Number theory]] |
Latest revision as of 13:10, 29 November 2017
Let and
be integers, with
. We say that
is a quadratic residue modulo
if there is some integer
so that
is divisible by
.
Contents
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 coprime integers
and
when using the Jacobi symbol defined below.
Additional properties
Also, we have for any odd prime the following rules:
Multiplicativity:
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 necessary 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 example, also gets:
, so
.
, so
.
, so
.
The general case
In general, to determine whether is a quadratic residue modulo
, one has to check whether
is a quadratic residue modulo every odd prime
dividing
. This is enough if
is odd or
and
is odd. If
and
is odd, one also has to check that
. Finally, if
is divisible by
, one also has to check that
.