ins_adsf@jhunix.UUCP (03/15/86)
Here's a nifty yet simple number theory problem. Prove that there
is a unique palindromic prime number with an even number of digits. Generalize
to other bases.
- David Fry
...!seismo!umcp-cs!aplcen!jhunix!ins_adsf
Johns Hopkins University
--------------------------------------------------------------------
"Rien n'est beau que le vrai, le vrai seul est aimable."
- Boileaubhaskar@cvl.UUCP (03/15/86)
In article <2222@jhunix.UUCP>, ins_adsf@jhunix.UUCP (David S Fry) writes: > > Here's a nifty yet simple number theory problem. Prove that there > is a unique palindromic prime number with an even number of digits. Generalize > to other bases. > Let b ( > 1 ) be the base under consideration and let the notation S{p <= i <= q, a[i]} represent the sum a[p] + a[p+1] +...+ a[q] and x^y represent x_to_power_y. Let the number sought, x, be represented by a[n-1] a[n-2] ...a[1] a[0] a[0] a[1]... a[n-2] a[n-1] in a b-ary base. Assume that n > 1. Then value(x) = S{ 0 <= i <= n-1 , a[i] * ( b^(n-i-1) + b^(n+i)) } = S{ 0 <= i <= n-1 , a[i] * b^(n-i-1) * (1 + b^(2i+1)) } = S{ 0 <= i <= n-1 , a[i] * b^(n-i-1) * (1 + b) * (1-b+b^2-... +b^2i) }. Thus x cannot be prime for it has b+1 as factor. Thus we must have n = 1 and the number sought is of the form a[0] a[0]. Then, value(x) = a[0] * ( 1 + b ) . Since x is prime, we must have a[0] = 1 and 1+b = x. Thus the only "even length palindromic primes" are of form 11 in a base b, where b+1 is itself prime. For example, eleven in base 10 or three in base 2. In particular, we cannot have such primes as described, in any odd-valued base b ( b > 1 ).
greg@harvard.UUCP (Greg) (03/16/86)
In article <2222@jhunix.UUCP> ins_adsf@jhunix.UUCP (David S Fry) writes: > > Here's a nifty yet simple number theory problem. Prove that there >is a unique palindromic prime number with an even number of digits. Generalize >to other bases. The number 100....01, if it has an even number of digits, is divisible by 11. Any palindrome with an even number of digits is the sum of such numbers. Therefore all palindromes with evenly many digits are multiples of 11, so the only such prime is 11 itself. In base p-1, where p is prime, p is the only prime palindrome with evenly many digits. In other bases, all such numbers are composite. Now for a more interesting problem in elementary number theory: Let C(a,b) = a!/(b!*(a-b)!), and let p>3 be a prime number. Show that: C(p*a,p*b) = C(a,b) mod p^3 -- gregregreg
bhaskar@cvl.UUCP (03/22/86)
In article <779@harvard.UUCP>, greg@harvard.UUCP writes: > > Let C(a,b) = a!/(b!*(a-b)!), and let p>3 be a prime number. > Show that: > > C(p*a,p*b) = C(a,b) mod p^3 > -- > gregregreg I have a proof, but it is rather messy. Rather than use the most general notation, I have used examples to clarify a point. If a simpler proof is available, I would like to see it (by mail). For e.g. Consider C(5*3,5*2) 15.14.13.12.11.10.9.8.7.6 = ------------------------- 10. 9. 8. 7. 6. 5.4.3.2.1 ( 15.10 ) (14.13.12.11.9.8.7.6) = ------- -------------------- ( 10.5 ) ( 9. 8. 7. 6.4.3.2.1) = C(3,2) * Mess Thus in general, we consider messes of the form : [kp+p-1][kp+p-2]...[kp+1] [(k-1)p+p-1].[(k-1)p+1]... divided by similar factors in the denominator. If S(n,k) denotes the Stirling number of the 1'st kind then [kp+p-1] [kp+p-2] . [kp+1] = Sigma{ 0 <= i <= p-1 , (kp)^i * (-1)^(p-1+i) * S(p,i+1) } = S(p,1) - S(p,2) * (kp) + S(p,3) * (kp)^2 (mod p^3) . Now, p * S(p,2) = p * (p-1)! * H(p-1) , where H(n) is the n'th harmonic no. But (p-1)! * H(p-1) = 0 (mod p^2) (* Wolstenholme's thm. *) Therefore p * (p-1)! * H(p-1) = 0 (mod p^3) . Also, S(p,k) = 0 (mod p) (* easily proven *) Therefore p^2 * S(p,k) = 0 (mod p^3) . Thus [kp+p-1] ... [kp+1] = S(p,1) (mod p^3) = (p-1)! (mod p^3) Since the numerator and denominator have the same number of factors of the form [kp+p-1]...[kp+1] and since each is (p-1)! (mod p^3), the Mess simplifies to 1 (mod p^3) and we are left with C(a,b).