Difference between revisions of "Quadratic residues"
Qkrwpwns12 (talk | contribs) m (→Additional properties) |
|||
(7 intermediate revisions by 7 users not shown) | |||
Line 1: | Line 1: | ||
− | Let <math>a</math> and <math>m</math> be [[integer]]s, with <math>m\neq 0</math>. We say that <math>a</math> is a '''quadratic residue''' [[modulo]] <math>m</math> if there is some integer | + | Let <math>a</math> and <math>m</math> be [[integer]]s, with <math>m\neq 0</math>. We say that <math>a</math> is a '''quadratic residue''' [[modulo]] <math>m</math> if there is some integer <math>n</math> so that <math>n^2-a</math> is [[divisibility | divisible]] by <math>m</math>. |
== Legendre Symbol == | == Legendre Symbol == | ||
Line 9: | Line 9: | ||
== Quadratic Reciprocity == | == Quadratic Reciprocity == | ||
− | Let <math>p</math> and <math>q</math> be distinct odd primes. Then <math>\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}</math>. This is known as the [[Quadratic Reciprocity Theorem]]. | + | Let <math>p</math> and <math>q</math> be distinct [[odd integer | odd]] primes. Then <math>\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}</math>. This is known as the [[Quadratic Reciprocity Theorem]]. |
− | Whereas the above are properties of the Legendre symbol, they still hold for any odd integers <math>p</math> and <math>q</math> when using the Jacobi symbol defined below. | + | Whereas the above are properties of the Legendre symbol, they still hold for any odd coprime integers <math>p</math> and <math>q</math> when using the Jacobi symbol defined below. |
== Additional properties == | == Additional properties == | ||
− | + | 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 == | ||
− | With the rules and properties already mentioned it's eays to calculate Jacobi symbols. Since they are for primes <math>p</math> identical to the Legendre symbol, this gives a fast way to decide if an integer is a quadratic residue <math>\mod p</math> or not. | + | With the rules and properties already mentioned, it's eays to calculate Jacobi symbols. Since they are for primes <math>p</math> identical to the Legendre symbol, this gives a fast way to decide if an integer is a quadratic residue <math>\mod p</math> or not. |
Example: | Example: | ||
Line 49: | Line 49: | ||
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> | 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 example also gets: | + | In a more general manner, one, 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{-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>. | ||
Line 59: | Line 59: | ||
== The general case == | == The general case == | ||
− | 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. | + | 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 12: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 .