Fermat's Little Theorem

Fermat’s small theorem is a number theory theorem that states that ^[1] :

If a $p$ ${\ displaystyle p}$ $p$ Is a prime number and $a$ ${\ displaystyle a}$ $a$ - integer not divisible by $p,$ ${\ displaystyle p,}$ $p$ then $a^{p-1}-1$ ${\ displaystyle a ^ {p-1} -1}$ $a ^ {p-1} -1$ divided by $p .$ ${\ displaystyle p.}$ $p.$

In the language of comparison theory : $a^{p-1}$ ${\ displaystyle a ^ {p-1}}$ $a ^ {p-1}$ comparable to 1 modulo simple $p$ ${\ displaystyle p}$ $p$ . Formal Record: $a^{p-1}\equiv 1{\pmod {p}}$ ${\ displaystyle a ^ {p-1} \ equiv 1 {\ pmod {p}}}$ $a ^ {p-1} \ equiv 1 {\ pmod {p}}$

For example, if $a=2;p=7,$ ${\ displaystyle a = 2; p = 7,}$ $a = 2; p = 7,$ then $2^{6}=64,$ ${\ displaystyle 2 ^ {6} = 64,}$ $2 ^ {6} = 64,$ and $64-1=63=7\cdot 9.$ ${\ displaystyle 64-1 = 63 = 7 \ cdot 9.}$ $64-1 = 63 = 7 \ cdot 9.$

Fermat’s small theorem is a special case of Euler’s theorem ^[2] , which, in turn, is a special case of Carmichael ’s theorem and Lagrange’s theorem for groups for finite cyclic groups . Pierre Fermat stated the theorem without proof, the first proof was given by Leonard Euler and Gottfried Wilhelm Leibniz .

Fermat's small theorem has become one of the main theorems for research not only in the theory of integers, but also in wider areas ^[3] ^[4] .

Content

History

Pierre Farm

Pierre Fermat formulated the initial statement of the theorem by 1640 . “I was illuminated with a bright light,” wrote Fermat, first reporting this discovery in his letter (1640) ^[5] . Interestingly, this phrase - “mi par di veder un gran lume” ^{[6] is} written in Italian, although the whole letter is in French.

The letter of October 18, 1640 by Pierre Fermat to the French mathematician Bernard Frenickl contained the following provision ^[7] :

Each prime number divides [in the original - “measures”] one of the degrees of any progression minus 1, for which the exponent is a divisor of this prime number minus 1; and after the first degree has been found that satisfies this property, all numbers having exponents that are multiples of the first exponent satisfy the same property.
Original text (Fr.)
Tout nombre premier mesure infailliblement une des puissances −1 de quelque progression que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre premier donné −1; et, après qu'on a trouvé la première puissance qui satisfait à la question, toutes celles dont les exposants sont multiples de l'exposant de la première satisfont tout de même à la question.

As an example, Fermat gives a progression of 3, 9, 27, 81, 243, 729 ... and a prime number 13. 13 divides 27 - 1 (the exponent for 27 is 3, and 3 divides 13 - 1), which implies that 13 also divides 729 - 1 (exponent for 729 is 6 and a multiple of 3).

Fermat himself left his theorem without proof. The first mathematician to find evidence was Gottfried Wilhelm Leibniz, from the manuscripts of which it follows that he knew the proof until 1683. Leibniz did not know about Fermat's result and discovered the theorem independently ^[8] . However, Leibniz's work was not published, and Euler published the proof in 1736 in the article Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio ^[9] . The proof of Fermat’s small theorem, based on the fact that if $x$ ${\ displaystyle x}$ runs through the complete system of deductions modulo $p$ ${\ displaystyle p}$ then for any $a:(a,p)=1$ ${\ displaystyle a: (a, p) = 1}$ composition $a x$ ${\ displaystyle ax}$ also runs through the complete modulus deduction system $p$ ${\ displaystyle p}$ , was published in 1806 by James Ivory ^[10] .

Number ${\frac {a^{p-1}-1}{p}}$ ${\ displaystyle {\ frac {a ^ {p-1} -1} {p}}}$ called Private Farm . Russian mathematician D. A. Grave suggested that the private Fermat is never divided by $p .$ ${\ displaystyle p.}$ For primes not exceeding 1000, this is true, but a counterexample was soon discovered: for $p=1093,a=2$ ${\ displaystyle p = 1093, a = 2}$ The private farm is divided into 1093 ^[11] .

Alternative wording

The following wording is distinguished by the absence of a requirement that the number $a$ ${\ displaystyle a}$ not divided into $p$ ${\ displaystyle p}$ :

If a $p$ ${\ displaystyle p}$ Is a prime number and $a$ ${\ displaystyle a}$ Is any integer then $a^{p}$ ${\ displaystyle a ^ {p}}$ comparable to $a$ ${\ displaystyle a}$ modulo $p$ ${\ displaystyle p}$ , i.e $a^{p}\equiv a{\pmod {p}}$ ${\ displaystyle a ^ {p} \ equiv a {\ pmod {p}}}$ .

For example, if $a=7;p=5$ ${\ displaystyle a = 7; p = 5}$ then $7^{5}=16807=5\cdot 3361+2,$ ${\ displaystyle 7 ^ {5} = 16807 = 5 \ cdot 3361 + 2,}$ and $7=5\cdot 1+2.$ ${\ displaystyle 7 = 5 \ cdot 1 + 2.}$ .

It is easy to show that this formulation is reduced to the original. So if $a$ ${\ displaystyle a}$ divided by $p$ ${\ displaystyle p}$ then $a\equiv 0{\pmod {p}}$ ${\ displaystyle a \ equiv 0 {\ pmod {p}}}$ and $a^{p}\equiv 0{\pmod {p}}$ ${\ displaystyle a ^ {p} \ equiv 0 {\ pmod {p}}}$ , i.e. $a^{p}\equiv a{\pmod {p}}$ ${\ displaystyle a ^ {p} \ equiv a {\ pmod {p}}}$ . If $a$ ${\ displaystyle a}$ not divided by $p$ ${\ displaystyle p}$ then the expression $a^{p}\equiv a{\pmod {p}}$ ${\ displaystyle a ^ {p} \ equiv a {\ pmod {p}}}$ equivalent to the expression $a^{p-1}\equiv 1{\pmod {p}}$ ${\ displaystyle a ^ {p-1} \ equiv 1 {\ pmod {p}}}$ ^[2] .

Evidence

Proof of the theorem proposed by Leibniz

Consider a homogeneous polynomial of degree p with n variables:

S(x,y,z,\dots ,w)=(x+y+z+\dots +w)^{p}-(x^{p}+y^{p}+z^{p}+\dots +w^{p}).

{\ displaystyle S (x, y, z, \ dots, w) = (x + y + z + \ dots + w) ^ {p} - (x ^ {p} + y ^ {p} + z ^ {p } + \ dots + w ^ {p}).}

Opening the brackets, we obtain the coefficient of the monomial $Mx^{\alpha }y^{\beta }z^{\gamma }\cdot \ldots \cdot w^{\nu }$ ${\ displaystyle Mx ^ {\ alpha} y ^ {\ beta} z ^ {\ gamma} \ cdot \ ldots \ cdot w ^ {\ nu}}$ (where at least two of the degrees $\alpha ,\beta ,\gamma \ldots \nu$ ${\ displaystyle \ alpha, \ beta, \ gamma \ ldots \ nu}$ are not equal to zero, and the sum of all degrees is equal to p ) is called a multinomial coefficient and is calculated by the formula

M={\frac {p!}{\alpha !\beta !\gamma !\dots \nu !}}.

{\ displaystyle M = {\ frac {p!} {\ alpha! \ beta! \ gamma! \ dots \ nu!}}.}

Since degrees $\alpha ,\beta ,\gamma ...$ ${\ displaystyle \ alpha, \ beta, \ gamma ...}$ less than $p,$ ${\ displaystyle p,}$ then the denominator of the multinomial coefficient does not contain factors that could be reduced by $p,$ ${\ displaystyle p,}$ therefore, all coefficients of the polynomial $S$ ${\ displaystyle S}$ multiple $p .$ ${\ displaystyle p.}$ Thus, the following identity is true:

(x+y+z+\dots +w)^{p}-(x^{p}+y^{p}+z^{p}+\dots +w^{p})=pH(x,y,z,\dots ,w),

{\ displaystyle (x + y + z + \ dots + w) ^ {p} - (x ^ {p} + y ^ {p} + z ^ {p} + \ dots + w ^ {p}) = pH ( x, y, z, \ dots, w),}

Where $H(x,y,z,...,w)$ ${\ displaystyle H (x, y, z, ..., w)}$ Is a polynomial with positive integer coefficients.

Let now in this identity $x=y=...=w=1,H(1,1,1,...,1)=N,$ ${\ displaystyle x = y = ... = w = 1, H (1,1,1, ..., 1) = N,}$ then $n^{p}-n=Np$ ${\ displaystyle n ^ {p} -n = Np}$ (here n is the number of variables in the original polynomial expression), therefore, $n(n^{p-1}-1)$ ${\ displaystyle n (n ^ {p-1} -1)}$ multiple $p$ ${\ displaystyle p}$ . If a $n$ ${\ displaystyle n}$ not divisible by prime $p,$ ${\ displaystyle p,}$ it is divided into $n^{p-1}-1$ ${\ displaystyle n ^ {p-1} -1}$ ^[12] .

Induction proof

Let us prove that for any prime p and a non-negative integer a , a ^p - a is divisible by p . We prove by induction on a .

Base. For a = 0 , a ^p - a = 0 and is divided by p .

Transition. Let the statement be true for a = k . We prove it for a = k + 1 .

a^{p}-a=(k+1)^{p}-(k+1)=k^{p}+1+\sum _{l=1}^{p-1}{p \choose l}k^{l}-k-1=k^{p}-k+\sum _{l=1}^{p-1}k^{l}{p \choose l}

{\ displaystyle a ^ {p} -a = (k + 1) ^ {p} - (k + 1) = k ^ {p} +1+ \ sum _ {l = 1} ^ {p-1} { p \ choose l} k ^ {l} -k-1 = k ^ {p} -k + \ sum _ {l = 1} ^ {p-1} k ^ {l} {p \ choose l}}

But k ^p - k is divisible by p by the induction hypothesis. The remaining terms contain a factor ${p \choose l}={p! \over l!(p-l)!}$ ${\ displaystyle {p \ choose l} = {p!$ $\ over l! (pl)!}}$ . For $1\leqslant l\leqslant p-1$ ${\ displaystyle 1 \ leqslant l \ leqslant p-1}$ , the numerator of this fraction is divided by p , and the denominator is coprime with p , therefore, ${p \choose l}$ ${\ displaystyle {p \ choose l}}$ divided by p . Since all the individual terms are divided by p , the whole sum $k^{p}-k+\sum _{l=1}^{p-1}k^{l}{p \choose l}$ ${\ displaystyle k ^ {p} -k + \ sum _ {l = 1} ^ {p-1} k ^ {l} {p \ choose l}}$ also divided by p .

For negative a and odd p, the theorem can easily be proved by substituting b = - a . For negative a and p = 2, the truth of the theorem follows from a ² - a = a ( a - 1) ^[13] .

Group theory proof

One of the simplest proofs of Fermat’s Little Theorem is based on a corollary of the Lagrange theorem from group theory , which states that the order of an element of a finite group divides the order of the group.

Recall that the order of a finite group $G$ ${\ displaystyle G}$ called the number of its elements, and the order of the element $g\in G$ ${\ displaystyle g \ in G}$ - the smallest natural indicator of its degree equal to a single element $e$ ${\ displaystyle e}$ groups $G$ ${\ displaystyle G}$ .

Let be $G$ ${\ displaystyle G}$ - finite group of order $n$ ${\ displaystyle n}$ . From the order of the element $g\in G$ ${\ displaystyle g \ in G}$ divides $n$ ${\ displaystyle n}$ , follows that $g^{n}=e$ ${\ displaystyle g ^ {n} = e}$ .

Consider the field $\mathbb {Z} _{p}$ ${\ displaystyle \ mathbb {Z} _ {p}}$ deductions modulo $p$ ${\ displaystyle p}$ . Integer deduction $a$ ${\ displaystyle a}$ will be denoted by $a$ ${\ displaystyle a}$ . Nonzero field elements $\mathbb {Z} _{p}$ ${\ displaystyle \ mathbb {Z} _ {p}}$ form a group with respect to multiplication.

The order of this group is obviously equal $p-1$ ${\ displaystyle p-1}$ . Its single element is $one$ ${\ displaystyle 1}$ . It follows that for each number $a$ ${\ displaystyle a}$ not divisible by $p$ ${\ displaystyle p}$ , $a^{p-1}=1$ ${\ displaystyle a ^ {p-1} = 1}$ but that just means comparison $a^{p-1}\equiv 1{\pmod {p}}$ ${\ displaystyle a ^ {p-1} \ equiv 1 {\ pmod {p}}}$ ^[one]

Elementary proof

Lemma. For any prime $p$ ${\ displaystyle p}$ and integer $k$ ${\ displaystyle k}$ not multiple $p$ ${\ displaystyle p}$ , works $k$ ${\ displaystyle k}$ and numbers $1,2,3,\ldots ,p-1$ ${\ displaystyle 1,2,3, \ ldots, p-1}$ when dividing modulo by $p$ ${\ displaystyle p}$ in the remainder give the same numbers $1,2,3,\ldots ,p-1,$ ${\ displaystyle 1,2,3, \ ldots, p-1,}$ perhaps recorded in some other order.

Proof of the lemma

Composition $k$ ${\ displaystyle k}$ and any of the numbers $1,2,3,\ldots ,p-1$ ${\ displaystyle 1,2,3, \ ldots, p-1}$ not multiple $p$ ${\ displaystyle p}$ therefore, the balance cannot be obtained $0$ ${\ displaystyle 0}$ . All residues are different. Let us prove the last statement by contradiction. Let two works $a k$ ${\ displaystyle ak}$ and $b k$ ${\ displaystyle bk}$ give when divided by $p$ ${\ displaystyle p}$ identical residues, then the difference $ak-bk=(a-b)k$ ${\ displaystyle ak-bk = (ab) k}$ multiple $p$ ${\ displaystyle p}$ which is impossible because $a-b$ ${\ displaystyle ab}$ not multiple $p$ ${\ displaystyle p}$ . Total exists $p-1$ ${\ displaystyle p-1}$ different non-zero remainders from dividing by $p$ ${\ displaystyle p}$ .

Since, according to the above lemma, the remainders from the division of the numbers a , 2 a , 3 a , ..., ( p - 1) a are accurate to the permutation of the numbers 1, 2, 3, ..., p - 1 , then $a\cdot 2a\cdot 3a\ldots (p-1)a\equiv 1\cdot 2\cdot 3\ldots (p-1){\pmod {p}}$ ${\ displaystyle a \ cdot 2a \ cdot 3a \ ldots (p-1) a \ equiv 1 \ cdot 2 \ cdot 3 \ ldots (p-1) {\ pmod {p}}}$ . From here $a^{p-1}(p-1)!\equiv (p-1)!{\pmod {p}}$ ${\ displaystyle a ^ {p-1} (p-1)! \ equiv (p-1)! {\ pmod {p}}}$ . The last relation can be reduced by ( p - 1)! , since all factors are numbers coprime to the base p , as a result we obtain the required statement $a^{p-1}\equiv 1{\pmod {p}}$ ${\ displaystyle a ^ {p-1} \ equiv 1 {\ pmod {p}}}$ ^[14] .

Consequences and generalizations

If a $p$ ${\ displaystyle p}$ Is a prime number then in the field $\mathbb {Z} _{p}$ ${\ displaystyle \ mathbb {Z} _ {p}}$ equality holds $a^{-1}=a^{p-2}$ ${\ displaystyle a ^ {- 1} = a ^ {p-2}}$ ^[15] .
If a $p$ ${\ displaystyle p}$ Is a prime number other than 2 and 5, then the number $10^{p-1}-1$ ${\ displaystyle 10 ^ {p-1} -1}$ whose decimal notation contains only numbers $9$ ${\ displaystyle 9}$ , divided by $p$ ${\ displaystyle p}$ . It follows that for any integer $N$ ${\ displaystyle N}$ , which is not divisible by 2 or 5, we can choose a number consisting of only nine, which is divisible by $N$ ${\ displaystyle N}$ . This fact is used in the theory of signs of divisibility and periodic fractions ^[16] .
Fermat’s small theorem allows us to find prime divisors of numbers of the form $a^{4}+a^{3}+a^{2}+a+1$ ${\ displaystyle a ^ {4} + a ^ {3} + a ^ {2} + a + 1}$ and $a^{2^{n}}+1$ ${\ displaystyle a ^ {2 ^ {n}} + 1}$ . ^[17] .
A generalization of Fermat's small theorem on algebraic numbers is a theorem formulated by in 1839: let $a_{1},\dots ,a_{d}$ ${\ displaystyle a_ {1}, \ dots, a_ {d}}$ - the roots of the normalized polynomial $f\in \mathbb {Z} [x]$ ${\ displaystyle f \ in \ mathbb {Z} [x]}$ degrees d , and p is a prime. Then $a_{1}^{p}+a_{2}^{p}+\dots +a_{d}^{p}\equiv a_{1}+\dots +a_{d}{\pmod {p}}$ ${\ displaystyle a_ {1} ^ {p} + a_ {2} ^ {p} + \ dots + a_ {d} ^ {p} \ equiv a_ {1} + \ dots + a_ {d} {\ pmod { p}}}$ ^[18] .
From Fermat’s small theorem follows Wilson’s theorem : Natural number $p>1$ ${\ displaystyle p> 1}$ is simple if and only if $(p-1)!+1$ ${\ displaystyle (p-1)! + 1}$ divided by p .

Proof of Wilson's Theorem

states that if a polynomial of degree $n$ ${\ displaystyle n}$ divisible by prime $p$ ${\ displaystyle p}$ with more than $n$ ${\ displaystyle n}$ incongruent modulo $p$ ${\ displaystyle p}$ (i.e. having different residues when divided by $p$ ${\ displaystyle p}$ ) variable values $x$ ${\ displaystyle x}$ then it is divided into $p$ ${\ displaystyle p}$ at any value $x$ ${\ displaystyle x}$ .

Consider a polynomial

G(x)=(x-1)(x-2)(x-3)...(x-(p-1))-(x^{p-1}-1),

{\ displaystyle G (x) = (x-1) (x-2) (x-3) ... (x- (p-1)) - (x ^ {p-1} -1),}

Where

p

{\ displaystyle p}

- Prime number.

Then we find:

G(1)=0,G(2)=1-2^{p-1},G(3)=1-3^{p-1},...,G(p-1)=1-(p-1)^{p-1}.

{\ displaystyle G (1) = 0, G (2) = 1-2 ^ {p-1}, G (3) = 1-3 ^ {p-1}, ..., G (p-1) = 1- (p-1) ^ {p-1}.}

By virtue of Fermat’s small theorem, all these numbers are divisible by a prime $p$ ${\ displaystyle p}$ therefore comparison $G(x)\equiv 0{\pmod {p}}$ ${\ displaystyle G (x) \ equiv 0 {\ pmod {p}}}$ It has $p-1$ ${\ displaystyle p-1}$ incongruent decisions. On the other hand, the degree of the polynomial is only $p-2;$ ${\ displaystyle p-2;}$ it follows that the polynomial $G(x)$ ${\ displaystyle G (x)}$ divided by $p$ ${\ displaystyle p}$ for all values $x,$ ${\ displaystyle x,}$ and in particular when $x=0.$ ${\ displaystyle x = 0.}$

Means $G(0)=[(p-1)!+1]\equiv 0{\pmod {p}}.$ ${\ displaystyle G (0) = [(p-1)! + 1] \ equiv 0 {\ pmod {p}}.}$

And if, in addition to this, prove that for all difficult natural $n$ ${\ displaystyle n}$ , Besides $n=4$ ${\ displaystyle n = 4}$ , $(n-1)!\equiv 0{\pmod {n}}$ ${\ displaystyle (n-1)! \ equiv 0 {\ pmod {n}}}$ then we get the proof of the theorem. ^[nineteen]

Applications

Pseudo-Simple Farm Numbers and Simplicity Testing

Fermat's small theorem can be used to test the number for simplicity: if $(a^{p}-a)$ ${\ displaystyle (a ^ {p} -a)}$ not divided by $p$ ${\ displaystyle p}$ , then p is a composite number . However, the converse of Fermat’s small theorem is generally false: if $a$ ${\ displaystyle a}$ and $p$ ${\ displaystyle p}$ Are coprime numbers and $a^{p-1}-1$ ${\ displaystyle a ^ {p-1} -1}$ divided by p , then the number $p$ ${\ displaystyle p}$ can be both simple and compound. In the case when $p$ ${\ displaystyle p}$ is compound, it is called pseudo-simple Fermat at the base of a .

For example, the Chinese hypothesis states that $p$ ${\ displaystyle p}$ is a prime if and only if $2^{p}\equiv 2{\pmod {p}}$ ${\ displaystyle 2 ^ {p} \ equiv 2 {\ pmod {p}}}$ ^[20] . Here is a direct statement that if $p$ ${\ displaystyle p}$ simple then $2^{p}\equiv 2{\pmod {p}}$ ${\ displaystyle 2 ^ {p} \ equiv 2 {\ pmod {p}}}$ is a special case of Fermat's little theorem. The converse is that if $2^{p}\equiv 2{\pmod {p}}$ ${\ displaystyle 2 ^ {p} \ equiv 2 {\ pmod {p}}}$ then $p$ ${\ displaystyle p}$ simple, there is a special case of reversing Fermat's small theorem. This appeal is false: Sarrus in 1820 found that the number $N=2^{341-1}-1$ ${\ displaystyle N = 2 ^ {341-1} -1}$ divided by $341$ ${\ displaystyle 341}$ , because $N$ ${\ displaystyle N}$ divided by $2^{10}-1=3\cdot 341$ ${\ displaystyle 2 ^ {10} -1 = 3 \ cdot 341}$ . but $341$ ${\ displaystyle 341}$ - composite number : $341=11\cdot 31$ ${\ displaystyle 341 = 11 \ cdot 31}$ . Thus, 341 is a pseudo-prime number in base 2 ^[21] .

In the general case, the inverse of Fermat's small theorem also fails. A counterexample in the general case is Carmichael numbers : these are numbers p , which are pseudo-simple with respect to the base a for all a , coprime to p. The smallest Carmichael number is 561.

Since the inverse of Fermat’s small theorem is incorrect, the fulfillment of its condition does not guarantee that p is a prime . Nevertheless, Fermat’s small theorem underlies Fermat ’s simplicity test ^[22] . The Fermat test is a probabilistic simplicity test: if the theorem is not satisfied, then the number is exactly compound, and if it is true, then the number is prime with some probability . Other probabilistic methods include the Solovey – Strassen test and the Miller – Rabin test ; the latter relies to some extent on Fermat’s small theorem ^[23] . There is also a deterministic algorithm: Test Agrawala - Kayala - Saxen .

In addition, the following two statements are true. If the pair (2, n ) satisfy the comparison $a^{n-1}\equiv 1{\pmod {n}}$ ${\ displaystyle a ^ {n-1} \ equiv 1 {\ pmod {n}}}$ then a couple of numbers $(2,2^{n}-1)$ ${\ displaystyle (2,2 ^ {n} -1)}$ also satisfy him. For any prime number n and any a > 2 such that $(a^{2}-1,n)=1$ ${\ displaystyle (a ^ {2} -1, n) = 1}$ , value ${\frac {a^{2n}-1}{a^{2}-1}}$ ${\ displaystyle {\ frac {a ^ {2n} -1} {a ^ {2} -1}}}$ is the pseudo-simple Fermat number at base a ^[24] .

RSA Algorithm

Fermat’s small theorem is also used in proving the correctness of the RSA encryption algorithm ^[2] .

Notes

↑ ¹ ² Winberg, 2008 , p. 43.
↑ ¹ ² ³ Sagalovich, 2014 , p. 34.
↑ Encyclopedia of Elementary Mathematics, Book 1, Arithmetic, P. Aleksandrov, A. I. Markushevich, A. Y. Khinchin, 1961. — P. 280
↑ Z. I. Borevich, I.R. Shafarevich. Number theory - M: Science, 1972. - 175 p.
↑ Translation of the Encyclopedic Dictionary of the Young Mathematician. Comp. A.P. Savin . - M .: Pedagogy, 1989 .-- 352 p. Article: Fermat's little theorem.
↑ Fermat a Mersenne. <juin? 1640> Oeuvres de Fermat. Tome II. Paris: Tannery & Henry, 1904, pp. 195-199.
↑ Letter from Pierre Fermat , October 18, 1640, to the French mathematician Bernard Frenikl (neopr.) . Archived December 22, 2006.
↑ Danzig, T. Numbers - the language of science, 2008 , p. 231-234.
↑ David C. Marshall, Edward Odell, Michael Starbird . Number Theory Through Inquiry Archived September 16, 2012 on Wayback Machine . - 2006. - pp. 62-63.
↑ John J. O'Connor and Edmund F. Robertson . Sir James Ivory (English) - biography in the MacTutor archive.
↑ Vilenkin N. Ya., Shibasov L.P. Shibasova 3. F. Behind the pages of a mathematics textbook: Arithmetic. Algebra. Geometry. - M .: Education, 1996.- S. 30. - 320 p. - ISBN 5-09-006575-6 .
↑ Danzig, T. Numbers - the language of science, 2008 , p. 231-234.
↑ Winberg, 2008 , p. 44.
↑ QUANTUM, 2000, No. 1, Sender V, Spivak A. Fermat’s Little Theorem.
↑ Akritas A. Fundamentals of Computer Algebra with Applications, p. 83.
↑ Danzig, T. Numbers - the language of science, 2008 , p. 232-234.
↑ QUANTUM, 2000, No. 3, Sender B, Spivak A, Fermat's Small Theorem
↑ Winberg, 2008 , p. 49.
↑ Danzig, T. Numbers - the language of science, 2008 , p. 234-238.
↑ Ribenboim, P. (1996), The New Book of Prime Number Records, New York: Springer-Verlag, pp. 103-105, ISBN 0-387-94457-5 .
↑ Weisstein EW Fermat Pseudoprime .. - 2005 ..
↑ Gabidulin E.M., Kshevetsky A.S., Kolybelnikov A.I. Information security: a training manual. - M .: MIPT, 2011 .-- S. 236-237. - 262 p. with. - ISBN 978-5-7417-0377-9 .
↑ Williams HC Primality testing on a computer (English) // Ars Combin. - 1978. - Vol. T. 5 , no. No. 12 . - P. 127-185 .
↑ Shitov Yu.A. Numerical methods in cryptography.

Literature

Aleksandrov P. C., Markushevich A.I., Khinchin A. Ya. Encyclopedia of Elementary Mathematics. Volume I: Arithmetic. - 1951.
Borevich Z. I., Shafarevich I. R. Theory of numbers . - M .: Nauka, 1972.- 510 p. Archived January 8, 2011 on Wayback Machine
Vinberg, E. B. Malaya Fermat's theorem and its generalizations // Mat. drift - M .: Publishing House of the Moscow Center for Scientific and Technical Education, 2008. - V. 12. - P. 43–53.
<a href=" https://wikidata.org/wiki/Track:Q21789820 "> </a> <a href=" https://wikidata.org/wiki/Track:Q450643 "> </a> <a href = " https://wikidata.org/wiki/Track:Q4284740 "> </a>
Gindikin S. G. "Fermat's Small Theorem" . - Quantum , 1972. - No. 10 . (inaccessible link)
Danzig, T. Numbers - the language of science . - M .: Technosphere, 2008 .-- ISBN 978-5-94836-172-7 .
Nesterenko Yu. V. Algorithmic problems of number theory . - 1997. - Vol. 2 . - No. third series .
Sagalovich Yu. L. Introduction to algebraic codes - 3rd ed., Rev. and add. - M .: IPPI RAS , 2014 .-- 310 p. - ISBN 978-5-901158-24-1
<a href=" https://wikidata.org/wiki/Track:Q21789632 "> </a> <a href=" https://wikidata.org/wiki/Track:Q21789631 "> </a>
Senderov V, Spivak A. Malaya Fermat's theorem // Quantum. - 2000. - No. 1 .
Senderov V, Spivak A. Malaya Fermat's theorem // Quantum. - 2000. - No. 3 .

[_bb963095c1c280e5-1] ¹ ² Winberg, 2008 , p. 43.

[_0969f11995f6b722-2] ¹ ² ³ Sagalovich, 2014 , p. 34.

[3] Encyclopedia of Elementary Mathematics, Book 1, Arithmetic, P. Aleksandrov, A. I. Markushevich, A. Y. Khinchin, 1961. — P. 280

[4] Z. I. Borevich, I.R. Shafarevich. Number theory - M: Science, 1972. - 175 p.

[5] Translation of the Encyclopedic Dictionary of the Young Mathematician. Comp. A.P. Savin . - M .: Pedagogy, 1989 .-- 352 p. Article: Fermat's little theorem.

[6] Fermat a Mersenne. <juin? 1640> Oeuvres de Fermat. Tome II. Paris: Tannery & Henry, 1904, pp. 195-199.

[7] Letter from Pierre Fermat , October 18, 1640, to the French mathematician Bernard Frenikl (neopr.) . Archived December 22, 2006.

[_dc30ecbfa12b7ba1-8] Danzig, T. Numbers - the language of science, 2008 , p. 231-234.

[9] David C. Marshall, Edward Odell, Michael Starbird . Number Theory Through Inquiry Archived September 16, 2012 on Wayback Machine . - 2006. - pp. 62-63.

[10] John J. O'Connor and Edmund F. Robertson . Sir James Ivory (English) - biography in the MacTutor archive.

[11] Vilenkin N. Ya., Shibasov L.P. Shibasova 3. F. Behind the pages of a mathematics textbook: Arithmetic. Algebra. Geometry. - M .: Education, 1996.- S. 30. - 320 p. - ISBN 5-09-006575-6 .

[_9285e3179881c054-12] Danzig, T. Numbers - the language of science, 2008 , p. 231-234.

[_bb963095c1c280e2-13] Winberg, 2008 , p. 44.

[14] QUANTUM, 2000, No. 1, Sender V, Spivak A. Fermat’s Little Theorem.

[15] Akritas A. Fundamentals of Computer Algebra with Applications, p. 83.

[DAN-16] Danzig, T. Numbers - the language of science, 2008 , p. 232-234.

[17] QUANTUM, 2000, No. 3, Sender B, Spivak A, Fermat's Small Theorem

[_bb963095c1c280ef-18] Winberg, 2008 , p. 49.

[_45ee36fdc71802a9-19] Danzig, T. Numbers - the language of science, 2008 , p. 234-238.

[:2-20] Ribenboim, P. (1996), The New Book of Prime Number Records, New York: Springer-Verlag, pp. 103-105, ISBN 0-387-94457-5 .

[:0-21] Weisstein EW Fermat Pseudoprime .. - 2005 ..

[22] Gabidulin E.M., Kshevetsky A.S., Kolybelnikov A.I. Information security: a training manual. - M .: MIPT, 2011 .-- S. 236-237. - 262 p. with. - ISBN 978-5-7417-0377-9 .

[23] Williams HC Primality testing on a computer (English) // Ars Combin. - 1978. - Vol. T. 5 , no. No. 12 . - P. 127-185 .

[24] Shitov Yu.A. Numerical methods in cryptography.