# Math Help - Divisibility

1. ## Divisibility

Hi

Prove that if $m=\alpha n$, where $m$ and $n$ are positive integers, and $\alpha$ is a positive odd integer, then $2^n+1 \mid 2^m+1$

Result due to Gauss or Euler... I can't remember... more likely to Gauss

2. Isn't it $x+1 \mid x^{2n+1} + 1$ ?

If it is correct , then $(x^n)+1 \mid (x^n)^{\alpha} +1 ~$ ... since $\alpha ~ is ~ odd$

$m=\alpha n$
$x^m = x^{\alpha n}$
$x^m + 1 = x^{\alpha n} + 1$

Therefore , $x^n + 1 \mid x^m + 1$

Finally , sub. x into 2

$2^n+1 \mid 2^m+1$

3. The fact that $\alpha$ is odd means that the expression $2^{n(\alpha-1)}-2^{n(\alpha-2)}+2^{n(\alpha-3)}-\cdots$ will end in $+1.$ Hence

$2^m+1$

$=\quad2^{\alpha n}+1$

$=\quad(2^n+1)\left(2^{n(\alpha-1)}-2^{n(\alpha-2)}+2^{n(\alpha-3)}-\cdots+1\right)$

$\implies\ 2^n+1\,\mid\,2^m+1$

4. Is it true for all positive integers $\alpha$

$2^n - 1 \mid 2^m - 1$ ??

Therefore ,

If $n \mid m ~$ , then $2^n -1 \mid 2^m - 1$ .

5. Originally Posted by simplependulum
Is it true for all positive integers $\alpha$

$2^n - 1 \mid 2^m - 1$ ??

Therefore ,

If $n \mid m ~$ , then $2^n -1 \mid 2^m - 1$ .
Yup, I’d say that’s true.

6. Originally Posted by simplependulum
Isn't it $x+1 \mid x^{2n+1} + 1$ ?

If it is correct , then $(x^n)+1 \mid (x^n)^{\alpha} +1 ~$ ... since $\alpha ~ is ~ odd$

$m=\alpha n$
$x^m = x^{\alpha n}$
$x^m + 1 = x^{\alpha n} + 1$

Therefore , $x^n + 1 \mid x^m + 1$

Finally , sub. x into 2

$2^n+1 \mid 2^m+1$

$=\quad(2^n+1)\left(2^{n(\alpha-1)}-2^{n(\alpha-2)}+2^{n(\alpha-3)}-\cdots+1\right)$
Yup, that's the key step

Here is how I did :

\begin{aligned}2^m+1 &=2^{\alpha n}+1 \\
&=(2^n)^\alpha+1 \\
&=(2^n+1-1)^\alpha+1 \\
&=1+\sum_{k=0}^\alpha {\alpha \choose k} \left\{(2^n+1)^k (-1)^{\alpha-k}\right\} \\
&=1+(-1)^\alpha +(2^n+1) \sum_{k=1}^\alpha \left\{{\alpha \choose k} (2^n+1)^{k-1} (-1)^{\alpha-k}\right\} \end{aligned}

Because $\alpha$ is odd, we have $2^m+1=(2^n+1) \sum_{k=1}^\alpha \left\{{\alpha \choose k} (2^n+1)^{k-1} (-1)^{\alpha-k}\right\}$

And since the sum is an integer, we're done