Prove that all palindromic prime numbers greater than 11 have an odd number of digits.
Rough proof outline (need pure mathematician
s to make it rigorous
- 1001 = 91 * 11; 100,001 = 9,091 * 11; 10,000,001 = 909,091 * 11 (this can be proved with mathematical induction)
- All palindromic numbers with an even number of digits can be trivially represented by sums of terms of the form 1000..0001 * 10^x. For example, 13377331 = 1 * 10000001 + 3 * 100001 * 10 + 3 * 1001 * 100 + 7 * 11 * 1000.
- All these terms are multiples of 11; the sum also must be a multiple of 11 and is therefore not prime. The contrapositive of this is that any palindrome that is not a multiple of 11 must have an odd number of digits; QED.
To put it another way, ariels
writes: "what you prove there stems from the following test for divisibility by 11: add the digits, alternating `+' and `-' signs; the number is prime iff this `+-sum' of the digits is too."