Timeline for Christening Fermat's Little Theorem

4 events

when toggle format	what		by	license	comment
Aug 20, 2010 at 15:01	vote	accept	Franz Lemmermeyer
Jul 28, 2010 at 0:20	comment	added	KConrad		I also have another suggestion: show that Fermat's little theorem is used in RSA. Nearly all books I have seen that discuss RSA use Euler's theorem, which compels the authors to say RSA requires that the message to be encoded is rel. prime to the modulus. This is wrong: RSA works for all numbers. That is, if p and q are different primes and d and e are positive integers such that de = 1 mod(p−1)(q−1) then $x^{de} = x \bmod pq$ for all integers $x$. To prove this, work mod $p$ and mod $q$ separately and use Fermat. Even the original RSA paper uses Fermat!
Jul 28, 2010 at 0:09	comment	added	KConrad		Stick to the standard name, however much it bothers you right now. (Is there any major mathematical language in which it is not called his little theorem?). I do have a different suggestion too. The first time you introduce the congruence, please describe it using correct quantifiers: $a^{p-1} = 1 \bmod p$ for all $a \not= 0 \bmod p$ (or $a^p = a \bmod p$ for all $a \bmod p$). That is the essential point. Last fall I asked my class what Fermat's little theorem is (we had discussed it in the previous class). One said "if $p$ is prime then for some $a$, $a^{p-1} = 1 \bmod p$." Ouch.
Jul 27, 2010 at 21:23	history	answered	Tilman	CC BY-SA 2.5