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
Let,
X=1010101…1=1+10^2+10^4+…+10^2n=(10^2n-1)/99=(10^n+1)*(10^n-1)/99

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