Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.
share|improve this question

closed as off-topic by Najib Idrissi, Old John, Giuseppe Negro, Daniel Fischer, Tunk-Fey Jul 31 at 10:43

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Najib Idrissi, Old John, Giuseppe Negro, Daniel Fischer, Tunk-Fey
If this question can be reworded to fit the rules in the help center, please edit the question.

1  
In (2) is $K$ supposed to be $n$? –  Jim Feb 18 '13 at 21:36
2  
I assume $x$ and $y$ aren't both equal to $1$. Otherwise that's a trivial counterexample to 1). –  Arthur Feb 18 '13 at 21:40
    
Also, part 2 is gibberish. If $n$ is odd then $2^n + 1$ is divisible by 3. –  Will Jagy Feb 18 '13 at 21:41
    
@GitGud: 1 is a power of 2 –  Emanuele Paolini Feb 18 '13 at 21:43
2  
Please show that you've spent at least as much effort on the question yourself as you expect anyone else to go through. –  Ben Millwood Feb 18 '13 at 21:50

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
I do not understand how you would do the proof for the second part –  Username Unknown Feb 19 '13 at 2:35

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