7 ms·
Fascinating stuff! How was it demonstrated that 2^67 - 1 was composite without providing a factorization?
by dduugg 4y ago
Fascinating stuff! How was it demonstrated that 2^67 - 1 was composite without providing a factorization?
- svat 4y agoThe brilliance of Édouard Lucas: see "Lucas primality test" (for general N, when you can factor N-1) and "Lucas–Lehmer primality test" (for Mersenne numbers N). Both work for M_67. There's a nice account somewhere of how Lucas carried out the latter test with a 127x127 chessboard to prove that M_127 is prime. For M_67, Lucas had done the calculations and declared it composite, and there was confirmation from another author. And Cole seems to have trusted this too. (I mention this because Shallit and Williams point out that on some occasions Lucas seems to have wavered in his confidence, for some reason….) https://en.wikipedia.org/wiki/Lucas_primality_test https://en.wikipedia.org/wiki/Lucas_primality_test and https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality...
- formerly_proven 4y ago> "Lucas–Lehmer primality test" Familiar to overclockers because that's what many use for stability testing of CPUs!
- deleted 4y ago[deleted]
- throwaway81523 4y agoA Fermat test with base 3 shows the number to be composite. I think that could be done in a day or so of hand calculation. That amounts to a brute force method and as svat says, there are better ways. The Fermat test only shows that it can be done without much subtlety.