Randomized Algorithms
Fermat's Little Theorem Introduction to a key result in elementary number theory using a visualization with beads
⇐ Use this menu to view and help create subtitles for this video in many different languages.
You'll probably want to hide YouTube's captions if using these subtitles.
- Bob discovered something very interesting
- while making multi-coloured ear rings 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 3, 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?
- Well, with 2 colours and 3 beads, there are 3 choices,
- each from two colours.
- So, 2 x 2 x 2 = 8 possible unique strings.
- Then he subtracts the strings which have only one colour.
- or mono-coloured strings
- since he is only building multi-coloured 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 can no longer tell the difference between most of them.
- It turns out he has only two styles
- because each style is now part of a group with 2 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 multi-coloured strings
- divides evenly into groups of size 3.
- Hm. 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
- and with 4 beads he can choose from 2 colours for each bead,
- so 2 x 2 x 2 x 2 = 16.
- Then he removes the two mono-coloured 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
- devides into styles.
- If strings are of the same style,
- it means that you can form one into the other
- simply by grabbing beads from one end,
- and sticking them onto the other end.
- There is one style which has only two members.
- This is because it is built out of
- a repeating unit of length 2,
- 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 5?
- Will they break into an equal number of each style?
- Wait! Suddenly he realises he does not need to build them
- in order to find out! It must work,
- since 5 cannot be made up of a repeating pattern,
- because 5 cannot be broken into equal parts.
- It's a prime number.
- So, no matter what kind of multi-coloured 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 mono-coloured strings.
- Then we separate the strings into groups
- which belong to the same style
- and build a single earring for each style.
- Notic that each earring rotates exactly 5 times
- to complete a cycle.
- Therefore, if we glue all the strings into rings,
- they must split into equal-sized groups
- of five.
- But then he goes a step further.
- Currently he is only using two colours,
- but he realises this must hold with any number of colours.
- Because any multi-coloured ring with a prime number of beads P
- must have a cycle lenght of P
- since primes cannot be broken into equal-sized units.
- But if a composite number of beads are used
- such as 6, he will allways have certain strings
- with shorter cycle lengths
- since it is built out of a repeating unit
- and therefore will form smaller groups.
- And amazingly, he just stumbled on to Fermat's Little Theorem.
- Given A colours
- ands strings of length P which are prime
- the number of possible strings
- is a x a x a, p times, or
- a to the power of p
- And when he removed the mono-coloured strings
- he subtracts exactly a strings
- since there are one for each colour.
- This leaves him with (a^p)-a strings
- And when he glues these strings together
- they will fall into groups of size p
- since each ring must have a cycle length of p
- Therefore, p divides a^p-a
- And that's it!
- We can express this statement in modular arithmetic too
- Think of it, if you divide a^p by p
- you will be left with a remainder a
- So we can write this as
- And here we have stumbled on to
- one of the fundamental number results in number theory,
- merely by playing with beads.
Be specific, and indicate a time in the video:
At 5:31, how is the moon large enough to block the sun? Isn't the sun way larger?
|
Have something that's not a question about this content? |
This discussion area is not meant for answering homework questions.
Discuss the site
For general discussions about Khan Academy, visit our Reddit discussion page.
Flag inappropriate posts
Here are posts to avoid making. If you do encounter them, flag them for attention from our Guardians.
abuse
- disrespectful or offensive
- an advertisement
not helpful
- low quality
- not about the video topic
- soliciting votes or seeking badges
- a homework question
- a duplicate answer
- repeatedly making the same post
wrong category
- a tip or feedback in Questions
- a question in Tips & Feedback
- an answer that should be its own question
about the site
Share a tip
Suggest a fix
Have something that's not a tip or feedback about this content?
This discussion area is not meant for answering homework questions.