Maths Olympiad Prep

Library / Indian National Mathematical Olympiad /35 of 103

Indian National Mathematical Olympiad

Number theory Difficulty 5.7 AIME, harder Prove it India

Let pp be an odd prime number and a,b,ca, b, c be integers so that the integers
a2023+b2023,b2024+c2024,c2025+a2025 a^{2023} + b^{2023}, \quad b^{2024} + c^{2024}, \quad c^{2025} + a^{2025}
are all divisible by pp. Prove that pp divides each of a,ba, b, and cc.

Solutions — 3

Solution 1

Set k=2023k = 2023. If one of a,b,ca, b, c is divisible by pp, then all of them are. Indeed, for example, if p∣ap \mid a, then p∣ak+bkp \mid a^k + b^k implies p∣bp \mid b, and then p∣bk+1+ck+1p \mid b^{k+1} + c^{k+1} implies p∣cp \mid c. The other cases follow similarly.
So for the sake of contradiction assume none of a,b,ca, b, c is divisible by pp. Then
ak(k+2)≡(ak)k+2≡(−bk)k+2≡−bk(k+2)(modp) a^{k(k+2)} \equiv (a^k)^{k+2} \equiv (-b^k)^{k+2} \equiv -b^{k(k+2)} \pmod{p}
and
ak(k+2)≡(ak+2)k=(−ck+2)k≡−ck(k+2)(modp). a^{k(k+2)} \equiv (a^{k+2})^k = (-c^{k+2})^k \equiv -c^{k(k+2)} \pmod{p}.
So bk(k+2)≡ck(k+2)(modp)b^{k(k+2)} \equiv c^{k(k+2)} \pmod{p}. But then
ck(k+2)⋅c≡c(k+1)2≡(−bk+1)k+1≡b(k+1)2≡bk(k+2)⋅b≡ck(k+2)⋅b(modp) c^{k(k+2)} \cdot c \equiv c^{(k+1)^2} \equiv (-b^{k+1})^{k+1} \equiv b^{(k+1)^2} \equiv b^{k(k+2)} \cdot b \equiv c^{k(k+2)} \cdot b \pmod{p}
which forces b≡c(modp)b \equiv c \pmod{p}. Thus
0≡bk+1+ck+1=2bk+1(modp) 0 \equiv b^{k+1} + c^{k+1} = 2b^{k+1} \pmod{p}
implying p∣bp \mid b, a contradiction. Thus the proof is complete. □

Solution 2

As before, we may assume pp divides none of a,ba, b, and cc and set k=2023k = 2023. Then
ak≡−bk(modp) a^k \equiv -b^k \pmod{p}
bk+1≡−ck+1(modp) b^{k+1} \equiv -c^{k+1} \pmod{p}
ck+2≡−ak+2(modp) c^{k+2} \equiv -a^{k+2} \pmod{p}
and multiplying these three equations yields akbk+1ck+2≡−bkck+1ak+2(modp)a^k b^{k+1} c^{k+2} \equiv -b^k c^{k+1} a^{k+2} \pmod{p}. By cancelling the factor akbkck+1a^k b^k c^{k+1}, we get a2≡−bc(modp)a^2 \equiv -bc \pmod{p}. Now
p∣ak+bk  ⟹  a4k≡b4k(modp)  ⟹  c2k≡b2k(modp) p \mid a^k + b^k \implies a^{4k} \equiv b^{4k} \pmod{p} \implies c^{2k} \equiv b^{2k} \pmod{p}
so
p∣bk+1+ck+1  ⟹  b2(k+1)≡c2(k+1)(modp)  ⟹  b2≡c2(modp) p \mid b^{k+1} + c^{k+1} \implies b^{2(k+1)} \equiv c^{2(k+1)} \pmod{p} \implies b^2 \equiv c^2 \pmod{p}
so either b≡c(modp)b \equiv c \pmod{p} or b≡−c(modp)b \equiv -c \pmod{p}. In the latter case, a2≡c2(modp)a^2 \equiv c^2 \pmod{p} so a≡c(modp)a \equiv c \pmod{p} or a≡−c(modp)a \equiv -c \pmod{p}. In any case, two out of {a,b,c}\{a, b, c\} are the same mod pp, so one of the equations gives p∣2xyp \mid 2x^y where x∈{a,b,c}x \in \{a, b, c\} and y∈{k,k+1,k+2}y \in \{k, k+1, k+2\}, hence pp odd implies p∣xp \mid x so p∣abcp \mid abc, the desired contradiction. □

Solution 3

We have
a2023≡−b2023(modp)(1) a^{2023} \equiv -b^{2023} \pmod{p} \qquad (1)
b2024≡−c2024(modp)(2) b^{2024} \equiv -c^{2024} \pmod{p} \qquad (2)
c2025≡−a2025(modp)(3) c^{2025} \equiv -a^{2025} \pmod{p} \qquad (3)
Thus,
a2023⋅2024⋅2025≡b2023⋅2024⋅2025(modp)by (1)≡−c2023⋅2024⋅2025(modp)by (2)≡−a2023⋅2024⋅2025(modp)by (3) \begin{align*} a^{2023 \cdot 2024 \cdot 2025} &\equiv b^{2023 \cdot 2024 \cdot 2025} \pmod{p} & \text{by (1)} \\ &\equiv -c^{2023 \cdot 2024 \cdot 2025} \pmod{p} & \text{by (2)} \\ &\equiv -a^{2023 \cdot 2024 \cdot 2025} \pmod{p} & \text{by (3)} \end{align*}
Thus, p∣2⋅a2023⋅2024⋅2025p \mid 2 \cdot a^{2023 \cdot 2024 \cdot 2025} and hence p∣ap \mid a since pp is odd. Now, finish as before. □

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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