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