2

Show that $a^m+1$ is composite if $a$ and $m$ are integers greater than 1 and $m$ is odd.
[$Hint:$ Show that $x+1$ is a factor of the polynomial $x^m+1$]

So I tried doing it and got a result which seems erroneous.

let $m = 2k+1$, so $a^m+1 = (a+1)[(-1)^0*a^{(2k)}+(-1)^1*a^{(2k-1)}....(-1)^{(2k)}*1]$.

Since $a\gt 1, a+1 \gt 1$ so I got one part that's not 1. then I applied geometric progression on the second part and got

$a^{(2k)}*(a^{(2k-1)}-1)/(a-1)$ where $a^{(2k-1)} \gt 1, a^{(2k)} \gt 1$ therefore the second part is also an integer that's not 1. so I conclude that $a^m+1$ is composite.

demalegabi
  • 421

1 Answers1

0

Your answer is correct but there is a simple method about concluding if the factors are trivial or not, we have: $$a^m+1=a^m-(-1)^m=\underbrace{(a+1)}_{\color{#f00} p}\underbrace{\left(\sum_{i=0}^{m-1}(-1)^ia^{m-1-i}\right)}_{\color{#f00} q} $$

so we have $a^m+1=pq$ it's obvious that $p\neq 1$ and if $q=1$ then $a^m+1=p=a+1$ so $a=0,a=1$ or $a=-1$.

Elaqqad
  • 13,725
  • Thank you for your answer, but in this case why does $m$ have to be odd. wouldn't it be fine if it's even as well? Thanks. – demalegabi May 02 '15 at 14:42
  • The sufficient and necessary condition is $m$ must be divisible by an odd number greater than $1$, and in this case if $m=(2q+1)n$ then $a^t+1$ divides $a^m+1$. The conclusion fails when $m$ is not divisible by any odd number or in other words $m$ is a power of $2$. By the way welcome to ME – Elaqqad May 02 '15 at 14:46
  • Sorry, I can't really see why $m$ must be odd. why would $m=(2q+1)n$ make $a^t+1$ divide $a^m+1$ but $m=(2q+2)n$ not. Thank you for your welcome – demalegabi May 02 '15 at 14:58
  • I did not say that $m$ must be odd , I said that $m$ must have an odd divisor of the form $2q+1$ and in this case if $m=(2q+1)n$ then $a^n+1$ divides $a^m+1$. otherwise $m$ is a power of two $m=2^t$ and the number $a^{2^t}+1$ has no trivial factors – Elaqqad May 02 '15 at 15:02
  • note that $2^{2^4}+1$ is prime so when $m$ is a power of $2$ we can not do better – Elaqqad May 02 '15 at 15:03
  • I see! Thanks for your patience and explanation. :) – demalegabi May 02 '15 at 15:08