Maths Olympiad Prep

Library / /19 of 23

Number theory Difficulty 7.0 National olympiad Prove it Ireland

For which prime numbers pp do there exist positive rational numbers x,yx, y and a positive integer nn such that
x+y+px+py=3n? x + y + \frac{p}{x} + \frac{p}{y} = 3n?

Solution

If p2(mod3)p \equiv 2 \pmod{3} and x=y=1x = y = 1, the number
x+y+px+py=2(1+p) x + y + \frac{p}{x} + \frac{p}{y} = 2(1 + p)
is an integer that is divisible by 3, hence for all such primes the required solutions x,y,nx, y, n exist.

We now show that solutions can only exist if p2(mod3)p \equiv 2 \pmod{3}.

Suppose
x=abandy=cd x = \frac{a}{b} \quad \text{and} \quad y = \frac{c}{d}
with positive integers a,b,c,da, b, c, d that satisfy gcd(a,b)=gcd(c,d)=1\gcd(a, b) = \gcd(c, d) = 1, is a solution. The given equation is then equivalent to
(a2+pb2)cd+(c2+pd2)ab=3nabcd.(1) (a^2 + p b^2) c d + (c^2 + p d^2) a b = 3 n a b c d. \quad (1)

Case (i) Because a3=a(a2+pb2)pb(ab)a^3 = a(a^2 + p b^2) - p b (a b), any prime factor of gcd(ab,a2+pb2)\gcd(a b, a^2 + p b^2) must divide aa. Hence, pp is not among these prime factors and such a prime factor must divide pb2=(a2+pb2)a2p b^2 = (a^2 + p b^2) - a^2. This contradicts gcd(a,b)=1\gcd(a, b) = 1. Hence, gcd(ab,a2+pb2)=1\gcd(a b, a^2 + p b^2) = 1. Similarly, using pc,w2p \nmid c, w_2 obtain gcd(cd,c2+pd2)=1\gcd(c d, c^2 + p d^2) = 1.

Equation (1) shows that aba b divides (a2+pb2)cd(a^2 + p b^2) c d. Because gcd(ab,a2+pb2)=1\gcd(a b, a^2 + p b^2) = 1, Euclid's Lemma implies that abcda b \mid c d. Similarly, cdc d divides (c2+pd2)ab(c^2 + p d^2) a b and, using gcd(cd,c2+pd2)=1\gcd(c d, c^2 + p d^2) = 1 we obtain cdabc d \mid a b. This shows that ab=cda b = c d.

As cd0c d \neq 0 we can now cancel cdc d in (1) and obtain
a2+pb2+c2+pd2=3nab. a^2 + p b^2 + c^2 + p d^2 = 3 n a b.
If p1(mod3)p \equiv 1 \pmod{3} we obtain that a2+b2+c2+d20(mod3)a^2 + b^2 + c^2 + d^2 \equiv 0 \pmod{3}, hence at least one of the four numbers a,b,c,da, b, c, d must be divisible by 3. But because ab=cda b = c d, there is a second of these numbers divisible by 3. But then the sum of the squares of the remaining two numbers must also be divisible by 3, which is only possible if these two numbers are divisible by 3 themselves. But this contradicts gcd(a,b)=1\gcd(a, b) = 1.

If p=3p = 3 we immediately obtain that a2+c2a^2 + c^2 is divisible by 3 and so aa and cc are divisible by 3, contrary to our assumption pacp \nmid a c.

Case (ii) If pap \mid a we can write a=paˉa = p \bar{a} with some positive integer aˉ\bar{a} and we have pbp \nmid b, as gcd(a,b)=1\gcd(a, b) = 1. Equation (1) is then equivalent to
(paˉ2+b2)cd+(c2+pd2)aˉb=3naˉbcd (p \bar{a}^2 + b^2) c d + (c^2 + p d^2) \bar{a} b = 3 n \bar{a} b c d
and we have gcd(aˉ,b)=gcd(c,d)=1\gcd(\bar{a}, b) = \gcd(c, d) = 1. So, we are again in the situation of Case (i), now with aˉ\bar{a} replacing bb and cc replacing aa. Therefore, we need to have p2(mod3)p \equiv 2 \pmod{3}.

Case (iii) If pap \mid a and pcp \mid c, we can write a=paˉa = p \bar{a} and c=pcˉc = p \bar{c} with positive integers aˉ,cˉ\bar{a}, \bar{c}. Equation (1) is then equivalent to
(paˉ2+b2)cˉd+(pcˉ2+d2)aˉb=3naˉbcˉd (p \bar{a}^2 + b^2) \bar{c} d + (p \bar{c}^2 + d^2) \bar{a} b = 3 n \bar{a} b \bar{c} d
with gcd(aˉ,b)=gcd(cˉ,d)=1\gcd(\bar{a}, b) = \gcd(\bar{c}, d) = 1. Moreover, because pap \mid a and gcd(a,b)=1\gcd(a, b) = 1 as well as pcp \mid c and gcd(c,d)=1\gcd(c, d) = 1, we also have pbdp \nmid b d. Hence, we are again in the situation of Case (i) and conclude that we need to have p2(mod3)p \equiv 2 \pmod{3} in this case as well.

The final result is that such numbers x,y,nx, y, n exist for all primes pp that satisfy p2(mod3)p \equiv 2 \pmod{3} and for no other prime number.

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 and solution reproduced as published; topic and difficulty added by this site.