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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.