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!=an1+bn1+cn1 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(n1)(n2)(n3)(34(n4))2(n1)4(3++(n4)n6)n6=2(n1)4(n12)n6<(n12)n1, \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<n12a, b, c < \frac{n-1}{2}.

For every prime pp and integer m0m \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=1nps=np1.(1) \nu_p(n!) < \sum_{s=1}^{\infty} \frac{n}{p^s} = \frac{n}{p-1}. \quad (1)
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,b,ca, b, c 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 (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!=an1+bn1+cn1n! = 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!)n1\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=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} \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 pa+b<np \le 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 (1). Next, using (1) 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).(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 n1>a+bn-1 > a+b. On the other hand, pcp|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 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 translated into English from zh; metadata (topic, difficulty) added by this project.