• Oct 24th 2010, 03:05 PM
JRichardson1729
I have recently happened upon an interesting problem that I cannot solve. Here it is:
a. Factorise \$\displaystyle x^3+1\$.
b. Factorise \$\displaystyle x^n+1\$ when \$\displaystyle {n}\geq{3}\$ is odd. Use this to prove the following:
i. If \$\displaystyle 2^n+1\$ is prime, then \$\displaystyle n\$ must be a power of \$\displaystyle 2\$.
ii. Show that \$\displaystyle 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, 04:10 PM
Dinkydoe
For (a),(b) show that \$\displaystyle 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 \$\displaystyle n=2^kq\$, where q is odd, then

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

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

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

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

Originally Posted by Dinkydoe
For (a),(b) show that \$\displaystyle 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 \$\displaystyle n=2^kq\$, where q is odd, then

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

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

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

Can you do modulo-calculations?

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

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

\$\displaystyle 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, 10:40 AM
JRichardson1729
Quote:

Originally Posted by undefined
\$\displaystyle 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 \$\displaystyle x^n+1\$ when \$\displaystyle {n}\geq{3}\$ and is odd as the question asks for.
• Oct 25th 2010, 11:13 AM
undefined
Quote:

Originally Posted by JRichardson1729
I knew of this, however I don't see how it uses the factorisation of \$\displaystyle x^n+1\$ when \$\displaystyle {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, 01: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, 02: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 \$\displaystyle x^n+1\$ when \$\displaystyle {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).