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.

## Computer science theory

### Course: Computer science theory>Unit 2

Lesson 7: Randomized algorithms

# 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?

• 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? •   The ≡ sign is the proper symbol for congruence relation.
The ≅ sign is the proper symbol for geometric congruence.
• What does "mod" mean in this video? I think it's a part of higher level math, but I'm not sure. • I didn't get the video in general • Can anyone give me a concise and clear explanation regarding the proof given quite recently to Fermat's final theorem? • 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
• How can Fermat's little theorem help us in prime or composite, but more importantly, how can it help us in prime factorization? • In , the 7th and 9th bead combinations are identical. Is these a mathematical reason for this, or did he just make a mistake? • 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. • 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
• At , why do you subtract exactly 'a' string(s), why wouldn't it be 2a? • Didn't a lot of early math come from playing with rocks and things ?  