Maths Olympiad Prep

Library / /1 of 22

Number theory Difficulty 5.2 AIME, harder Prove it Croatia

Find all positive integers nn such that
n3n23n+13n2 \frac{n^{3n-2} - 3n + 1}{3n - 2}
is an integer.

Solution

Since 3n2n3n23n+13n-2 \mid n^{3n-2}-3n+1, it follows that 3n2n3n213n-2 \mid n^{3n-2}-1, hence n3n21(mod3n2)n^{3n-2} \equiv 1 \pmod{3n-2}.

Note that nn must be odd (otherwise the even 3n23n-2 would divide the odd n3n23n+1n^{3n-2}-3n+1, which is impossible).

Let p>2p > 2 be the smallest prime factor of the odd 3n23n-2. Obviously pnp \nmid n, hence by Fermat's little theorem we have np11(modp)n^{p-1} \equiv 1 \pmod{p}. We also have n3n21(modp)n^{3n-2} \equiv 1 \pmod{p}.

Let rr be the order of nn modulo pp. Then rp1r \mid p-1 and r3n2r \mid 3n-2. Since rgcd(p1,3n2)r \mid \gcd(p-1, 3n-2) and gcd(p1,3n2)=1\gcd(p-1, 3n-2) = 1, it must be r=1r=1, i.e. n1(modp)n \equiv 1 \pmod{p}.

Considering pn1p \mid n-1 and p3n2p \mid 3n-2, it follows that p1p \mid 1, which contradicts the assumption about the existence of prime factor of 3n23n-2. Hence 3n2=13n-2=1, i.e. n=1n=1, and that is indeed the only solution.

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 and solution reproduced as published; topic and difficulty added by this site.