2 ms·
My Math "FizzBuzz" question is: prove Fermat's Little Theorem and Wilson's Theorem. Even those with very rudimentary understanding of modular arithmetic (comin
by sheetjs 13y ago
My Math "FizzBuzz" question is: prove Fermat's Little Theorem and Wilson's Theorem. Even those with very rudimentary understanding of modular arithmetic (coming from non-math backgrounds) can prove both with some pointers (obviously the process is interactive)
- crntaylor 13y agoInteresting. I think the proof of Wilson's theorem is easy enough to be accessible for a non-mathematician - for non-prime n you can find a pair of numbers in the product (n-1)! that are congruent to 0 (mod n), and if n is prime then you pair up numbers in the product with their inverses until you are left with ±1. But I can't think of a similarly low-level proof of Fermat's Little Theorem. Is there an obvious one I'm missing?
- ColinWright 13y agoConsider Q to be the product (p-1)!. Then consider the product a.2a.3a.4a...(p-1)a. These are the same items rearranged, because a has an inverse. But the product is also a^(p-1).(p-1)! by commutativity. So a^(p-1)=1 (mod p). There's a clever idea in there, to consider prod(ka) for fixed a and k=1..(p-1). Not finding the clever idea means you won't prove it. Finding the clever idea is tricky. Once you know the clever idea the proof is trivial.