Fermat's Little Theorem (2013) [video]

https://www.youtube.com/watch?v=XPMzosLWGHo&feature=youtu.be

by ColinWright • 11 years ago

77 27 11 years ago

Reminds me of Burnside's Lemma (https://en.wikipedia.org/wiki/Burnside%27s_lemma).

JadeNB3• 11 years ago

Indeed, the idea of the proof of Burnside's lemma is essentially the same as what is often called the necklace-counting proof of Fermat's little theorem: https://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_little_th... .

ColinWright5• 11 years ago

Yes, and the submitted video is that necklace counting proof, hence the video reminding them of it.

mrcactu5• 11 years ago

Fermat Little Theorem is one of my favorite results. Here is a short proof by Lionel Levine it is only 2 pages http://www.math.cornell.edu/~levine/fermat.pdf

He also get formulas like: pq divides a^pq - a^p - a^q + a

JadeNB3• 11 years ago

He also get formulas like: pq divides a^pq - a^p - a^q + a

Incidentally, assuming you mean p and q to be distinct primes, this latter formula is almost just another instance of Fermat's little theorem: we have that q divides (a^p - a)^q - (a^p - a) and p divides (a^q - a)^p - (a^q - a) (that's the little theorem), and then that q divides (a^(pq) - a^q) - (a^p - a)^q and p divides (a^(pq) - a^p) - (a^q - a)^p (that's essentially the binomial theorem); so both p and q divide a^(pq) - a^p - a^q + a.

zurtri• 11 years ago

There is an awesome book entitled "Fermat's Enigma: The Epic Quest to Solve the World's Greatest Mathematical Problem"

(you can google it for a link to a supplier)

Well worth the read. Tells the whole story of the famous "Fermat's last Theorum" problem and is extremely well written.

curryhoward• 11 years ago

You may know this, but for those who might not: Fermat's Last Theorem and Fermat's Little Theorem are two totally different theorems (both about number theory).

Fermat's Little Theorem: For any integer a and prime p, a^p is congruent to a mod p.

Fermat's Last Theorem: For any integer n > 2, there are no integers a, b, and c such that a^n + b^n = c^n.

The Little Theorem has been known for hundreds of years and is easy to prove. The Last Theorem, on the other hand, was only finally proven in 1994 by Andrew Wiles after countless failed attempts by mathematicians before him.

CurtMonash3• 11 years ago

My best friend from graduate school (which was the Harvard Math department at a time Wiles was an assistant professor) used to stay with me when he visited his employer in NYC after moving to Israel. He would take an overnight flight and arrive, quite blearly, early in the morning. The day of a visit, the NYT had the story. And so I greeted him at the door to my apartment, not with my usual warm hello, but rather the words "Wiles proved Fermat's Last Theorem".

jacderida• 11 years ago

Simon Singh, the guy who wrote that book, also made a very cool documentary on it. It used to be on YouTube, but it was removed by the BBC (they have a very annoying habit of removing educational content from YouTube). It's on the BBC iPlayer.

There is also an excellent long interview with Ken Ribet, who proved a result that inspired Wiles to take on the proof: https://www.youtube.com/watch?v=nUN4NDVIfVI

CurtMonash3• 11 years ago

I love Fermat's Little Theorem, both for its own sake and because it's an intermediate step in proving the Two Squares Theorem. My equivalent to "counting sheep" used to be to review the proof of the TST.

The simplest proof I know of Fermat's Little Theorem is induction, assuming that we already know the Binomial Theorem. Suppose a^p == a. (== is my symbol for "is congruent to mod p" in this post.) Expand (a+1)^p, and note that every binomial coefficient except the first and last has p in the numerator but not the denominator. Hence (a+1)^p == a^p+1 == a+1.

Cleaning up the proof from there is trivial.

baggers2• 11 years ago

This question is as someone who is mathematically curious but not yet adept.

In programming we slowly gain a big grab-bag of patterns and approaches to certain problems and build an intuition of what to apply where. It doesn't nearly cover your full experience but helps break problems down.

Do you find there is an analog to this with theorems? If so what's the essentials from your 'grab bag' and, beyond just reading more, what practices help build your feeling of where to use them?

ColinWright5• 11 years ago

Yes, there is, but I've never thought of it in those terms, and I can't enumerate them easily. There are techniques to apply, approaches to try, and connections to make that can help. But I don't know any way of building intuition other than by actual doing.

Tim Gowers writes well about how to build mathematical knowledge, techniques, and a library of tools.

CurtMonash3• 11 years ago

I haven't been a mathematician for decades, and in particular I don't recall the details in the examples I'm about to give. :) But I'd say yes up to a point. In particular, one matches problems to generalized patterns, which in math often has the feel of transforming a problem into another form.

1. If you're going to take a test for school, you can recognize patterns pretty easily. For example, Harvard has a 3-day Qualifying Exam as a PhD requirement, given twice a year. Once, after looking at the exam pages for the first two days, I said "Hmm, there hasn't been a Schwarz Reflection Principle question yet."

The next evening, I got a nice hug from Lisa Mantini. :)

2. If you're doing actual research math, it's of course much harder. For example, the theorem in my thesis was scooped by a few months by Neyman and Mertens. What's more, they did it as a special case of a fixed-point theorem, while I just proved it by brute force.

And now some simpler anecdotes from my undergraduate days.

3. In my E&M course, we were supposed to work out fields for a cylindrical wire with an off-center cylindrical hole. This was a LOT easier in curvilinear coordinates than Euclidean. When I showed that to the professor in his office, he literally stood up and applauded.

4. In an abstract algebra course, there was a typo in the book for one of the exercises as to whether a certain polynomial was reducible. I solved the hard form by transforming the problem into one about a polynomial with matrix variables.

I took that story with me when I went to graduate school. Ron Livne's eyes lit up, and he transformed it again into something about -- well, into something about transformations on the polynomial's complex roots.

mixedmath• 11 years ago

There is an elementary number theory textbook by the famed number theorist and Ramanujan scholar Dr. George Andrews called Number Thoery, http://www.amazon.com/Number-Theory-Dover-Books-Mathematics/...

It contains proofs of very many results from elementary number theory, like Fermat's Little Theorem here. The reason this book is different from any other is because the proofs are all combinatorial, like counting beaded necklaces or otherwise. It is also a Dover book, meaning it costs very little. It is also one of the books I used as reference to create the elementary number theory course that I sometimes teach.

clear-as-mud• 11 years ago

This is why I despise mathematicians. Everything was going smoothly, until they obscured the whole concept behind that awful notation. Why? Notation is the destroyer of understanding.

Letter, pipe, letter, superscript. Yeah, real nice. Clear as mud.

ColinWright5• 11 years ago

If you choose not to invest the time learning the notation, you will forever be limited to writing everything out in longhand. Try reading maths from the 1600s or 1700s and you will come to appreciate the value of notation.

And don't start down the road of thinking everything can be made unambiguous. It is context dependent, and always will be. Look at computer code, look at something deep in the bowels, and tell me what the "+" sign means. Is it integer? Float? List? Or has it been over-ridden by some library you've loaded somewhere else? Even finding where it's been defined can be a challenge. You have to trust that the author has played fair, and that your intuitive understanding that "+" is doing something consistent with the concept of "+" in numbers is close enough.

You could write out all the math notation in longhand, but it won't aid your understanding. If you actually follow the video then you will follow the notation. But there's a reason why we say "read like math" - it takes time and effort to gain understanding. It's not a novel, it's not a comic.

    The only way to learn mathematics
        is to do mathematics.
            -- Paul Halmos

    "There is no Royal Road to geometry,"
        -- Euclid, in reply to King Ptolemy's
           request for an easier way of learning
           mathematics.

jonsen3• 11 years ago

Well said and all, but notation is a destroyer of understanding, if you are not well versed in reading math. There is a very abrupt jump in the video from the pleasant down to earth demonstration using picture language when the "cold" math notation is just thrown at you in the end.

S4M2• 11 years ago

Am I the only one who doesn't get it? My background is in maths and I am (was) able to prove formally Fermat's little theorem, but I got lost around minute 3:08, and am not clear why the fact that 5 is prime means that any combination must take 5 rotations to return to itself. I can see that it is true but the reason is not clear to me.

gjm11• 11 years ago

Suppose the smallest (positive) number of rotations it takes to return is d. Then the numbers of rotations that have that effect are 0, d, 2d, 3d, etc. But clearly 5 rotations take you back where you started, so 5 is one of those numbers; that is, 5 is a multiple of d. Since 5 is prime this means either d=1 or d=5.

My second sentence above is a bit of a handwave. If you want to get formal about it, here's one way: suppose d isn't a multiple of 5; then note that there's an integer a such that ad = 1 (mod 5). Then ad rotations have the same effect as 1 rotation; but ad rotations do nothing, so d=1.

Now the handwaving is concentrated in the "then note that ..."; if that isn't sufficiently obvious, consider ad for a=0,1,2,3,4 and note that no two can be equal mod 5 because if ad=bd mod 5 then (a-b)d is a multiple of 5, but neither factor is a multiple of 5 and 5 is prime. So: five numbers, all of them different mod 5, so we must have one each of each congruence class mod 5; in particular, one of them is 1 mod 5.

S4M2• 11 years ago

Yes, that's a good explanation (I suspect your first paragraph is at the core of Fermat's little theorem's demonstration), it's just a shame it was left out of the video - but maybe because this part would require its own video.

Fermat's Little Theorem (2013) [video]

Related Stories