# Difference between revisions of "Quadratic residues"

m (Moving comment on symbols to talk page) |
|||

Line 10: | Line 10: | ||

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 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. | ||

+ | |||

+ | == Additional properties == | ||

+ | |||

+ | We have for any odd prime <math>p</math> also the following rules: | ||

+ | |||

+ | Multiplicaticity: <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> | ||

+ | |||

+ | First supplementary rule: <math>\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}</math>, so <math>\left(\frac{-1}{p}\right)=1 \iff p \equiv 1 \mod 4</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 usefull 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 == | ||

− | Now suppose that <math>m</math> | + | Now suppose that <math>m</math> is odd, and let <math>m=p_1^{e_1}\cdots p_n^{e_n}</math>. Then we write <math>\left(\frac{a}{m}\right)=\left(\frac{a}{p_1}\right)^{e_1}\cdots\left(\frac{a}{p_n}\right)^{e_n}</math>. 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 <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 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 <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: | ||

+ | <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> |

## Revision as of 06:33, 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

## 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 usefull 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: