News for hackers. Stuff that matters.
Re:Fermat's Little Theorem (2013) [video] by S4M on Monday August 03, 2015 @05:53AM (#9994729)
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.
Re:Fermat's Little Theorem (2013) [video] by gjm11 on Monday August 03, 2015 @07:22AM (#9994984)
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] by S4M on Monday August 03, 2015 @07:36AM (#9995027)
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.