• Oct 24th 2010, 04:05 PM
JRichardson1729
I have recently happened upon an interesting problem that I cannot solve. Here it is:
a. Factorise $x^3+1$.
b. Factorise $x^n+1$ when ${n}\geq{3}$ is odd. Use this to prove the following:
i. If $2^n+1$ is prime, then $n$ must be a power of $2$.
ii. Show that $2^3^2+1$ is not prime.

I can't seem to make any headway on the problem, in particular the very last part. All help is appreciated on this problem.
• Oct 24th 2010, 05:10 PM
Dinkydoe
For (a),(b) show that $x^n+1 = (x+1)(x^{n-1}-x^{n-2}+\cdots +x^2-x+1)$, as n is odd.

i) Use (b) to show that if $n=2^kq$, where q is odd, then

the factorisation of $x^n+1$ is obtained by substituting $x=x^{2^k}$ into $(x^q+1)$

So this means if n is not a power of 2....?

ii) You can show that $2^{32}+1$ is divisable by 5.

Can you do modulo-calculations?
• Oct 25th 2010, 09:04 AM
JRichardson1729
Quote:

Originally Posted by Dinkydoe
For (a),(b) show that $x^n+1 = (x+1)(x^{n-1}-x^{n-2}+\cdots +x^2-x+1)$, as n is odd.

i) Use (b) to show that if $n=2^kq$, where q is odd, then

the factorisation of $x^n+1$ is obtained by substituting $x=x^{2^k}$ into $(x^q+1)$

So this means if n is not a power of 2....?

ii) You can show that $2^{32}+1$ is divisable by 5.

Can you do modulo-calculations?

I cannot do modulo-calculations, however I don't think that $2^3^2+1$ is divisible by $5$.
• Oct 25th 2010, 10:47 AM
undefined
Quote:

Originally Posted by JRichardson1729
I cannot do modulo-calculations, however I don't think that $2^3^2+1$ is divisible by $5$.

$2^3^2+1$ was proven composite by Euler. Explanation in this PDF

http://www.maa.org/editorial/euler/H...oring%20F5.pdf
• Oct 25th 2010, 11:40 AM
JRichardson1729
Quote:

Originally Posted by undefined
$2^3^2+1$ was proven composite by Euler. Explanation in this PDF

http://www.maa.org/editorial/euler/H...oring%20F5.pdf

I knew of this, however I don't see how it uses the factorisation of $x^n+1$ when ${n}\geq{3}$ and is odd as the question asks for.
• Oct 25th 2010, 12:13 PM
undefined
Quote:

Originally Posted by JRichardson1729
I knew of this, however I don't see how it uses the factorisation of $x^n+1$ when ${n}\geq{3}$ and is odd as the question asks for.

Since 32 is not odd, the property does not directly apply. Maybe it is an error in the problem statement.
• Oct 25th 2010, 02:49 PM
Dinkydoe
Sorry, made a lame error in (ii)....but indeed. I agree with undefined. I don't see any relation between (ii) and the previous.
• Oct 25th 2010, 03:24 PM
JRichardson1729
I found this video, YouTube - the 5th Fermat number is not a prime (german), that shows this, but, unfortunately, I don't think that it uses the factorization of $x^n+1$ when ${n}\geq{3}$ and is odd and I don't know how to adapt it so that it does (if that is possible at all).