Maths Olympiad Prep

Library / /6 of 20

Number theory Difficulty 5.3 AIME, harder Prove it Greece

The positive integer nn is such that n29n^2-9 has exactly 6 positive divisors. Prove that gcd(n3,n+3)=1\text{gcd}(n-3, n+3)=1.

Solution

In order the positive integer nn to have exactly 6 positive divisors, it must be of the form n29=q5n^2-9 = q^5 or n29=p2qn^2-9 = p^2q, where pp, qq are primes mutually different.

In the first case we have n29=q5(n3)(n+3)=q5n^2-9 = q^5 \Rightarrow (n-3)(n+3) = q^5 (1)
It gives that
n3=qs and n+3=qt, with t>s and t+s=5. n-3 = q^s \text{ and } n+3 = q^t, \text{ with } t > s \text{ and } t+s = 5.
By subtracting we get qtqs=6qs(qts1)=23q^t - q^s = 6 \Leftrightarrow q^s(q^{t-s} - 1) = 2 \cdot 3 and hence q{2,3}q \in \{2,3\}.
For q=2q=2 (1) gives n2=41n^2 = 41, (it has no solutions in Z\mathbb{Z}), while for q=3q=3, (1) gives n2=252n^2 = 252, (impossible in Z\mathbb{Z}).

In the second case n29=p2qn^2-9 = p^2q, it follows that (n3)(n+3)=p2q(n-3)(n+3) = p^2q, and so
(n+3=pq and n3=p) or (n+3=q and n3=p2)or (n+3=p2 and n3=q). \begin{align*} (n+3 = pq \text{ and } n-3 = p) \text{ or } (n+3 = q \text{ and } n-3 = p^2) \\ \text{or } (n+3 = p^2 \text{ and } n-3 = q). \end{align*}
From the first case we get p(q1)=6p(q-1) = 6, and hence (p=3p=3 and q=3q=3), which must be rejected because pqp \neq q.
From the last two cases we conclude that gcd(n3,n+3)=1\text{gcd}(n-3, n+3)=1.

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.