Maths Olympiad Prep

Library / /43 of 383

, 2021

Number theory Difficulty 7.8 National Olympiad, round 2 Prove it IMO

Prove that there are only finitely many quadruples (a,b,c,n)(a, b, c, n) of positive integers such that
n!=an1+bn1+cn1 n! = a^{n-1} + b^{n-1} + c^{n-1}

Solution

For fixed nn there are clearly finitely many solutions; we will show that there is no solution with n>100n > 100. So, assume n>100n > 100. By the AM-GM inequality,
n!=2n(n1)(n2)(n3)(34(n4))2(n1)4(3++(n4)n6)n6=2(n1)4(n12)n6<(n12)n1 \begin{aligned} n! & = 2 n(n-1)(n-2)(n-3) \cdot (3 \cdot 4 \cdots (n-4)) \\ & \leqslant 2(n-1)^{4}\left(\frac{3+\cdots+(n-4)}{n-6}\right)^{n-6} = 2(n-1)^{4}\left(\frac{n-1}{2}\right)^{n-6} < \left(\frac{n-1}{2}\right)^{n-1} \end{aligned}
thus a,b,c<(n1)/2a, b, c < (n-1)/2.

For every prime pp and integer m0m \neq 0, let νp(m)\nu_{p}(m) denote the pp-adic valuation of mm; that is, the greatest non-negative integer kk for which pkp^{k} divides mm. Legendre's formula states that
νp(n!)=s=1nps \nu_{p}(n!) = \sum_{s=1}^{\infty} \left\lfloor \frac{n}{p^{s}} \right\rfloor
and a well-known corollary of this formula is that
νp(n!)<s=1nps=np1. \begin{equation*} \nu_{p}(n!) < \sum_{s=1}^{\infty} \frac{n}{p^{s}} = \frac{n}{p-1} . \tag{$\ominus$} \end{equation*}
If nn is odd then an1,bn1,cn1a^{n-1}, b^{n-1}, c^{n-1} are squares, and by considering them modulo 44 we conclude that a,ba, b and cc must be even. Hence, 2n1n!2^{n-1} \mid n! but that is impossible for odd nn because ν2(n!)=ν2((n1)!)<n1\nu_{2}(n!) = \nu_{2}((n-1)!) < n-1 by ()(\ominus).

From now on we assume that nn is even. If all three numbers a+b,b+c,c+aa+b, b+c, c+a are powers of 22 then a,b,ca, b, c have the same parity. If they all are odd, then n!=an1+bn1+cn1n! = a^{n-1} + b^{n-1} + c^{n-1} is also odd which is absurd. If all a,b,ca, b, c are divisible by 44, this contradicts ν2(n!)n1\nu_{2}(n!) \leqslant n-1. If, say, aa is not divisible by 44, then 2a=(a+b)+(a+c)(b+c)2a = (a+b) + (a+c) - (b+c) is not divisible by 88, and since all a+b,b+c,c+aa+b, b+c, c+a are powers of 22, we get that one of these sums equals 44, so two of the numbers of a,b,ca, b, c are equal to 22. Say, a=b=2a = b = 2, then c=2r2c = 2^{r} - 2 and, since cn!c \mid n!, we must have can1+bn1=2nc \mid a^{n-1} + b^{n-1} = 2^{n} implying r=2r = 2, and so c=2c = 2, which is impossible because n!0≢32n1(mod5)n! \equiv 0 \not\equiv 3 \cdot 2^{n-1} (\bmod 5).

So now we assume that the sum of two numbers among a,b,ca, b, c, say a+ba+b, is not a power of 22, so it is divisible by some odd prime pp. Then pa+b<np \leqslant a+b < n and so cn1=n!(an1+bn1)c^{n-1} = n! - (a^{n-1} + b^{n-1}) is divisible by pp. If pp divides aa and bb, we get pn1n!p^{n-1} \mid n!, contradicting ()(\ominus). Next, using ()(\ominus) and the Lifting the Exponent Lemma we get
νp(1)+νp(2)++νp(n)=νp(n!)=νp(n!cn1)=νp(an1+bn1)=νp(a+b)+νp(n1). \begin{equation*} \nu_{p}(1) + \nu_{p}(2) + \cdots + \nu_{p}(n) = \nu_{p}(n!) = \nu_{p}(n! - c^{n-1}) = \nu_{p}(a^{n-1} + b^{n-1}) = \nu_{p}(a+b) + \nu_{p}(n-1) . \tag{$\diamond$} \end{equation*}
In view of ()(\diamond), no number of 1,2,,n1, 2, \ldots, n can be divisible by pp, except a+ba+b and n1>a+bn-1 > a+b. On the other hand, pcp \mid c implies that p<n/2p < n/2 and so there must be at least two such numbers. Hence, there are two multiples of pp among 1,2,,n1, 2, \ldots, n, namely a+b=pa+b = p and n1=2pn-1 = 2p. But this is another contradiction because n1n-1 is odd. This final contradiction shows that there is no solution of the equation for n>100n > 100.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.