If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content
Current time:0:00Total duration:6:06

Video transcript

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 3 he begins by figuring out all possible styles well 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 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 mono colored strings since he's only building multicolored earrings then he glues them all together to form rings he was assuming you'd end up with six different earrings but something happened he can 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 hmm 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 four beads he can choose from two colors for each bead so 2 times 2 times 2 times 2 equals 16 then he removes the two mono colored 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 on to 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 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 5 well let's check first we'll build all possible strings and remove the two mono colored 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 5 times to complete a cycle therefore if we glue all the strings into rings they must split into equal sized groups of 5 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 Prime's 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 on to form AHS 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 ^ P and when he removed the mono coloured 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 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 to think of it if you divide a to the power of P by P you will be left with a remainder a so we can write this as a to the power of P is congruent to a mod P and here we have stumbled on to one of the fundamental results in number theory merely by playing with beads