Consider the number $n= 2^{1000000000000000000000000000000000} +1$. Suppose that it is known that none of the numbers $1 < k < n - 10^{6}$ divides $n$. Does it follow that $n$ is a prime number? Explain your answer!
Solution
Theorem : Let $n\in\mathbb{Z}$ . If there is no prime $p$ such that $p < \sqrt{n}$ and $p\mid n$, then $p$ is a prime number.
We know that no number $k\mid n$ where $1 < k < n- 10^{6}$ .
So:
$\sqrt{n} < n - 10^{6}$
$n < (n - 10^{6} )^{2}$
Let $n = 1$
$1 < (1- 10^{6} )^{2}$
$1< 9.99998 * 10^{11}$
Since $n$ is less than $(n - 10^{6} )^{2}$ . Thus by theorem $n$ is a prime number.
Please give feedback to this solution.
No, there seems to be some confusion there. The number $n$ has been explicitly defined in the problem, so you cannot just decide to set it to $1$ halfway through.
What you need to argue is that $\sqrt{2^{10^{33}}+1}<2^{10^{33}}+1-10^6$ -- not that $\sqrt{1}<1-10^6$.
In fact $\sqrt{1}<1-10^6$ is not true, so it's a good thing that's not what you need to show. (When you squared both sides of the inequality you needed to assume that both sides were positive, but that is not true for $1-10^6$).
Wouldn't it be simpler to observe that $$ n = 2^{10^{33}}+1 = (2^{2\cdot 10^{32}}+1)(2^{8\cdot 10^{32}}-2^{6\cdot 10^{32}}+2^{4\cdot 10^{32}}-2^{2\cdot 10^{32}}+1) $$ and therefore is not prime?