Maths Olympiad Prep

Library / /40 of 121

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 pap \mid a, then pak+bkp \mid a^k + b^k implies pbp \mid b, and then pbk+1+ck+1p \mid b^{k+1} + c^{k+1} implies pcp \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+2bk(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)kck(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)cc(k+1)2(bk+1)k+1b(k+1)2bk(k+2)bck(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 bc(modp)b \equiv c \pmod{p}. Thus
0bk+1+ck+1=2bk+1(modp) 0 \equiv b^{k+1} + c^{k+1} = 2b^{k+1} \pmod{p}
implying pbp \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
akbk(modp) a^k \equiv -b^k \pmod{p}
bk+1ck+1(modp) b^{k+1} \equiv -c^{k+1} \pmod{p}
ck+2ak+2(modp) c^{k+2} \equiv -a^{k+2} \pmod{p}
and multiplying these three equations yields akbk+1ck+2bkck+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 a2bc(modp)a^2 \equiv -bc \pmod{p}. Now
pak+bk    a4kb4k(modp)    c2kb2k(modp) p \mid a^k + b^k \implies a^{4k} \equiv b^{4k} \pmod{p} \implies c^{2k} \equiv b^{2k} \pmod{p}
so
pbk+1+ck+1    b2(k+1)c2(k+1)(modp)    b2c2(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 bc(modp)b \equiv c \pmod{p} or bc(modp)b \equiv -c \pmod{p}. In the latter case, a2c2(modp)a^2 \equiv c^2 \pmod{p} so ac(modp)a \equiv c \pmod{p} or ac(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 p2xyp \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 pxp \mid x so pabcp \mid abc, the desired contradiction. □

Solution 3

We have
a2023b2023(modp)(1) a^{2023} \equiv -b^{2023} \pmod{p} \qquad (1)
b2024c2024(modp)(2) b^{2024} \equiv -c^{2024} \pmod{p} \qquad (2)
c2025a2025(modp)(3) c^{2025} \equiv -a^{2025} \pmod{p} \qquad (3)
Thus,
a202320242025b202320242025(modp)by (1)c202320242025(modp)by (2)a202320242025(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, p2a202320242025p \mid 2 \cdot a^{2023 \cdot 2024 \cdot 2025} and hence pap \mid a since pp is odd. Now, finish as before. □

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.