cinelli wrote:Using no more than a non-programmable calculator, find the prime factors of the following 20-digit number:
12 318 876 808 768 112 319
I've come to this thread way too late, but to give the most elegant way of expressing the solution I know: the well-known "a number is divisible by 9 if the sum of its digits is divisible by 9" test generalises to any base as "in base B, a number is divisible by B-1 if the sum of its digits in divisible by B-1".
Apply that in base 10,000,000,000, in which the number concerned has two 'digits', namely 1,231,887,680 and 8,768,112,319. They add to 9,999,999,999, so it is divisible by 9,999,999,999 - specifically, it is 9,999,999,999 * 1,231,887,681. Then apply it in base 100,000 to each of those factors and you find they're both divisible by 99,999, leading to the factorisation 100,001 * 99,999 * 12,319 * 99,999.
Taking out the obvious factors of 3*3 from each occurrence of 99,999, and the easy factor of 11 from 100,001 (using the fairly well-known test that a number is divisible by 11 if the sum of its even digits differs from the sum of its odd digits by a multiple of 11) gets us to 3 * 3 * 3 * 3 * 11 * 9,091 * 11,111 * 11,111 * 12,319. It's then a matter of brute force trial division with the calculator as far as I am aware, as psychodom indicates, but with the biggest of those factors being less than 111^2 = 12,321, not all that much force is required - it's a bit tedious, but with there only being 29 prime numbers under 111, nothing worse than that.
Gengulphus