Maths Olympiad Prep

Library / /18 of 22

Number theory Difficulty 8.9 Shortlist Prove it Germany

Problem:
Can one find, for every positive integer nn, non-negative integers a,b,c,d,e,f,g,ha, b, c, d, e, f, g, h with

n=2a2b2c2d2e2f2g2h n=\frac{2^{a}-2^{b}}{2^{c}-2^{d}} \cdot \frac{2^{e}-2^{f}}{2^{g}-2^{h}}

? The answer is to be justified.

Solution

Solution:
Preliminary remark: In what follows let nn be odd. Without loss of generality a>b,c>d,e>f,g>ha>b, c>d, e>f, g>h. The condition equation is then equivalent to
n2d+hbf(2cd1)(2gh1)=(2ab1)(2ef1). n 2^{d+h-b-f}\left(2^{c-d}-1\right)\left(2^{g-h}-1\right)=\left(2^{a-b}-1\right)\left(2^{e-f}-1\right).
Since nn is odd, we have d+hbf=0d+h-b-f=0, and one can, without loss of generality, set d=h=b=f=0d=h=b=f=0:
n(2c1)(2g1)=(2a1)(2e1) n\left(2^{c}-1\right)\left(2^{g}-1\right)=\left(2^{a}-1\right)\left(2^{e}-1\right)

1st Solution (sketched): The numbers of the form n=19+64kn=19+64k with integer k0k \geqq 0 cannot be represented. For x>1x>1, 2x12^{x}-1 gives remainder 3 upon division by 4, for x=1x=1 remainder 1. Only if an odd number of the variables a,c,e,ga, c, e, g has value 1 can equation (*) be satisfied. If three of the variables have value 1, the equation cannot hold, since nn does not have the form 2x12^{x}-1. Hence exactly one of the brackets in ()(*) has value 1. By corresponding considerations and case distinctions concerning remainders upon division by 8, 16, 32, 64, one can fix the values of the remaining brackets and in each case lead to a contradiction.

2nd Solution (sketched): The number n=19n=19 is not representable. One uses the relation gcd(2x1,2y1)=2gcd(x,y)1\gcd(2^{x}-1, 2^{y}-1)=2^{\gcd(x, y)}-1 to show: from (2x1)(2y1)(2z1)(2^{x}-1) \mid (2^{y}-1)(2^{z}-1) it follows that xyx \mid y or xzx \mid z.
From this it follows, together with ()(*), that 19 can be written as
19=2a12c12e12g1or19=2a1(2c1)(2g1)(2e1) 19=\frac{2^{a}-1}{2^{c}-1} \cdot \frac{2^{e}-1}{2^{g}-1} \quad \text{or} \quad 19=\frac{2^{a}-1}{(2^{c}-1)(2^{g}-1)} \cdot (2^{e}-1)
as a product of two integer factors. Since 19 is a prime number and does not have the form 2e12^{e}-1, it suffices to show that the equation
19=2a1(2c1)(2g1) 19=\frac{2^{a}-1}{(2^{c}-1)(2^{g}-1)}
cannot hold. The numerator contains the prime factor 19, which is only possible for a18a \geq 18. The numbers cc and gg divide aa, without loss of generality cgc \geq g. For c=g=a/2c=g=a/2 the fraction has the non-integer value 1+2/(2a/21)1+2/(2^{a/2}-1), for ca/3,ga/3c \leq a/3, g \leq a/3 or for c=a/2,ga/4c=a/2, g \leq a/4 the value is too large. Thus c=a/2,g=a/3c=a/2, g=a/3, and the fraction has the non-integer value 2a/6+1/(2a/61)2^{a/6}+1/(2^{a/6}-1).

Remark: It is not always the case that nn is a product of two integer factors of the form (2x1)/(2y1)(2^{x}-1)/(2^{y}-1). For example, 13=(2121)(221)(261)(241)13=\frac{(2^{12}-1)(2^{2}-1)}{(2^{6}-1)(2^{4}-1)}, but one can show, as in the 2nd Solution, that 13 cannot be represented in the form (2x1)/(2y1)(2^{x}-1)/(2^{y}-1).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from de; metadata (topic, difficulty) added by this project.