0
$\begingroup$

If $a^n + 1$ is prime for some numbers $a \geq 2$ and $n\geq 1$, show that n must be a power of 2.

I understand how to do this proof. Specifically by showing that $x^n + 1$ is composite. My question is how to come up with the notion to show that $(x+1)$ divides $x^n + 1$. My prof used a hand wavy argument stating that because $x^m + 1$ equals 0 when $x = -1$ But that does not comvince me in the slightest. I am not seeing how that implies divisibility.

$\endgroup$
  • $\begingroup$ $x+1$ doesn't always divide $x^n+1$, but that is not necessary here. See my answer. $\endgroup$ – TonyK Feb 24 '16 at 18:32
3
$\begingroup$

Your teacher was probably trying to quickly show that:
$x^{2n+1} + 1 = (x+1)(x^{2n}-x^{2n-1}+x^{2n-2}- ... +x^2-x+1)$

The signs there in the RHS are alternating i.e. $+,-,+,-,$ etc.

Note that this formula is true only if $m=2n+1$ is odd.

In general, note that if a polynomial (like e.g. $x^{2n+1}+1$) has a root $a$, then that polynomial is divisible by $(x-a)$. Since $x^{2n+1}+1$ obviously has a root $-1$, it means it's divisible by $(x+1)$.

$\endgroup$
  • 1
    $\begingroup$ The statement is true for even $n$ too, as long as $n$ is not a power of $2$. $\endgroup$ – TonyK Feb 24 '16 at 18:38
  • $\begingroup$ @TonyK I was talking about the polynomial formula only. $\endgroup$ – peter.petrov Feb 24 '16 at 18:40
  • $\begingroup$ You were trying (unsuccessfully) to read the teacher's mind. This is a perfectly valid exercise, and you missed the point of it. $\endgroup$ – TonyK Feb 24 '16 at 18:57
1
$\begingroup$

Since (-1)^m + 1 = 0 when m is odd, we have that -1 is a root of $x^m + 1$ for m odd. Therefore $x - (-1) = x + 1$ divides $x^m + 1$ since x^m + 1 is the product of linear factors of its roots.

$\endgroup$
0
$\begingroup$

Polynomial division with remainder is always possible. That is, we can certainly find polynomials $q(x)$, $r(x)$ such that $x^n+1=q(x)\cdot (x+1)+r(x)$ and $\deg r<\deg(x+1)$. The latter condition makes $r$ constant and the value of that constant can be found by evaluating at $x=-1$.

$\endgroup$
  • $\begingroup$ So $r=0$ if $n$ is odd, and $r=2$ if $n$ is even... $\endgroup$ – TonyK Feb 24 '16 at 18:32
0
$\begingroup$

$x+1$ doesn't necessarily divide $x^n+1$ (for instance, $2+1$ doesn't divide $2^6+1=65$). But it does if $n$ is odd and $\ge 3$, as more than one alternative answer demonstrates.

And if $n$ is not odd, but is not a power of $2$, then $n$ can be expressed as $uv$ where $u$ is an odd number $\ge 3$. And now $x^v+1$ divides $(x^v)^u+1 = x^n+1$.

In our example, we have $n=6$, so $u=3$ and $v=2$. And indeed $2^2+1$ divides $65$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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