Maths Olympiad Prep

Library / /293 of 520

Number theory Difficulty 6.6 National olympiad Prove it

Let x x and y y be positive integers and assume that z=4xyx+y z = \frac{4xy}{x+y} is an odd integer. Prove that at least one divisor of z z can be expressed in the form 4n1 4n-1 where n n is a positive integer.

Solutions — 2

Solution 1

Let x=2sx1x=2^{s} x_{1} and y=2ty1y=2^{t} y_{1} where x1x_{1} and y1y_{1} are odd integers. Without loss of generality we can assume that sts \geq t. We have

z=2s+t+2x1y12t(2stx1+y1)=2s+2x1y12stx1+y1 z=\frac{2^{s+t+2} x_{1} y_{1}}{2^{t}\left(2^{s-t} x_{1}+y_{1}\right)}=\frac{2^{s+2} x_{1} y_{1}}{2^{s-t} x_{1}+y_{1}}

If sts \neq t, then the denominator is odd and therefore zz is even. So we have s=ts=t and z=2s+2x1y1/(x1+y1)z=2^{s+2} x_{1} y_{1} /\left(x_{1}+y_{1}\right). Let x1=dx2,y1=dy2x_{1}=d x_{2}, y_{1}=d y_{2} with gcd(x2,y2)=1\operatorname{gcd}\left(x_{2}, y_{2}\right)=1. So z=z= 2s+2dx2y2/(x2+y2)2^{s+2} d x_{2} y_{2} /\left(x_{2}+y_{2}\right). As zz is odd, it must be that x2+y2x_{2}+y_{2} is divisible by 2s+242^{s+2} \geq 4, so x2+y2x_{2}+y_{2} is divisible by 4. As x2x_{2} and y2y_{2} are odd integers, one of them, say x2x_{2} is congruent to 3 modulo 4. But gcd(x2,x2+y2)=1\operatorname{gcd}\left(x_{2}, x_{2}+y_{2}\right)=1, so x2x_{2} is a divisor of zz.

Solution 2

1. Given: z=4xyx+y z = \frac{4xy}{x+y} is an odd integer, where x x and y y are positive integers.
2. Claim: z z is less than x x or y y . Assume for contradiction that z>x z > x and z>y z > y .
3. Contradiction: If z>x z > x and z>y z > y , then:
4xyx+y>xand4xyx+y>y \frac{4xy}{x+y} > x \quad \text{and} \quad \frac{4xy}{x+y} > y
This implies:
4xy>x(x+y)and4xy>y(x+y) 4xy > x(x+y) \quad \text{and} \quad 4xy > y(x+y)
Simplifying these inequalities:
4xy>x2+xy3xy>x23y>x 4xy > x^2 + xy \quad \Rightarrow \quad 3xy > x^2 \quad \Rightarrow \quad 3y > x
4xy>y2+xy3xy>y23x>y 4xy > y^2 + xy \quad \Rightarrow \quad 3xy > y^2 \quad \Rightarrow \quad 3x > y
Adding these inequalities:
3y+3x>x+y2(x+y)>0 3y + 3x > x + y \quad \Rightarrow \quad 2(x + y) > 0
This is always true, so the contradiction does not arise from this step. Instead, we need to consider the properties of z z .

4. Substitution: Assume z=y+t z = y + t for some tZ+ t \in \mathbb{Z}_+ . Substituting into the equation:
z=4xyx+y=y+t z = \frac{4xy}{x+y} = y + t
leads to:
4xyx+y=y+t \frac{4xy}{x+y} = y + t
Multiplying both sides by x+y x + y :
4xy=(y+t)(x+y) 4xy = (y + t)(x + y)
Expanding and rearranging:
4xy=xy+y2+tx+ty3xy=y2+tx+ty 4xy = xy + y^2 + tx + ty \quad \Rightarrow \quad 3xy = y^2 + tx + ty
y2+(t3x)y+tx=0 y^2 + (t - 3x)y + tx = 0

5. Discriminant Analysis: Considering the discriminant Δy \Delta_y of the quadratic equation:
Δy=(t3x)241tx=(t3x)24tx \Delta_y = (t - 3x)^2 - 4 \cdot 1 \cdot tx = (t - 3x)^2 - 4tx
For y y to be an integer, Δy \Delta_y must be a perfect square. Let:
(t3x)24tx=k2 (t - 3x)^2 - 4tx = k^2
Rearranging:
(t3x)2+4x2=k2+4tx (t - 3x)^2 + 4x^2 = k^2 + 4tx
This can be written as:
(2y+t3x)2+(4x)2=(5xt)2 (2y + t - 3x)^2 + (4x)^2 = (5x - t)^2

6. **Existence of r r and s s **: There exist r,sZ+ r, s \in \mathbb{Z}_+ such that:
2y+t3x=r2s2,4x=2rs,5xt=r2+s2 2y + t - 3x = r^2 - s^2, \quad 4x = 2rs, \quad 5x - t = r^2 + s^2
Solving these:
x=rs2,y=r2rs2,z=y+t=2rss2 x = \frac{rs}{2}, \quad y = r^2 - \frac{rs}{2}, \quad z = y + t = 2rs - s^2
Since z z is odd, one of r r or s s must be even and the other odd.

7. Conclusion: If r r is even and s s is odd, then:
z=2rss23(mod4) z = 2rs - s^2 \equiv 3 \pmod{4}
This implies that z z has a divisor of the form 4n1 4n - 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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.