Skip to main content

Section 5.4 Some Contributions of Fermat

Though we all seem to remember Pierre de Fermat for his "Last" theorem, he did much more than just scribble notes in the margins of books. In fact, Fermat was one of the last great mathematicians to pursue mathematics as an aside to his normal life; he was a lawyer and magistrate. Due to this he is known as the "Prince of Amateurs." In this lecture we will discuss some of the mathematics behind the man.

Section 5.4.1 Factoring Integers

With this theorem in mind Fermat figured out a way to factor an integer, that is usually quicker than the method in the application above.

Since powers of two are easy to factor, let us assume that \(n\) is odd. Fermat noticed that finding a factor of an odd integer \(n\) is equivalent to finding an integer solution to

\begin{equation*} n=x^2-y^2 \end{equation*}

If this is the case, then

\begin{equation*} n=x^2-y^2=(x-y)(x+y), \end{equation*}

and conversely if \(n=ab\) where \(a\geq b\geq 1,\) then

\begin{equation*} n=ab=\left(\frac{a+b}{2}\right)^2-\left(\frac{a-b}{2}\right)^2. \end{equation*}

To start the search for factors of \(n,\) we notice that the equation \(n =x^2-y^2\) is equivalent to

\begin{equation*} x^2-n=y^2. \end{equation*}

So we find the smallest \(k\) for which \(k^2\geq n,\) and look at the numbers

\begin{equation*} k^2-n,(k + 1)^2-n,(k + 2)^2-n,(k + 3)^2-n,(k + 4)^2-n,... \end{equation*}

until a value \(m\geq\sqrt{n}\) is found making \(m^2-n\) a square. We know the process ends since

\begin{equation*} n=\left(\frac{n+1}{2}\right)^2-\left(\frac{n-1}{2}\right)^2, \end{equation*}

which corresponds to the factorization \(n = n\cdot 1.\)

Remark 5.4.1.

Fermat used this method to factor

\begin{equation*} 2027651281 = 44021\cdot 46061 \end{equation*}

in \(11\) steps, compared to doing \(4580\) divisions by odd primes up to \(44021.\)

This method gets more effective if there are two factors close to \(\sqrt{n}.\)

Let \(n = 23449.\) The smallest square exceeding \(n\) is \(154^2,\) so we have

\begin{align*} 154^2-23449 \amp= 23716-23449 = 267\\ 155^2-23449 \amp= 24075-23449 = 576 = 24^2, \end{align*}

so that

\begin{equation*} 23449 = 155^2-24^2 = (155+24)(155-24) = 179\cdot 131. \end{equation*}

If we used the odd prime division way to find a factorization, it would have taken, \(\pi(131) = 32\) divisions.

Section 5.4.2 Fermat's Little Theorem

This is another of Fermat's many contributions, which again he did not prove (to our knowledge). He wrote in a letter to Frénicle dated October 18, 1640, "I would send you a demonstration, if I did not fear its being too long." Again, it would be almost 100 years before Euler, in 1736, would give the first proof of Fermat's Little Theorem.

To show this, let \(p\) be a prime, \(a\in\mathbb{N},\) and \(p\nmid a.\) Consider the multiples of \(a,\)

\begin{equation*} a, 2a, 3a,..., (p-1)a. \end{equation*}

None of these are congruent modulo \(p,\) since if \(ra\equiv sa \pmod{p}\) with \(0\leq r\lt s\lt p-1,\) then \(r\equiv s\pmod{p}\) so that \(p\vert r-s,\) which is impossible.

Thus the set of integers in the above list is congruent modulo \(p\) to the set \(1, 2,..., p-1,\) so that

\begin{equation*} a\cdot 2a\cdot 3a...(p-1)a\equiv 1\cdot 2\cdot 3...(p-1) \pmod{p}. \end{equation*}

Since \(\gcd((p-1)!, p) = 1\) we may cancel \((p-1)!\) from each side to give \(a^{p-1}\equiv 1\pmod{p}.\)

If \(p\vert a\) the statement holds trivially. If \(p \nmid a,\) then Fermat's Little Theorem gives \(a^{p-1} \equiv 1 \pmod{p},\) so that multiplication on each side by \(a\) gives the desired result.

By the previous corollary \((a^q)^p \equiv a^q \pmod{p}.\) Since, by hypothesis, \(a^q \equiv a\pmod{p},\) we have \(a^{pq} \equiv a\pmod{p}\) so that \(p\vert a^{pq}-a.\) Similarly \(q\vert a^{pq}-a\) so that since \(\gcd(p, q) = 1\) we have \(pq\vert a^{pq}-a\) and so \(a^{pq} \equiv a\pmod{p}.\)

Remark 5.4.4.

Fermat's Little Theorem can be used as a test for non-primality. Suppose you have a number \(n,\) and you wish to know if \(n\) is not prime. If

\begin{equation*} 2^n\not\equiv 2\pmod{n}, \end{equation*}

then \(n\) is not prime.

Consider \(n = 117,\) then

\begin{equation*} 2^{117} = 2^{7\cdot 16+5} = (2^7)^{16}2^5 \end{equation*}

and \(2^7 = 128 \equiv 11 \pmod{117}.\) So

\begin{align*} 2^{117} \amp \equiv 11^{16}2^5\\ \amp\equiv 121^82^5 \\ \amp\equiv 4^82^5 \\ \amp\equiv 2^21 \\ \amp\equiv (2^7)^3 \\ \amp\equiv 11^3 \\ \amp\equiv 121\cdot 11 \\ \amp\equiv 4\cdot 11 \\ \amp\equiv 44 \\ \amp\not\equiv 2\pmod{117}, \end{align*}

so \(117\) is not prime.

Unfortunately this test cannot be used to show a number is prime. In fact, there are composite numbers \(n\) for which \(2^n\equiv 2 \pmod{n}.\) These are special.