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 :
where is an integer and a prime number (further symbolism is described in the article Congruence ).
If is not a multiple of , the result can be expressed in the frequently used form
because then the multiplicative inverse modulo exists.
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.
See: Proofs of Fermat's small theorem in the evidence archive
Conclusion by Euler
The 3rd binomial formula says:
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 .
It is therefore true
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
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.
Use as a prime number test
According to Fermat's little theorem, for every prime and every relatively prime number :
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% .
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 )
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.
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
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 .
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.
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.
n | ||||||
---|---|---|---|---|---|---|
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 .
In this example , the values for the following cycle result
- 1, 2, 4, 1 , 2, 4, 1 , 2, ...
For results
- 1, 3, 2, 6, 4, 5, 1 , 3, ...
The number 7 applies to all three bases 2, 3 and 5
- for all
or in general
for all and all natural a , for which holds . This is a direct consequence of Fermat's Little Theorem.
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.
Further simplification
If this is the form , further simplifications of the calculation result. This is illustrated here using the example .
n | 1 | 2 | 4th | 8th | 16 | 32 |
---|---|---|---|---|---|---|
2 | 4th | 16 | 1 | 1 | 1 | |
3 | 9 | 13 | 16 | 1 | 1 | |
5 | 8th | 13 | 16 | 1 | 1 | |
7th | 15th | 4th | 16 | 1 | 1 | |
11 | 2 | 4th | 16 | 1 | 1 | |
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
- ,
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
- 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 .