Maths Olympiad Prep

Library / /167 of 397

, 2022

Number theory Difficulty 5.6 AIME, harder Prove it Taiwan

Prove that there are only finitely many quadruples of positive integers (a,b,c,n)(a, b, c, n) for which the equality
n!=an−1+bn−1+cn−1 n! = a^{n-1} + b^{n-1} + c^{n-1}
holds.

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 AM-GM inequality,
n!=2n(n−1)(n−2)(n−3)⋅(3⋅4⋯(n−4))≤2(n−1)4(3+⋯+(n−4)n−6)n−6=2(n−1)4(n−12)n−6<(n−12)n−1, \begin{aligned} n! &= 2n(n-1)(n-2)(n-3) \cdot (3 \cdot 4 \cdots (n-4)) \\ &\le 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<n−12a, b, c < \frac{n-1}{2}.

For every prime pp and integer m≠0m \ne 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=1∞nps=np−1.(1) \nu_p(n!) < \sum_{s=1}^{\infty} \frac{n}{p^s} = \frac{n}{p-1}. \quad (1)
If nn is odd then an−1,bn−1,cn−1a^{n-1}, b^{n-1}, c^{n-1} are squares, and by considering them modulo 44 we conclude that a,b,ca, b, c must be even. hence, 2n−1∣n!2^{n-1} \mid n! but that is impossible for odd nn because ν2(n!)=ν2((n−1)!)<n−1\nu_2(n!) = \nu_2((n-1)!) < n-1 by (1). 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 are all odd, then n!=an−1+bn−1+cn−1n! = a^{n-1}+b^{n-1}+c^{n-1} is also odd, contradicting the assumption that nn must be even. If all a,b,ca, b, c are divisible by 44, this contradicts ν2(n!)≤n−1\nu_2(n!) \le 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=2r−2c = 2^r - 2 and since c∣n!c \mid n!, we must have c∣an−1+bn−1=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≢3⋅2n−1(mod5)n! \equiv 0 \not\equiv 3 \cdot 2^{n-1} \pmod 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 p≤a+b<np \le a+b < n and so cn−1=n!−(an−1+bn−1)c^{n-1} = n! - (a^{n-1} + b^{n-1}) is divisible by pp. If pp divides aa and bb, we get pn−1∣n!p^{n-1} \mid n!,

contradicting (1). Next, using (1) and the Lifting the Exponent Lemma we get
νp(1)+νp(2)+⋯+νp(n)=νp(n!)=νp(n!−cn−1)=νp(an−1+bn−1)=νp(a+b)+νp(n−1).(2) \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{2}
In view of (2), no number of 1,2,…,n1, 2, \dots, n can be divisible by pp, except a+ba+b and n−1>a+bn-1 > a+b. On the other hand, p∣cp|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, \dots, n, namely a+b=pa+b = p and n−1=2pn-1 = 2p. But this is another contradiction because n−1n-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 translated into English from zh; metadata (topic, difficulty) added by this project.