(I got this material from a nice article by Arthur Benjamin here.)
Conway suggested the following trick to determine if a number is divisible by each of the following:
2,3,5,7,11,17,19,31
Note that
\( 152=2^3\times 19\)
\(153 =3^2 \times 17\)
\(154=2 \times 7 \times 11\)
\(155=5 \times 31\)
\(156=2^2 \times 13 \)
Here is the Div trick:
a) Input N
b) Divide N by 150 and note the remainder. So
N=150q+r
r=N-150q
Subtract q from r a few times:
Note that
r-q = N-150q-q = N-151q
r-2q=N-152q
AH HA!- if 19 divides r-2q then 19 divides N. So divide r-2q by 19. (Note that r-2q is much smaller than N. Smaller enough to make this technique feasible? That is the question!)
r-3q=N-153q.
AH HA!- if 17 divides r-3q then 17 divides N. So Divide r-3q by 17.
r-4q=N-154q
AH HA- if 11 divides r-4q then 7 divides N. So Divide r-4q by7.
r-5q=N-155q
AH HA- if 31 divides r-5q then 31 divides N. So Divide r-5q by 31.
r-6q=N-156q
AH HA- if 13 divides r-6q then 13 divides N. So Divide r-6q by 13.
Complexity with 1 division, 6 subtractions and 6 divisions of small numbers (r\le 150 and q\le N/150)
you find out the divisibility by 7,13,17,19,31. For 2,3,5,11 there are well known tricks to use. OR you can test those as well by doing (for example) dividing r-4q=r-154 by 11.
Some Points
1) Is this method faster than just dividing N by the numbers (and using tricks for 2,3,5,11)? You would need to get into addition being faster than division, and look at the size of the numbers.
2) Is this method practical? For hand calculation YES. For computers it would be easy to code up but the main question of this post: is it better than just dividing N by numbers.
3) Are there larger runs of numbers that pick up more divisors? Yes. We present one. The order will look funny but we explain it later.
\(2000=2^4 \times 5^3 \) (you could skip this one, though dividing by 2000 is easier than by 2001)
\(2001=23\times 29\times 3\) (would divide N-2q by both 23 and 29)
\(2002=7\times 11\times 13\times 2\)
\(1998=37\times 54\)
\(2006=17\times 29\times 2\)
\(2010=67\times 30\)
\(2014=19\times 53\times 2\)
\(2013=61\times 33\)
\(2015=31\times 65\)
\(2009=41\times 49\)
\(2021=43\times 47\)
The order was suggested by Conway so that algorithm at every step adds or subtracts one of q, 2q, 4q, 6q, 8q, 12q. So after you get q you can compute these values.
I leave it to the reader to count the number of divisions, subtractions, and size of the numbers involved.
4) For cracking RSA this technique is useless since RSA uses numbers of the form pq where p and q are large primes. For factoring randomly generated numbers I would be curious if this method is better than just dividing by numbers.
5) Project: find other sequences like those above that cover more prime factors.
