Maths Olympiad Prep

Library / Taiwan IMO Selection Camp /50 of 359

Taiwan IMO Selection Camp, 2018

Number theory Difficulty 5.1 AIME, harder Prove it Taiwan

Given that all divisors of the positive integer nn, other than 1, are not perfect squares.
Prove that there do not exist coprime positive integers xx and yy such that xn+ynx^n + y^n is a multiple of (x+y)3(x + y)^3.

Solution

Suppose there exist coprime positive integers x,yx, y such that xn+ynx^n + y^n is a multiple of (x+y)3(x+y)^3. Let s=x+ys = x+y, then s>2s > 2.

(1) If nn is even, since xn+yn=xn+(s−x)n=2xn(mods)x^n + y^n = x^n + (s-x)^n = 2x^n \pmod s. But at the same time, xn+ynx^n + y^n is a multiple of (x+y)3(x+y)^3, so xn+yn=0(mods)x^n + y^n = 0 \pmod s, hence 2xn=0(mods)2x^n = 0 \pmod s. But since xx and yy are coprime, xx and ss are coprime, therefore we must have 2=0(mods)2 = 0 \pmod s, that is, x=y=1x = y = 1, a contradiction!

(2) If nn is odd, since xn+yn=xn+(s−x)n=C2ns2(−x)n−2+C1ns(−x)n−1(mods3)x^n + y^n = x^n + (s-x)^n = C_2^n s^2 (-x)^{n-2} + C_1^n s(-x)^{n-1} \pmod{s^3}. But at the same time, xn+ynx^n + y^n is a multiple of (x+y)3=s3(x+y)^3 = s^3, so xn+yn=0(mods3)x^n + y^n = 0 \pmod{s^3}, hence C2ns2(−x)n−2+C1ns(−x)n−1=0(mods3)C_2^n s^2 (-x)^{n-2} + C_1^n s(-x)^{n-1} = 0 \pmod{s^3}. This means there exists an integer kk such that
−12n(n−1)sxn−2+nxn−1=ks2.(1) -\frac{1}{2}n(n-1)sx^{n-2} + nx^{n-1} = ks^2. \quad (1)
From this we know s∣nxn−1s|nx^{n-1}, and since (x,s)=1(x,s) = 1, we get s∣nxn−2s|nx^{n-2}, hence s2∣12n(n−1)sxn−2s^2|\frac{1}{2}n(n-1)sx^{n-2}. Substituting back into Eq. (1), we obtain s2∣nxn−1s^2|nx^{n-1}, and again since (x,s)=1(x,s) = 1 we know s2∣ns^2|n, but this contradicts the fact that nn has no square factor, a contradiction!

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 translated into English from zh; metadata (topic, difficulty) added by this project.