Little Fermatsch sentence

The little Fermat's theorem , or “the little Fermat ” for short , is a theorem of number theory . It makes a statement about the properties of prime numbers and was established by Pierre de Fermat in the 17th century . The sentence describes the generally valid congruence :

${\displaystyle a^{p}\equiv a{\pmod {p}},}$

where is an integer and a prime number (further symbolism is described in the article Congruence ). ${\displaystyle a}$ ${\displaystyle p}$

If is not a multiple of , the result can be expressed in the frequently used form ${\displaystyle a}$ ${\displaystyle p}$

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$

because then the multiplicative inverse modulo exists. ${\displaystyle a^{-1}}$ ${\displaystyle p}$

proof

The theorem can be proven with induction or as a special case of Lagrange's theorem from group theory . This says that every group element raised to the power of the (finite) group order results in the one element. ${\displaystyle a}$

See: Proofs of Fermat's small theorem in the evidence archive

Conclusion by Euler

The 3rd binomial formula says:

${\displaystyle (a^{\frac {p-1}{2}}-1)\cdot (a^{\frac {p-1}{2}}+1)=a^{p-1}-1}$

Now be an odd prime number and any whole number. If is not a divisor of , it follows from Fermat's Little Theorem that the right-hand side of the equation is a multiple of the prime number . So one of the factors is a multiple of . ${\displaystyle p}$ ${\displaystyle a}$ ${\displaystyle p}$ ${\displaystyle a}$ ${\displaystyle p}$ ${\displaystyle p}$

It is therefore true

${\displaystyle a^{\frac {p-1}{2}}\equiv \pm 1{\pmod {p}}}$

This conclusion is attributed to Leonhard Euler .

generalization

One can generalize Fermat's little theorem to Euler's theorem.

For two coprime numbers and applies ${\displaystyle n}$ ${\displaystyle a}$

${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}},}$

where denotes the Euler φ function . This provides the number of numbers between and which are coprime . If is a prime number, then is , so that Fermat's little theorem is obtained as a special case. ${\displaystyle \varphi (n)}$ ${\displaystyle 1}$ ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \varphi (n)=n-1}$

Use as a prime number test

According to Fermat's little theorem, for every prime and every relatively prime number : ${\displaystyle p}$ ${\displaystyle a}$

${\displaystyle \left(a^{\frac {p-1}{2}}-1\right)\cdot \left(a^{\frac {p-1}{2}}+1\right)=a^{p-1}-1=k\cdot p}$

with an integer . This relationship can also apply to a composite number and a number with . However, this is very rare , at least for large numbers . If you find numbers with this property for a composite number , this can be used to factorize the number , since the factors on the left then yield real divisors of with a probability of 50% . ${\displaystyle k}$ ${\displaystyle p}$ ${\displaystyle a}$ ${\displaystyle 1<a<p}$ ${\displaystyle p}$ ${\displaystyle a}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$

For a number with 100 or more digits, however, prime factorization is only possible with more efficient methods such as the square sieve . The theorem can therefore also be used in its reverse to judge with high reliability whether a number is a prime number. In the case of large numbers with over 100 digits, there is practically no doubt that is a prime number if the equation holds for a with . (see: Fermatsch primality test ) ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle a}$ ${\displaystyle 1<a<p}$

For an exact proof, however, it would be necessary to check all values , so that the trial division is more efficient in this case. It is not known that a 100-digit or greater number could be factored this way. ${\displaystyle 1<a<p-1}$

For some specific numbers, however, such exceptions can be found more often.

Shor algorithm

Let it be the product of two large prime numbers and . We consider a number with . We know that for the exponent ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle x}$ ${\displaystyle 1<x<n}$ ${\displaystyle r=\varphi (n)=(p-1)\cdot (q-1)}$

${\displaystyle x^{r}\equiv 1{\pmod {n}}}$

applies.

The question arises whether this equation is already true for smaller exponents. The quantum part of the Shor algorithm for factoring large numbers is used to calculate the smallest number for which this equation applies. The classic part of this algorithm can easily be performed on almost any computer . ${\displaystyle r}$

If you look at the powers of a number with respect to the modulo operation, these are repeated in cycles. This is inevitable as only the values can be accepted. We consider this using the example of smaller numbers. ${\displaystyle 1,2,3,\ldots ,n-1}$

We can restrict ourselves to the consideration of prime numbers, since the minimum cycle length for the product results from the smallest common multiple of the cycle lengths for the factors.

Example with p = 7

n	${\displaystyle 2^{n}}$	${\displaystyle 2^{n}{\pmod {7}}}$	${\displaystyle 3^{n}}$	${\displaystyle 3^{n}{\pmod {7}}}$	${\displaystyle 5^{n}}$	${\displaystyle 5^{n}{\pmod {7}}}$
0	1	1	1	1	1	1
1	2	2	3	3	5	5
2	4th	4th	9	2	25th	4th
3	8th	1	27	6th	125	6th
4th	16	2	81	4th	625	2
5	32	4th	243	5	3125	3
6th	64	1	729	1	15625	1
7th	128	2	2187	3	78125	5

and so on. In the table was calculated from . In order to avoid larger numbers, the result can be calculated more simply from . ${\displaystyle a^{n}{\pmod {p}}}$ ${\displaystyle a^{n}}$ ${\displaystyle a\cdot (a^{n-1}{\pmod {p}})}$

In this example , the values for the following cycle result ${\displaystyle p=7}$ ${\displaystyle a=2}$ ${\displaystyle a^{n}{\pmod {p}}}$

• 1, 2, 4, 1 , 2, 4, 1 , 2, ...

For results ${\displaystyle a=3}$

• 1, 3, 2, 6, 4, 5, 1 , 3, ...

The number 7 applies to all three bases 2, 3 and 5

${\displaystyle a^{(7-1)\cdot c}\equiv 1\ {\pmod {7}}}$ for all ${\displaystyle c\geq 1}$

or in general

${\displaystyle a^{(p-1)\cdot c}\equiv 1\ {\pmod {p}}}$

for all and all natural a , for which holds . This is a direct consequence of Fermat's Little Theorem. ${\displaystyle c\geq 1}$ ${\displaystyle 1<a<p}$

The example of the modulo values ​​for shows that the algorithm can be shortened if the cycle is shorter. There is also , d. H. . This saves work for larger numbers. ${\displaystyle a=2}$ ${\displaystyle 2^{3}\equiv 1{\pmod {7}}}$ ${\displaystyle 2^{3*2}\equiv 1{\pmod {7}}}$ ${\displaystyle 2^{7-1}\equiv 1{\pmod {7}}}$

Further simplification

If this is the form , further simplifications of the calculation result. This is illustrated here using the example . ${\displaystyle p}$ ${\displaystyle 2^{n}+1}$ ${\displaystyle p=17}$

Example with p = 17

n	1	2	4th	8th	16	32
${\displaystyle 2^{n}{\pmod {17}}}$	2	4th	16	1	1	1
${\displaystyle 3^{n}{\pmod {17}}}$	3	9	13	16	1	1
${\displaystyle 5^{n}{\pmod {17}}}$	5	8th	13	16	1	1
${\displaystyle 7^{n}{\pmod {17}}}$	7th	15th	4th	16	1	1
${\displaystyle 11^{n}{\pmod {17}}}$	11	2	4th	16	1	1
${\displaystyle 13^{n}{\pmod {17}}}$	13	16	1	1	1	1

Since it is a multiple of the cycle length, only the numbers come into consideration, which can significantly reduce the computational effort, especially for very large ones. The case makes even less work ${\displaystyle p-1=2^{4}}$ ${\displaystyle r}$ ${\displaystyle 2,4,8,16}$ ${\displaystyle p}$

${\displaystyle x^{r}\equiv 16\equiv -1{\pmod {17}}}$,

since the result is then already fixed as 1 for the next power of 2.

literature

• Gunter Saake, Kai-Uwe Sattler: Algorithms and data structures . 4th edition. P. 657

Web links

Wikibooks: Proof of Fermat's little theorem  - learning and teaching materials

• Eric W. Weisstein : Fermat's Little Theorem . In: MathWorld (English).
• Fermat's Little Theorem on Cut-the-Knot
• Video: Fermat's Little Theorem . University of Education Heidelberg (PHHD) 2012, made available by the Technical Information Library (TIB), doi : 10.5446 / 19892 .