number theory question from USAMO 2010 preparation session Prove that for any natural number k, there exists a natural number n such that
n has exactly k different prime factors and $2^{n^{2}}+ 1$ is divisible by $n^3$.
Below i present my attempt. PLease highlight my mistakes and lemme know what i could improve upon.
Solution:
Since there are infinitely primes, thus $\forall k$ there exists an $n$ with $k$ prime factors. Thus we only need to show that an $n $ which satisfies the second condition exists.
Define $n=k_1^{\alpha_1}\cdot k_2^{\alpha_2}\cdot k_3^{\alpha_3}\cdot.... k_k^{\alpha_k}$, Where $k_i$ is a unique prime.
Now, if $n^3| 2^{n^{2}}+ 1 \Rightarrow n^3|2^{2n^{2}}- 1$, Or,
$2^{2n^{2}}\equiv 1$ ($mod$ $n^3$).
Define $\epsilon=ord_{n^3}(2)$. Thus if $\epsilon|2n^{2}$ or $Q \cdot \epsilon=2n^{2}$
We will have
$2^{Q \cdot \epsilon}\equiv 1$ ($mod$ $n^3$), Equivalently,
$2^{b_i} \equiv 1 $ $(mod$ $k_j^{3\alpha_j})$, $1 \leq j\leq k$ Which has a unique solution modulo $n^3$ by Chinese Remainder Theorem.

But how do i show that an $n$ which satisfies  $\epsilon|2n^{2}$, where epsilon has the same definition ? Also is this approach right or good? Or even plausible in the first place?
 A: I am not sure about your approach, but induction seems to be the way to go. For $k=1$, we need to find prime $p$ such that:
$$p^3 \mid 2^{p^2}+1 \implies p^3 \mid2^{2p^2}-1$$
and $p=3$ satisfies this (simple to observe by Lifting the Exponent). Now, let $n$ have $k$ prime factors and let $n^3 \mid 2^{n^2}+1$. We will find a new prime $p \nmid n$ such that $pn$ satisfies our conditions. We require:
$$n^3p^3 \mid 2^{n^2p^2}+1$$
Clearly, $n^3$ divides $2^{n^2p^2}+1$ from induction hypothesis and since $p$ is an odd prime we are going to take. It suffices to find:
$$p^3 \mid (2^{n^2p^2}+1)$$
It follows from a modification of Zsigmondy's theorem that there exists a primitive prime divisor for $2^t+1$ for all $t>2$. Letting $p$ be a primitive prime divisor of $2^{n^2}+1$ and using Lifting the Exponent does the job. Now, we need to verify that $p \nmid n$. However, we can see from our method of induction that all the prime factors of $n$ were chosen as primitive prime divisors of $2^t+1$ for some $t<n^2$. and since $p$ is a primitive prime divisor of $2^{n^2}+1$, this shows that $p$ is not a prime factor of $n$. Hence, proved.
