Maths Olympiad Prep

Track / Stage 7 / 224 of 300 #2104 of 2444

Problem 2104

National Olympiad second round; IMO P1/P4
Number theory Difficulty 7.7 Prove it Japan Mathematical Olympiad · Japan

Determine all the quintets (a,n,p,q,r)(a, n, p, q, r) of positive integers for which the identity
an1=(ap1)(aq1)(ar1)a^n - 1 = (a^p - 1)(a^q - 1)(a^r - 1)
is satisfied.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

If a=1a = 1, the identity of the problem holds regardless of how other positive integers n,p,q,rn, p, q, r are chosen. So, we assume that a2a \ge 2 in the sequel. Since the given identity is symmetric in p,q,rp, q, r, we may assume that pqrp \le q \le r holds.

We can rewrite the given identity in the form
an=ap+q+r(ap+q+ap+r+aq+r)+(ap+aq+ar). a^n = a^{p+q+r} - (a^{p+q} + a^{p+r} + a^{q+r}) + (a^p + a^q + a^r).
Since a2a \ge 2, we have ap+q>apa^{p+q} > a^p, aq+r>aqa^{q+r} > a^q, ap+r>ara^{p+r} > a^r. This together with the fact that ap+aq+ar>0a^p + a^q + a^r > 0 gives us
ap+q+r>an>ap+q+r(ap+q+ap+r+aq+r). a^{p+q+r} > a^n > a^{p+q+r} - (a^{p+q} + a^{p+r} + a^{q+r}).
From the left half of the inequality above, we see that np+q+r1n \le p+q+r-1 and using this we get from the right half of the inequality above that ap+q+r1>ap+q+r(ap+q+ap+r+aq+r)a^{p+q+r-1} > a^{p+q+r} - (a^{p+q} + a^{p+r} + a^{q+r}), which simplifies to
a1+ap+aq+ar>1. a^{-1} + a^{-p} + a^{-q} + a^{-r} > 1.
Because of the fact that 1pqr1 \le p \le q \le r, we have a1apaqara^{-1} \ge a^{-p} \ge a^{-q} \ge a^{-r} and since the sum of these 4 numbers is greater than 1 as we saw above, we get a1>14a^{-1} > \frac{1}{4}. Thus we have a<4a < 4 and since a2a \ge 2, we must have either a=2a = 2 or a=3a = 3.

(1) Consider the case when a=3a = 3:

In this case we have 3p+3q+3r>131=233^{-p} + 3^{-q} + 3^{-r} > 1 - 3^{-1} = \frac{2}{3} so that 3p>293^{-p} > \frac{2}{9}, and therefore, p=1p = 1. We then get 3q+3r>133^{-q} + 3^{-r} > \frac{1}{3}, which in turn implies 3q>163^{-q} > \frac{1}{6}, and therefore, q=1q = 1. Now from p=q=1p = q = 1, we conclude from the given identity that 3n=43r33^n = 4 \cdot 3^r - 3 must hold. Since 43r<93r=3r+24 \cdot 3^r < 9 \cdot 3^r = 3^{r+2}, we must have nr+1n \le r+1. Consequently, we must have 3r+143r33^{r+1} \ge 4 \cdot 3^r - 3, which simplifies to 3r33^r \le 3. Therefore, r=1r = 1 must hold. Thus we see that if a=3a = 3, then p=q=r=1p = q = r = 1 must hold and then the given identity forces nn to satisfy 3n1=(31)33^n - 1 = (3-1)^3, from which we get n=2n = 2. Thus we conclude that (3,2,1,1,1)(3, 2, 1, 1, 1) is the unique solution in the case (1).

(2) Consider the case when a=2a = 2:

In this case, we have 2p+2q+2r>122^{-p} + 2^{-q} + 2^{-r} > \frac{1}{2}, which implies 2p>162^{-p} > \frac{1}{6}. Therefore, we must have either p=1p = 1 or p=2p = 2.

* Case when p=2p = 2:

In this case, we have 2q+2r>142^{-q} + 2^{-r} > \frac{1}{4} so that 2q>182^{-q} > \frac{1}{8} and combining with the fact qp=2q \ge p = 2 we get q=2q = 2 as well. Then, we see that the given identity takes the form 2n=92r82^n = 9 \cdot 2^r - 8. From 92r<162r=2r+49 \cdot 2^r < 16 \cdot 2^r = 2^{r+4} we get 2r+392r82^{r+3} \ge 9 \cdot 2^r - 8, which simplifies to 2r82^r \le 8. So, we must have r=2r = 2 or r=3r = 3. Checking each of these cases, we can conclude that (a,n,p,q,r)=(2,6,2,2,3)(a, n, p, q, r) = (2, 6, 2, 2, 3) is the unique solution in this case.

* Case when p=1p = 1:

In this case the given identity takes the form 2n=2q+r2q2r+22^n = 2^{q+r} - 2^q - 2^r + 2. Since the right side of this equality is less than 2q+r2^{q+r}, we must have 2q+r12q+r2q2r+22^{q+r-1} \ge 2^{q+r} - 2^q - 2^r + 2, which reduces to the inequality 2q+r1+22q+2r2^{q+r-1} + 2 \le 2^q + 2^r, from which we get, as 2q+2r2r+12^q + 2^r \le 2^{r+1}, that 2q+r1<2r+12^{q+r-1} < 2^{r+1}. Hence, q+r1<r+1q+r-1 < r+1 and we get q=1q = 1. The given identity now reduces, as p=q=1p = q = 1, to the equality 2n=2r2^n = 2^r, so we must have n=rn = r, which can be any positive integer. Thus the solution in this case takes the form (a,n,p,q,r)=(2,k,1,1,k)(a, n, p, q, r) = (2, k, 1, 1, k), where kk is an arbitrary positive integer.

Summarizing the arguments given above, we can write down all the quintuples (a,n,p,q,r)(a, n, p, q, r) satisfying the given identity as follows:

* a=1a = 1 and n,p,q,rn, p, q, r can be arbitrary positive integers.
* (a,n,p,q,r)=(3,2,1,1,1)(a, n, p, q, r) = (3, 2, 1, 1, 1).
* (a,n,p,q,r)=(2,6,2,2,3)(a, n, p, q, r) = (2, 6, 2, 2, 3) and its variants obtained by permuting p,q,rp, q, r.
* (a,n,p,q,r)=(2,k,1,1,k)(a, n, p, q, r) = (2, k, 1, 1, k) where kk is an arbitrary positive integer and their variants obtained by permuting p,q,rp, q, r.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.