Show that any integer greater than 10 whose digits are all members of {1, 3, 7, 9} has a prime factor ≥ 11.
Solution
Such a number cannot be divisible by 2 (or its last digit would be even) or by 5 (or its last digit would be 0 or 5). So if the result is false then the number must be of the form 3m7n for non-negative integers m, n. But we claim that a number of this form must have even 10s digit.
It is easy to prove the claim by induction. It is true for 3 and 7 (the digit is 0 in both cases). But if we multiply such a number by 3 or 7, then the new 10s digit has the same parity as the carry from the units digit. But multiplying 1, 3, 7, 9 by 3 gives a carry of 0, 0, 2, 6 respectively, which is always even, and multiplying by 7 gives a carry of 0, 2, 4, 6, which is also always even. So the new number also has an even 10s digit.
© John Scholes
jscholes@kalva.demon.co.uk
5 Aug 2002