What is most motivating way to introduce Fermat's Little Theorem

What is the best way to introduce Fermat’s Little Theorem (F$l$T) to students? What can I use as an opening paragraph which will motivate and have an impact on why students should learn this theorem and what are the applications of F$l$T? Are there any good resources on this topic?

• (Often FlT or F$\ell$T is used to refer to this theorem so as to avoid confusion with Fermat's Last Theorem...) – Benjamin Dickman Apr 23 '17 at 18:59
• I think the answer to this question probably depends on what class you're teaching and what the background of students is. One great application of Fermat's Little Theorem is the RSA cryptosystem. Although RSA is usually described starting with Euler's theorem (a generalization of Fermat's) it can be described just based on Fermat's, though that's easier given familiarity with modular (multiplicative) inverses. – Chris Chudzicki Apr 23 '17 at 20:17
• The link with primality testing is interesting. Start with a puzzle: how can you tell if a really big number is prime, when the number is so big that attempting to factor a number of that size might take billions of years using current methods and hardware? Introduce FLT as a method for classifying (most) odd composite numbers as composite without needing to actually factor them. If it wouldn't be too tangential, this could lead into a discussion of Fermat pseudoprimes, how PGP identifies probable primes, and the Miller-Rabin test. – John Coleman Apr 24 '17 at 3:12

I wrote an article for NCTM's grades 8-14 journal, The Mathematics Teacher, which is about building towards ${\rm F}\ell{\rm T}$ by thinking through ways in which the following statement can be generalized:

If you subtract a natural number from its square, then the result is even.

I wrote more about this in some earlier StackExchange posts, e.g., MESE 907. Since then, the article has appeared; its citation and link are:

Dickman, B. (2017). Enriching divisibility: multiple proofs and generalizations. The Mathematics Teacher, 110(6), pp. 416-423. Link (without pay-wall).

The write-up is less concerned with specific applications, and has as its goal, instead, to indicate how the process of generalizing a routine number theoretic proposition can lead to theorems like ${\rm F}\ell{\rm T}$.

Look at patterns in decimal expansions: what is the period of the repeating decimal of $1/n$? From numerical data, the period is at most $n-1$, and you only get equality when $n = p$ is prime (but not conversely: $1/11$ has decimal period $2$, not $10$). If you look at the period of the decimal of $1/p$ for primes $p$ besides $2$ and $5$, you find that although the period is not always $p-1$ it does always appear to divide $p-1$.

That divisibility (sharper than an inequality) is basically Fermat's little theorem. The period of the decimal for $1/n$ is the order of $10 \bmod n$ (for $n$ relatively prime to $10$), so the fact that the period of the decimal for $1/p$ when $p$ is a prime (besides $2$ or $5$) is a factor of $p-1$ is equivalent to saying $10^{p-1} \equiv 1 \bmod p$. This is possibly how Gauss was led to Fermat's little theorem.

Beauty. I really enjoy the combinatorial necklace proof, which alone could motivate it.

Another way to think of it is a representation which I first learned of in Wagon and Bressoud, where you look at a table of all powers of the integers (or units) modulo $p$ and color-code entries by least nonnegative residue. Then the last column of the table is all one color, just like the first column; the first column is $a^0\equiv 1$, but the last is $a^{p-1}\equiv 1$; so we have a visualization of FlT (among many other results).

Try it out! (Quick Sage code below, you may wish to relabel the rows or columns.)

@interact
def power_table_plot(p=(7,prime_range(50))):
P=matrix_plot(matrix(p-1,[mod(a,p)^b for a in range(1,p) for b in srange(p)]),cmap='jet')
show(P,figsize=6)

Generally We enter the subject(FLT) with a problem like $a^m \equiv ? \pmod{n}$.

After the training like these:

$3^{100}\equiv ? \pmod{5}$, $2^{80}\equiv ? \pmod{7}$, ... etc

Students are important to 'We need to smallest positive $m$ that $3^{m}\equiv 1 \pmod{5}$ or $2^{m}\equiv 1 \pmod{7}$, ... etc. (in fact $m$ is order of $3$ in $\mod 5$.) But sometimes we are in difficulty for finding the order. Especially for bigger $p$ prime numbers in $\mod{p}$. If we ask to students $2^{100}\equiv ? \pmod{101}$, they will spend a lot of time. Thus, we can give FLT to students. If students do not use FLT, they will conclude that it will be very difficult.

Furthermore, if $\gcd (a,p)=1$ then $a^{p-1}\equiv 1 \pmod{p}$ but $p-1$ coudn't be order of $a$ in $\mod p$. So, we can say $\text{ord}(a) \mid {p-1}$.

Last of all; because of The World need to the order(!), FLT is important for us:)