The Inductive Proof and Applications of Fermat's Little Theorem

Posted on 2023-11-14 Edited on 2023-11-17 In Study Notes Views: Symbols count in article: 14k Reading time ≈ 13 mins.

In the history of mathematics, Pierre de Fermat was a special figure. His formal occupation was as a lawyer, but he was exceptionally fond of mathematics. Although an amateur, Fermat’s achievements in mathematics were no less than those of professional mathematicians of the same era. He contributed to modern calculus, analytic geometry, probability, and number theory. Especially in the field of number theory, Fermat was most interested and achieved the most outstanding results.

Logic is the foundation of the certainty of all the knowledge we acquire.
— Leonhard Euler (Swiss mathematician, physicist, astronomer, geographer, logician, and engineer, one of the greatest mathematicians in history)

As the "king of amateur mathematicians", Fermat proposed some famous conjectures in number theory but did not give strong proof. The most famous is Fermat's Last Theorem¹. Although Fermat claimed he had found an ingenious proof, there was not enough space on the margin to write it down. But in fact, after more than 350 years of unremitting efforts by mathematicians, it was not until 1995 that British mathematician Andrew John Wiles and his student Richard Taylor published a widely recognized proof.

Ferma and Fermat's Last Theorem On Stamp

In contrast, there is also a little theorem of Fermat. In October 1640, Fermat first wrote down words equivalent to the following in a letter to a friend:

If \(p\) is a prime and \(a\) is any integer not divisible by \(p\), then \(a^{p-1}-1\) is divisible by \(p\).

Similarly, Fermat did not give proof in the letter. Nearly a hundred years later, the complete proof was first published by the great mathematician Euler in 1736. Later, people found in the unpublished manuscripts of another great mathematician Leibniz that he had obtained almost the same proof before 1683.

Fermat's little theorem is one of the fundamental results of elementary number theory. This theorem can be used to generate primality testing rules and corresponding verification algorithms. In the late 1970s, public key cryptography emerged, and Fermat's little theorem helped prove the correctness of RSA. Afterward, researchers combined it with the Chinese remainder theorem and also discovered an optimized method for RSA decryption and signing. The following further introduces these applications.

Theorem and Corollaries

The complete statement of Fermat's little theorem is: If \(\pmb{p}\) is a prime number, then for any integer \(\pmb{a}\), the number \(\pmb{a^p−a}\) is an integer multiple of \(\pmb{p}\). In the notation of modular arithmetic, this is expressed as \(\pmb{a^p\equiv a\pmod p}\). If \(\pmb{a}\) is not divisible by \(\pmb{p}\), then \(\pmb{a^{p-1}\equiv 1\pmod p}\).

From \(a^{p-1}\equiv 1\pmod p\) it can be deduced that \(\pmb{a^{p-2}\equiv a^{-1}\pmod p}\). This new congruence just gives a way to find the multiplicative inverse of \(a\) modulo \(p\). This is a direct corollary of Fermat's little theorem.

Another important corollary is: If \(\pmb{a}\) is not a multiple of \(\pmb{p}\) and \(\pmb{n=m\bmod {(p-1)}}\), then \(\pmb{a^n\equiv a^m\pmod p}\). This inference does not seem very intuitive, but the proof is simple:

Because \(n=m\bmod {(p-1)}\), it follows that \(m = k⋅(p-1)+n\)
Substituting the result into the power operation, \(a^m=a^{k⋅(p-1)+n}=(a^{(p-1)})^k⋅a^n\)
Then applying modular arithmetic and Fermat's little theorem, \(a^m=(a^{(p-1)})^k⋅a^n\equiv (1)^ka^n\equiv a^n\pmod p\)
Therefore \(a^n\equiv a^m\pmod p\), Q.E.D.

Proof by Induction

There are many ways to prove Fermat's little theorem. Among them, mathematical induction based on the binomial theorem is the most intuitive one. First, for \(a=1\), it is obvious that \(1^p \equiv 1\pmod{p}\) holds. Now assume that for an integer \(a\), \(a^p \equiv a \pmod{p}\) is true. As long as it is proved under this condition that \((a+1)^p\equiv a+1\pmod{p}\), the proposition holds.

According to the binomial theorem, \[(a+1)^p = a^p + {p \choose 1} a^{p-1} + {p \choose 2} a^{p-2} + \cdots + {p \choose p-1} a + 1\] Here the binomial coefficient is defined as \({p \choose k}= \frac{p!}{k! (p-k)!}\). Note that because \(p\) is a prime number, for \(1≤k≤p-1\), each binomial coefficient \({p \choose k}\)is a multiple of \(p\).

Then taking \(\bmod p\), all the intermediate terms disappear, leaving only \(a^p+1\) \[(a+1)^p \equiv a^p + 1 \pmod{p}\]Referring to the previous assumption \(a^p ≡ a \pmod p\), it infers that \((a+1)^p \equiv a+1 \pmod{p}\), the proof is complete.

Applications of the Theorem

Solution to Math Competition Problems

Fermat's little theorem provides concise solutions to some seemingly complicated computational problems. First look at a simple example: If today is Sunday, what day will it be in \(2^{100}\) days? There are 7 days in a week. According to Fermat's little theorem, we have \(2^{7−1}≡1\bmod 7\), from which we can get \[2^{100}=2^{16×6+4} ≡ 1^{16}×2^4≡16≡2\pmod 7\]So the answer is Tuesday. This actually repeats the proof process of the second corollary above with specific numbers. Applying this corollary can greatly speed up modular exponentiation. For example, to calculate \(49^{901}\bmod 151\), since \(901\bmod(151-1)=1\), it can be deduced immediately that \[49^{901}\equiv 49^1\equiv 49\pmod {151}\]

Now look at a question that seems a little more difficult: Given the equation \(133^5+110^5+84^5+27^5=n^{5}\), find the value of \(n\).

At first glance, there seems to be no clue, so start with basic parity checking. The left side of the equation has two odd terms and two even terms, so the total is even, which also determines that \(n\) must be even. Looking at the exponent 5 which is a prime number, and thinking of Fermat's little theorem, we get \(n^5≡n\pmod 5\), therefore \[133^5+110^5+84^5+27^5≡n\pmod 5\] \[3+0+4+2≡4≡n\pmod 5\] Continuing to take modulo 3, according to the corollary of Fermat's little theorem again, we have \(n^5≡n^{5\mod(3-1)}≡n\pmod 3\). So \[133^5+110^5+84^5+27^5≡n\pmod 3\] \[1+2+0+0≡0≡n\pmod 3\]

Okay, now summarize:

\(n\) should be greater than 27 and an even number
\(n\) is a multiple of 3, so the sum of all digits is a multiple of 3
\(n\) divided by 5 gives a remainder of 4, the ones place should be 4 (9 does not satisfy the condition of an even number)

These lead to \(n = 144\) or \(n\geq 174\). Obviously, 174 is too big. It can be concluded that n can only be 144.

This question actually appeared in the 1989 American Invitational Mathematics Examination (AIME), which is a math competition for high school students. Interestingly, the solution to the question happens to disprove Euler's conjecture.

Primality Testing

Many encryption algorithm applications require "random" large prime numbers. The common method to generate large primes is to randomly generate an integer and then test for primality. Since Fermat’s little theorem holds on the premise that p is a prime number, this provides a prime test method called the Fermat primality test. The test algorithm is

Input: \(n\) - the number to be tested, \(n>3\); \(k\) - the number of iterations
Output: \(n\) is composite, otherwise may be prime
Repeat k times:
\(\quad\quad\)Randomly select an integer \(a\) between \([2, n-2]\)
\(\quad\quad\)If \(a^{n-1}\not \equiv 1{\pmod n}\), return \(n\) is composite
Return \(n\) may be prime

It can be seen that Fermat’s primality test is non-deterministic. It uses a probabilistic algorithm to determine whether a number is composite or probably prime. When the output is composite, the result is definitely correct; but those numbers tested to be probably prime may actually be composite, such numbers are called Fermat pseudoprimes. The smallest Fermat pseudoprime is 341, with \(2^{340}\equiv1\pmod {341}\) but \(341=11×31\). So in fact, Fermat's little theorem provides a necessary but insufficient condition for determining prime numbers. It can only be said that the more iterations performed, the higher the probability that the tested number is prime.

There is also a class of Fermat pseudoprimes \(n\) which are composite numbers themselves, but for any integer \(x\) that is coprime with \(n\), it holds \(x^{n-1}\equiv 1\pmod n\). In number theory, they are called Carmichael numbers. The smallest Carmichael number is 561, equal to \(3×11×17\). Carmichael numbers can fool Fermat’s primality test, making the test unreliable. Fortunately, such numbers are very rare. Statistics show that among the first \(10^{12}\) natural numbers there are only 8241 Carmichael numbers.

The PGP encryption communication program uses Fermat’s primality test in its algorithm. In network communication applications requiring large primes, Fermat’s primality test method is often used for pretesting, followed by calling the more efficient Miller-Rabin primality test to ensure high accuracy.

Proof of RSA Correctness

Fermat's little theorem can also be used to prove the correctness of the RSA algorithm, that is, the decryption formula can completely restore the plaintext \(m\) from the ciphertext \(c\) without errors: \[c^d=(m^{e})^{d}\equiv m\pmod {pq}\]

Here \(p\) and \(q\) are different prime numbers, \(e\) and \(d\) are positive integers that satisfy \(ed≡1\pmod {λ(pq)}\), where \(λ(pq)=\mathrm{lcm}(p−1,q−1)\). \(\mathrm{lcm}\) is the least common multiple function.

Before starting the proof, first introduce a corollary of the Chinese remainder theorem: If integers \(\pmb{n_1,n_2,...,n_k}\) are pairwise coprime and \(\pmb{n=n_{1}n_{2}...n_{k}}\), then for any integer \(\pmb x\) and \(\pmb y\), \(\pmb{x≡y\pmod n}\) holds if and only if \(\pmb{x≡y\pmod{n_i}}\) for each \(\pmb{i=1,2,...k}\). This corollary is easy to prove, details are left as an exercise². According to this corollary, if \(m^{ed}≡m\pmod p\) and \(m^{ed}≡m\pmod q\) are both true, then \(m^{ed}≡m\pmod{pq}\) must also hold.

Now look at the first step of the proof. From the relationship between \(e\) and \(d\), it follows \(ed-1\) can be divided by both \(p-1\) and \(q-1\), that is, there exist non-negative integers \(h\) and \(k\) satisfying: \[ed-1=h(p-1)=k(q-1)\]

The second step is to prove \(m^{ed}≡m\pmod p\). Consider two cases:

If \(m≡ 0\pmod p\), i.e. \(m\) is an integer multiple of \(p\), then naturally \(m^{ed}≡0≡m\pmod p\)
If \(m\not \equiv 0\pmod p\), it can be deduced that: \[m^{ed}=m^{ed-1}m=m^{h(p-1)}m=(m^{p-1})^{h}m\equiv 1^{h}m\equiv m{\pmod {p}}\]Here Fermat’s little theorem \(m^{p−1}≡1\pmod p\) is applied.

The third step has the goal of proving \(m^{ed}≡m\pmod q\). The deduction process is similar to the previous step, and it can also be deduced that m^ed ≡ m (mod q):

If \(m≡ 0\pmod p\), i.e. \(m\) is an integer multiple of \(q\), then naturally \(m^{ed}≡0≡m\pmod q\)
If \(m\not \equiv 0\pmod q\), it can be deduced that: \[m^{ed}=m^{ed-1}m=m^{h(q-1)}m=(m^{q-1})^{h}m\equiv 1^{h}m\equiv m{\pmod {q}}\]

Since both \(m^{ed}≡m\pmod p\) and \(m^{ed}≡m\pmod q\) have been proved, \(m^{ed}≡m\pmod{pq}\) holds, Q.E.D.

Optimized RSA Decryption

Combining Fermat’s little theorem and the Chinese remainder theorem can not only verify the correctness of the RSA but also deduce an optimized decryption method.

In the RSA encryption algorithm, the modulus \(N\) is the product of two prime numbers \(p\) and \(q\). Therefore, for any number \(m\) less than \(N\), letting \(m_1=m\bmod p\) and \(m_2=m\bmod q\), \(m\) is uniquely determined by \((m_1,m_2)\). According to the Chinese remainder theorem, we can use the general solution formula to deduce \(m\) from \((m_1,m_2)\). Since \(p\) and \(q\) each have only half the number of bits as \(N\), modular arithmetic will be more efficient than directly computing \(c^d\equiv m\pmod N\). And in the process of calculating \((m_1,m_2)\), applying the corollary of Fermat's little theorem yields: \[\begin{align} m_1&=m\bmod p=(c^d\bmod N)\bmod p\\ &=c^d\bmod p=c^{d\mod(p-1)}\bmod p\tag{1}\label{eq1}\\ m_2&=m\bmod q=(c^d\bmod N)\bmod q\\ &=c^d\bmod q=c^{d\mod(q-1)}\bmod q\tag{2}\label{eq2}\\ \end{align}\]

Obviously, in above \((1)\) and \((2)\) the exponent \(d\) is reduced to \(d_P=d\bmod (p-1)\) and \(d_Q=d\bmod (q-1)\) respectively, which further speeds up the calculation. Finally, the step of calculating \(m\) is further optimized using the Garner algorithm³: \[\begin{align} q_{\text{inv}}&=q^{-1}\pmod {p}\\ h&=q_{\text{inv}}(m_{1}-m_{2})\pmod {p}\\ m&=m_{2}+hq\pmod {pq}\tag{3}\label{eq3} \end{align}\] Note that given \((p,q,d)\), the values of \((d_P,d_Q,q_\text{inv})\) are determined. So they can be precomputed and stored. For decryption, only \((m_1,m_2,h)\) are to be calculated and substituted into the above (3).

This is actually the decryption algorithm specified in the RSA cryptography standard RFC 8017 (PKCS #1 v2.2). The ASN.1 formatted key data sequence described by this specification corresponds exactly to the above description (\(d_P\) - exponent1，\(d_Q\) - exponent2，\(q_{\text{inv}}\) - coefficient):

RSAPrivateKey ::= SEQUENCE {
    version           Version,
    modulus           INTEGER,  -- n
    publicExponent    INTEGER,  -- e
    privateExponent   INTEGER,  -- d
    prime1            INTEGER,  -- p
    prime2            INTEGER,  -- q
    exponent1         INTEGER,  -- d mod (p-1)
    exponent2         INTEGER,  -- d mod (q-1)
    coefficient       INTEGER,  -- (inverse of q) mod p
    otherPrimeInfos   OtherPrimeInfos OPTIONAL
}

The widely used open-source library OpenSSL implements this efficient and practical decryption algorithm. As shown below, the key data generated using the OpenSSL command line tool is consistent with the PKCS #1 standard:

# Generate 512-bit RSA keys saved in PEM format file.
# For demo only, DON'T USE 512-bit KEYS IN PRODUCTION!
$ openssl genrsa -out private-key.pem 512
Generating RSA private key, 512 bit long modulus
.++++++++++++
......................++++++++++++
e is 65537 (0x10001)

# Inspect RSA keys saved in a PEM format file.
$ openssl pkey -in private-key.pem -text
-----BEGIN PRIVATE KEY-----
MIIBVAIBADANBgkqhkiG9w0BAQEFAASCAT4wggE6AgEAAkEA7HwgswSjqvDRPWj3
vVIxMZDAtXJCa7Qx+2jFv7e7GXB8+fa3MTBL36YjIcAgLeCHAyIzWkPndxvTJE2l
WvYzRQIDAQABAkBCUp2pF0f/jQJhwqqYQhDh4cLqIF1Yb3UFGWE8X37tpwCifAqg
t8NEpaXWkct5M+YxqjKfdOKYy0TVcJRlyS+RAiEA9xujHmh+bOvl0xWDFoARDAHw
v94qRCpeRNveHFpNvPsCIQD0/qFpeSjRWj/4vjCkIOv1RbbhDHVsgsF9HRJNW2Rc
vwIgaGIAUcQKQ7CScMxRh5upl8zqCeKrMAhFsgi+lnN/CykCIDMdAL4Jmht7ccdK
nslPWQs1/T6co878xLN+ojfjbl/vAiEAhmp4YDX1g8kFh6cVtTIDT5AGtzqwB2Jw
cCq+IoKDYBc=
-----END PRIVATE KEY-----
Private-Key: (512 bit)
modulus:
    00:ec:7c:20:b3:04:a3:aa:f0:d1:3d:68:f7:bd:52:
    31:31:90:c0:b5:72:42:6b:b4:31:fb:68:c5:bf:b7:
    bb:19:70:7c:f9:f6:b7:31:30:4b:df:a6:23:21:c0:
    20:2d:e0:87:03:22:33:5a:43:e7:77:1b:d3:24:4d:
    a5:5a:f6:33:45
publicExponent: 65537 (0x10001)
privateExponent:
    42:52:9d:a9:17:47:ff:8d:02:61:c2:aa:98:42:10:
    e1:e1:c2:ea:20:5d:58:6f:75:05:19:61:3c:5f:7e:
    ed:a7:00:a2:7c:0a:a0:b7:c3:44:a5:a5:d6:91:cb:
    79:33:e6:31:aa:32:9f:74:e2:98:cb:44:d5:70:94:
    65:c9:2f:91
prime1:
    00:f7:1b:a3:1e:68:7e:6c:eb:e5:d3:15:83:16:80:
    11:0c:01:f0:bf:de:2a:44:2a:5e:44:db:de:1c:5a:
    4d:bc:fb
prime2:
    00:f4:fe:a1:69:79:28:d1:5a:3f:f8:be:30:a4:20:
    eb:f5:45:b6:e1:0c:75:6c:82:c1:7d:1d:12:4d:5b:
    64:5c:bf
exponent1:
    68:62:00:51:c4:0a:43:b0:92:70:cc:51:87:9b:a9:
    97:cc:ea:09:e2:ab:30:08:45:b2:08:be:96:73:7f:
    0b:29
exponent2:
    33:1d:00:be:09:9a:1b:7b:71:c7:4a:9e:c9:4f:59:
    0b:35:fd:3e:9c:a3:ce:fc:c4:b3:7e:a2:37:e3:6e:
    5f:ef
coefficient:
    00:86:6a:78:60:35:f5:83:c9:05:87:a7:15:b5:32:
    03:4f:90:06:b7:3a:b0:07:62:70:70:2a:be:22:82:
    83:60:17

Also known as "Fermat's conjecture"，its gist is that, when \(n > 2\), the equation \(x^{n}+y^{n}=z^{n}\) has no positive integer solutions \((x, y, z)\). After it was finally proven correct in 1995, it became known as "Fermat's last theorem."↩︎
Hint: If two integers are congruent modulo \(n\), then \(n\) is a divisor of their difference.↩︎
Garner, H., "The Residue Number System", IRE Transactions on Electronic Computers, Volume EC-8, Issue 2, pp.140-147, DOI 10.1109/TEC.1959.5219515, June 1959↩︎