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

Fermat's little theorem

Introduction to a key result in elementary number theory using a visualization with beads. Created by Brit Cruise.

Want to join the conversation?

  • leaf green style avatar for user 福龍丸
    In the geometry videos by Sal Khan, the 'congruent' symbol appears as a = sign with a squiggly line on top (≅). But here Brit uses ≡, which I know to be read as 'identical to'. A confusion of terms, a legitimate free interchange of the terms, or something more?
    (46 votes)
    Default Khan Academy avatar avatar for user
  • leaf yellow style avatar for user ♦SamuelM♦
    What does "mod" mean in this video? I think it's a part of higher level math, but I'm not sure.
    (18 votes)
    Default Khan Academy avatar avatar for user
  • marcimus pink style avatar for user Samu
    I didn't get the video in general
    (8 votes)
    Default Khan Academy avatar avatar for user
  • leaf red style avatar for user Claudia the Scientist/Amazon with 12 guns_shut up
    Can anyone give me a concise and clear explanation regarding the proof given quite recently to Fermat's final theorem?
    (Note: I do not mean Fermat's little theorem and please don't post any links; those links always lead to the long convoluted and non-concise answers)
    (3 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      I can't give you a clear and concise explanation of the proof of Fermat's Last Theorem, but perhaps I can explain to you why it is such a difficult (if not impossible) task.

      To provide a concise and clear explanation to the proof of Fermat's Last Theorem would essentially require an elementary proof. An elementary proof is a proof that only uses basic mathematical techniques. Unfortunately, an elementary proof to Fermat's Last Theorem has not been found. If someone finds an elementary proof to it, they will become rich and famous.

      The proof that Andrew Wiles produced for Fermat's Last Theorem in 1995 is a proof, but it is not an elementary proof. It is over 100 pages and involves advanced, cutting edge mathematics. Most of the material involved in the paper requires the equivalent of a graduate level degree in mathematics to understand, and is hard to simplify in a meaningful way.

      If you are really interested in learning more about the proof, may I suggest:
      -"Fermat's Enigma" by Simon Singh would give one a better "feel" for what the proof was about. (no degrees required to read this, only a love of math)
      -"Invitation to the Mathematics of Fermat-Wiles" by Yves Hellegouarch would give one the necessary mathematical background to understand the proof (the book assumes that the reader has an undergraduate degree in mathematics).

      Hope this makes sense
      (17 votes)
  • winston default style avatar for user 🌟♔John W
    How can Fermat's little theorem help us in prime or composite, but more importantly, how can it help us in prime factorization?
    (5 votes)
    Default Khan Academy avatar avatar for user
  • aqualine ultimate style avatar for user Aqualine
    In , the 7th and 9th bead combinations are identical. Is these a mathematical reason for this, or did he just make a mistake?
    (5 votes)
    Default Khan Academy avatar avatar for user
  • female robot grace style avatar for user S J
    If I divide a^p by p, why will I be left with a remainder of a?
    sorry if this seems stupid, but I can't seem to get it.
    (3 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      There are no stupid questions

      Fermat's little theorem is often expressed as:
      a^p mod p = a mod p
      or equivalently as
      a^(p-1) mod p = 1
      where p is a prime number

      "x mod y" is just the remainder that we get when we divide "x" by "y", so:
      "a^p mod p" is the remainder we get when we divide "a^p" by "p"
      "a mod p" is the remainder we get when we divide "a" by "p"

      If "a<p" then "a mod p = a", which means "a^p mod p = a", which means "a^p" divide by "p" will give you a remainder of "a".
      If "a>= p" then "a^p" divide by "p" will give you the same remainder as dividing "a" by "p".

      Hope this makes sense
      (4 votes)
  • spunky sam blue style avatar for user Kyle H
    At , why do you subtract exactly 'a' string(s), why wouldn't it be 2a?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • piceratops ultimate style avatar for user Rowain Hardby
      Because a is the amount of colors we're using.
      For the video, we had two colors: yellow, and black. We also had two monochromatic strings: entirely yellow, and entirely black.
      In general, each new color we add will add one string we need to remove, namely the string composed entirely of that color.
      (1 vote)
  • leafers ultimate style avatar for user Tracy Dunn
    Didn't a lot of early math come from playing with rocks and things ?
    (2 votes)
    Default Khan Academy avatar avatar for user
  • mr pink red style avatar for user Federico.Jover
    I know this theorem has a % of error, but if we used base 3, we get an error just with number 6 (or maybe the error is mine)
    a= 3 p= 6 Mod 3 ¿Prime?

    Thanks
    (2 votes)
    Default Khan Academy avatar avatar for user

Video transcript

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.