Questions about prime numbers

Question

Let $x,y,k$ be nonnegative integers, with $k$ not being a power of $2$.

1. Prove that $x^k+y^k$ is not prime.
2. Conclude that if $2^n + 1$ is prime and $n$ is not a power of $2$, then $n$ is prime.

Answer 1

1) Clearly $1^k+1^k=2$ and $x^0+y^0=2$ are exceptions to the claim. Let us therefore exclude the cases $k=0$ as well as $x=y=1$. As $k$ is not a power of $2$, we have $k\ge 3$. Without loss of generality, $x\ge y$. We can exclude the case $y=0$ as then $x^k+y^k=x\cdot x^{k-1}$ is either a nontrivial factorization or we have $x\in\{0,1\}$, and in both cases $x^k+y^k$ is not prime. Then we can also exclude the case $x=y$ as then $x^k+y^k=2\cdot x^k$ with $x^k>1$ is a nontrivial factorization. Hence $x>y\ge 1$. Write $k=2^mu$ with $u>1$. Then $$\tag1x^k+y^k=a^u-b^u=(a-b)(a^{u-1}+a^{u-2}b+\ldots +b^u)$$ with $a=x^{2^m}$, $b=-y^{2^m}$. Since clearly $2=1+1< x^{2^m}+y^{2^m}=a-b<x^k+y^k$, (1) is a nontrivial factorization.

2) Letting $x=2, y=1, k=n$, we see that if $n$ is not a power of $2$ (and $n>0$, remeber the exceptions!) then $2^n+1$ is not prime. By contraposition, if $2^n+1$ is prime, then $n$ is a power of two (or $n=0$). Or: If $2^n+1$ is prime and $n$ is not a power of $2$, then ... $n=0$ (and not $n$ is prime, as the problem statement claims)

---

Remark: Primes of the form $2^n+1$ with $n$ a power of $2$ are called Fermat primes (e.g. $2^1+1=3, 2^2+1=5, 2^4+1=17, 2^8+1=257$). If $2^n-1$ is prime, then $n$ is prime and $2^n-1$ is called a Mersenne prime (e.g. $2^2-1=3, 2^3-1=7, 2^5-1=31, 2^7-1=127$). This is a much more common phenomenon