Determine the smallest positive integer X, such that X is not expressible in the form (2^P – 2^Q)/(2^R – 2^S), where each of P, Q, R and S is a positive integer.

answer is 11
first I provide (p,q,r,s) values for 1 through 10
1: (1,0,1,0)
2: (2,1,1,0)
3: (2,0,1,0)
4: (3,2,1,0)
5: (4,0,2,0)
6: (3,1,1,0)
7: (3,0,1,0)
8: (4,3,1,0)
9: (6,0,3,0)
10: (5,1,2,0)

Now I shall prove that no positive integers p,q,r,s will give 11
now obviously p>q and r>s so let
p=q+a
r=s+b
then we have
(2^p-2^q)/(2^r-2^s)=
2^q*(2^a-1)/[2^s*(2^b-1)]
now 2^a-1 is odd so 2^s must divide 2^q for this to be an integer and thus s<=q and we have
2^(q-s)*(2^a-1)/(2^b-1)=11
2^(q-s)*(2^a-1)=11*(2^b-1)
now the right hand side is odd thus q-s=0 and q=s and we are left with
2^a-1=11*2^b-11
2^a=11*2^b-10
2^a=2*(11*2^(b-1)-5)
2^(a-1)=11*2^(b-1)-5
if b-1=0 then we have
2^(a-1)=11-5=6
2^(a-1)=6
which has no integer solution for a
now if on the other hand we have b-1>0 then the right hand side is odd and the only way the left hand side will also be odd is if a-1=0 and thus that gives us
1=11*2^(b-1)-5
6=11*2^(b-1)
6/11=2^(b-1)
which obviously has no integer solution and thus there can not be any (p,q,r,s) that gives (2^p-2^q)/(2^r-2^s)=11
and thus 11 is the smallest such x

Edited on November 8, 2009, 6:54 am

Posted by Daniel on 2009-11-07 17:18:52