Maths Olympiad Prep

Library / Croatian Mathematical Olympiad /1 of 37

Croatian Mathematical Olympiad

Number theory Difficulty 5.2 AIME, harder Prove it Croatia

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

Solution

Since 3n−2∣n3n−2−3n+13n-2 \mid n^{3n-2}-3n+1, it follows that 3n−2∣n3n−2−13n-2 \mid n^{3n-2}-1, hence n3n−2≡1(mod3n−2)n^{3n-2} \equiv 1 \pmod{3n-2}.

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

Let p>2p > 2 be the smallest prime factor of the odd 3n−23n-2. Obviously p∤np \nmid n, hence by Fermat's little theorem we have np−1≡1(modp)n^{p-1} \equiv 1 \pmod{p}. We also have n3n−2≡1(modp)n^{3n-2} \equiv 1 \pmod{p}.

Let rr be the order of nn modulo pp. Then r∣p−1r \mid p-1 and r∣3n−2r \mid 3n-2. Since r∣gcd⁡(p−1,3n−2)r \mid \gcd(p-1, 3n-2) and gcd⁡(p−1,3n−2)=1\gcd(p-1, 3n-2) = 1, it must be r=1r=1, i.e. n≡1(modp)n \equiv 1 \pmod{p}.

Considering p∣n−1p \mid n-1 and p∣3n−2p \mid 3n-2, it follows that p∣1p \mid 1, which contradicts the assumption about the existence of prime factor of 3n−23n-2. Hence 3n−2=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,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.