Wednesday, November 11, 2009

Carmichael orrery

It occurs to me that it ought to be possible to demonstrate pseudoprimality with a purely mechanical device.

For instance, we could demonstrate 2^560%561 with 560 2:1 (or equivalently, 35 65536:1) gear amplifications followed by a 1:561 reduction, and rotate the input shaft once to see the output gear rest at 1. Of course, 2^560 ~ 3.8E168, so you'd have to turn the crank fairly hard.

You could also do a single 65536:1:561 train cranked n times for individual 65536n (mod 561) reductions, and repeat 35 iterations for 65536^35%561.

That would provide a (false) Fermat witness of 2. Simile for the other integers < 561. Not very interesting so far, but perhaps there's something more elegant.

No comments: