Thursday, December 31, 2009

How many primes

#Problem 4
How many primes among the positive integers, written as usual in base 10, are such that their digits are altenating 1’s and 0’s, beginning and ending with 1? [Putnam]

Solution scheme and approach

For n=2 X=101 which is a prime number
For n>=3
If n is even
As (10^n+1)>99
(10^n-1)=(9+1)^n -1=0(mod 9) So,(10^n-1)=9a
(10^n-1)=(11-1)^n -1=0(mod 11)So (10^n-1)=11b
therefore we can write X=99*a*b*(10^n+1)=>Composite
If n is odd
As (10^n-1)>99
(10^n-1)=(9+1)^n -1=0(mod 9) So, (10^n-1)=9a[a>1]
(10^n+1)=(11-1)^n +1=0(mod 11) So,(10^n+1)=11b[b>1]
therefore X=99*a*b=>composite

So, there is only one prime number, 101, exists.Q.E.D.

No comments:

Post a Comment