[dncouprc] Pedagogical examples of primality testing

If p is prime, then a^(p-1) ≡ 1 (mod p) by Fermat's Little Theorem. However, the converse has exceptions (though the exceptions can be worked around with the Miller-Rabin primality test).

341 = 11 * 31 is composite, but 2^340 ≡ 1 (mod 341), because 2^(340/4) = 2^85 ≡ 32 (mod 341) is a nontrivial square root of unity modulo 341: 32^2 = 1024 = 341*3 + 1. Note that 32 ≡ -1 (mod 11) ≡ 1 (mod 31)

91 = 7 * 13 is composite, but 3^90 ≡ 1 (mod 91), because 3^45 ≡ 27 (mod 91) is a nontrivial square root of unity modulo 91: 27^2 = 729 = 91*8 + 1. Note that 27 ≡ -1 (mod 7) ≡ 1 (mod 13)

15 = 3 * 5 is composite, but 4^14 ≡ 1 (mod 15), because 4^7 ≡ 4 (mod 15) is a nontrivial square root of unity modulo 15: 4^2 = 15 + 1. Note that 4 ≡ 1 (mod 3) ≡ -1 (mod 5). The other nontrivial square root is 11, and 11 ≡ -1 (mod 3) ≡ 1 (mod 5). The square roots sum to 15.

For bases 2 through 30, the sequence where Miller-Rabin first helps over the plain Fermat test is: 341 91 15 217 35 561 21 205 33 15 65 21 39 341 51 45 85 45 57 55 69 33 115 39 45 65 45 35 91