The 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….)
A 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.
https://en.wikipedia.org/wiki/Lucas_primality_test and https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality...