Fermat's Little Theorem

Voiceover: Bob discovered
something very interesting

while making multicolored earrings

out of beads for his store.

Now, his customers like variety,

so he decides to make every
possible style for each size.

Starting with size three, he begins

by figuring out all possible styles.

Each earring begins as a string of beads,

and then the ends are
attached to form a ring.

So first, how many
possible strings are there?

With two colors and three beads,

there are three choices,
each from two colors.

So two times two times two equals eight

possible unique strings.

And then he subtracts the strings

which have only one color,
or monocolored strings,

since he's only building
multicolored earrings.

Then he glues them all
together to form rings.

He was assuming he would end
up with six different earrings,

but something happened.

He could no longer tell the
difference between most of them.

It turns out he only has two styles,

because each style is now part of a group

with two identical partners.

Notice you can always match
them up based on rotations.

So the size of these groups must be based

on how many rotations it takes
to return to the original.

Or how many rotations to complete a cycle.

So this means that the original set

of all multicolored strings divides evenly

into groups of size three.

Now, would this be true for other sizes?

That would be convenient,
since he always wants

the same amount of each style.

So he tries this with four beads.

First he builds all possible strings.

With four beads he can
choose from two colors

for each bead, so two times two

times two times two equals sixteen.

Then he removes the two
monocolored necklaces

and attaches all of the
others to form rings.

Now, will they form equal sized groups?

Apparently not.

What happened?

Notice how the initial set of
strings divides into styles.

If strings are of the same style,

it means you can form one into the other

simply by grabbing beads from one end

and sticking them onto the other end.

And there is one style
which only has two members,

and this is because it's built

out of a repeating unit of length two.

So only two rotations are
required to complete a cycle.

Therefore this group only contains two.

He cannot split them into
an equal number of styles.

What about size five?

Will they break into equal
number of each style?

Wait, suddenly he realizes he doesn't even

need to build them in order to find out.

It must work, since five cannot be made up

of a repeating pattern, because five

cannot be broken up into equal parts.

It's a prime number.

So no matter what kind
of multicolored string

you start with, it will
always take five rotations,

or bead swaps, to return to itself.

The cycle length of every
string must be five.

Well let's check.

First we'll build all possible strings

and remove the two monocolored strings.

Then we separate the strings into groups

which belong to the same style,

and build a single earring for each style.

Notice that each earring
rotates exactly five times

to complete a cycle.

Therefore, if we glued all
the strings into rings,

they must split into equal
sized groups of five.

But then he goes one step further.

Currently he is only using
two colors, but he realizes

this must hold with any number of colors.

Because any multicolored
earring with a prime number

of beads, P, must have
a cycle length of P,

since primes cannot be broken
into equal sized units.

But if a composite
number of beads are used,

such as six, we will
always have certain strings

with shorter cycle lengths,
since it's actually

built out of a repeating
unit, and therefore

will form smaller groups.

And amazingly he just stumbled
onto Fermat's Little Theorem.

Given A colors and strings
of length P, which are prime,

the number of possible
strings is A times A

times A, P times, or A to the power of P.

And when he removed the
monocolored strings,

he subtracts exactly A strings,

since there are one for each color.

This leaves him with A to the
power of P minus A strings.

And when he glues these strings together,

they will fall into groups of size P,

since each earring must
have a cycle length of P.

Therefore, P divides A to
the power of P minus A.

And that's it.

We can express this statement
in modular arithmetic too.

Think of it, if you
divide A to the power of P

by P, you will be left
with a remainder of A.

So we can write this
as A to the power of P

is congruent to A mod P.

And here we have stumbled onto one

of the fundamentals
results in number theory

merely by playing with beads.