How did Cole factor $2^{67}-1$ in 1903?

The paper by Cole "On the factoring of large numbers." BAMS (1903) discusses this.

Summarizing what Cole says for my own understanding: By methods which he doesn't make clear to me, Cole found solutions to $x^2 \equiv a \bmod N$ for many small values of $a$ and convinced himself (but not rigorously) that many other $a$ were not achievable. This gave many congruence conditions on possible divisors of $N$. In this manner, he was rapidly able to filter the integers up to $16$ million down to just a few trial divisors, none of which worked. (Note that it is okay if he winds up trying some non-prime divisors in the process.)

At this point, he used his data in a different way. Suppose that $N=pq$ and look at one of his small values of $a$, for example $a=-7$. Since he knew $-7$ was square modulo $N$, we deduce that $p$ and $q$ are each $ 1$ , $2$ or $4 \bmod 7$ and, since $2^{67}-1 \equiv 1 \bmod 7$, we get that $(p,q)$ is $(1,1)$, $(2,4)$ or $(4,2) \bmod 7$. This means that $(p+q)/2 \equiv 1$ or $3 \bmod 7$. In this way, he obtained many modular conditions on $(p+q)/2$, giving a few possibilities. For each possibility $x$, he checked whether $x^2-N$ was square. When he tried the right option, he had $x^2-N = ((p+q)/2)^2 - N = ((p-q)/2)^2$ and won.

You assume that he did his computations by hand, but that's not a necessity. At the time, mechanical calculators (arithmometers) were widely available. It's not at all unusual that the kind of person who devotes Sundays to factoring would own one.

These machines are orders of magnitude faster and more precise than doing computations by hand. This model from 1875 could handle 20-digit numbers, for instance. ($2^{67}$ has 21 digits.)

Multiplying two numbers on one of them takes a few seconds. To multiply 761838257287 by 193707721, for instance (assuming they fit on the machine, which isn't the case for the machine in the picture --- it can multiply two ten-digit numbers at most, natively), you'd have to:

• reset the machine by turning a certain small reset crank or switch.
• slide up and down the 10 linear switches in the lower-right part, one by one, to the positions corresponding to the digits of 761838257287.
• turn the crank one time, then slide the upper slab to the right by one notch, then turn the crank again 2 times, then move the slab, then turn it 7 times, and so on for each digit of the second number, for a total of 1+9+3+7+0+7+7+2+1 = 37 turns. The number of turns made in each position is displayed on an indicator, to reduce mistakes. (those ten tiny circular holes on top of the linear switches, I think).
• then you can read off the digits of the result in the upper row of 20 rotating indicators.

Similarly, to divide (with remainder) a certain number $A<10^{20}$ by a $B<10^{10}$, you can do the following, which directly mimics grade school division:

• set up the machine so that the top moving row shows the number $A$
• slide the upper slab to the right a certain number $k$ of tims, so that the most significant digit of $A$ is aligned with the most significant digit of $B$.
• turn the crank in the reverse direction between 0 and 10 times; each turn subtracts $10^k B$ from $A$. Stop when you'd reach below zero. In practice, these machines work modulo $10^{20}$, and many models make a bell sound when you move below zero; so in practice you'd turn the crank until you hear the bell, then make one turn back.
• slide the upper slab one notch to the left, and continue by subtracting multiples of $10^{k-1}B$ from the number in the top row. Continue until the upper slab is back to the original position (which means you're subtracting multiples of $10^{0}B$ and can't slide it left anymore. Then you can read the remainder on the top row, and the quotient on a tiny (barely visible here) row of numbers below it, which kept track of how many turns were made in each position.

I don't have much manual skill with these machines, but it looks like the method could be performed in a completely mindless way --- turn the crank until you hear the bell, turn it back one turn, slide left, repeat.