Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fermat's Little Theorem (2013) [video]

youtube.com

Post reply on HN
Print view View original

21–28 of 28 posts

Re: Fermat's Little Theorem (2013) [video]

#21

Post by gjm11 »

S4M wrote: post #16

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.

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.

Re: Fermat's Little Theorem (2013) [video]

#22

Post by jonsen »

ColinWright wrote: post #20
jonsen wrote: post #19

Earlier quoted context omitted.

My point was, that the way notation is just thrown at you in the video can only add to the phobia for the uninitiated. The video is clearly aiming at basic pedagogic explanation, and it is all destroyed in the end. The math versed who easily read that math without explanation do not need the bead juggling. The pedagogy fails in the end.

The explanation of the theorem has got as far as it can go by that point. There's a choice to be made. Avoiding notation means that those who could now connect the explanation with things they have already seen is lost. Avoiding notation also means that it's just all been a show, and there's no real take away except that, well, this guy played with beads an counted things. If someone is truly notation-phobic then the…

Yes, we agree a long way. I'm sure the video works well in its intended greater context, as you describe here. My points are about taking the video at face value out of context, which is probably what lead to clear-as-muds comment.

Re: Fermat's Little Theorem (2013) [video]

#23

Post by S4M »

gjm11 wrote: post #21
S4M wrote: post #16

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.

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: su…

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.

Re: Fermat's Little Theorem (2013) [video]

#24

Post by baggers »

ColinWright wrote: post #14
baggers wrote: post #11

Earlier quoted context omitted.

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…

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.

Thanks, that's good to know.

Re: Fermat's Little Theorem (2013) [video]

#25

Post by jacderida »

zurtri wrote: post #4

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.

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

Re: Fermat's Little Theorem (2013) [video]

#26

Post by JadeNB »

ColinWright wrote: post #15
JadeNB wrote: post #7

Earlier quoted context omitted.

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... .

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

Heh, sorry about that. I was on a low bandwidth connection, and couldn't watch the video.

Re: Fermat's Little Theorem (2013) [video]

#27

Post by britcruise »

jonsen wrote: post #22
ColinWright wrote: post #20

Earlier quoted context omitted.

The explanation of the theorem has got as far as it can go by that point. There's a choice to be made. Avoiding notation means that those who could now connect the explanation with things they have already seen is lost. Avoiding notation also means that it's just all been a show, and there's no real take away except that, well, this guy played with beads an counted things. If someone is truly notation-phobic then the…

Yes, we agree a long way. I'm sure the video works well in its intended greater context, as you describe here. My points are about taking the video at face value out of context, which is probably what lead to clear-as-muds comment.

Hey there, I created this video. It was just one part of a longer lesson I was trying on "Random Algorithms" because it involved Fermat's primality test...so in this case we really needed that formula to try it out which is why I added it at the end.

https://www.khanacademy.org/computing/computer-science/crypt...

Re: Fermat's Little Theorem (2013) [video]

#28

Post by CurtMonash »

baggers wrote: post #11
CurtMonash wrote: post #8

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, an…

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…

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.

Post reply on HN