# 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?

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. 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.