# Math Help - Prove

1. ## Prove

If m and n are natural numbers, prove that m^(2*n) is congruent to 1(mod m+1)

2. ## I'm sure that there is a better way, but I think this works.

Originally Posted by mandy123
If m and n are natural numbers, prove that m^(2*n) is congruent to 1(mod m+1)
We need to show that $(m+1)|(m^{2n}-1)$

rewriting we get...

$(m+1)|(m^n-1)(m^n+1)$

so it is sufficient to show m+1 divides either of them...

define q

$q=\sum_{i=0}^{n-1}(-1)^im^{(n-1)-i}$

so multiplying (m+1)q we get...

$(m+1) \cdot \sum_{i=0}^{n-1}(-1)^im^{(n-1)-i}=\left(\sum_{i=0}^{n-1}(-1)^im^{(n)-i}\right)+\sum_{i=0}^{n-1}(-1)^im^{(n-1)-i}$

By telescoping the sum we get..

$m^n+1$ if n is odd or

$m^n-1$ if n is even.

Then we get...

$(m+1)q=m^n+1$ or $(m+1)q=m^n-1$

This show s that

$(m+1)|(m^n+1)$ or $(m+1)|(m^n-1)$

3. Note, if $k$ is odd then $x^k + 1 = (x+1)(x^{k-1} - x^{k-2}+...-x+1)$,

We need to show $(m+1)|(m^{2n}-1)$. Thus, $(m+1)|(m^n-1)(m^n+1)$. If $n$ is odd then $m^n+1$ is divisible by $m+1$ and use the result above. If $n$ is even then $m^n - 1 = (m^{n/2} - 1)(m^{n/2}+1)$. Now if $n/2$ is odd then $m+1$ is a factor by above result. Otherwise it is even and then factor $m^{n/2} - 1 = (m^{n/4} - 1)(m^{n/4} + 1)$ and apply the same argument. Since we cannot go indefinitely it means at some point $n/2^i$ is odd and at that point $m^{n/2^i}+1$ has $m+1$ as a factor,

4. Originally Posted by mandy123
If m and n are natural numbers, prove that m^(2*n) is congruent to 1(mod m+1)
To show that m+1 divides $f(m) = m^{2n} - 1$, you can use the factor theorem. This says that m+1 will be a factor of f(m) if f(–1)=0. But that is obvious, since $(-1)^{2n}=1$.

5. Originally Posted by Opalg
To show that m+1 divides $f(m) = m^{2n} - 1$, you can use the factor theorem. This says that m+1 will be a factor of f(m) if f(–1)=0. But that is obvious, since $(-1)^{2n}=1$.
after looking at the other solutions, this one is nice and concise! but question: doesn't the fact that m and n are natural numbers mean we cannot have m = -1, which is what you seem to be saying, or is there something i am missing?

6. Originally Posted by Jhevon
after looking at the other solutions, this one is nice and concise! but question: doesn't the fact that m and n are natural numbers mean we cannot have m = -1, which is what you seem to be saying, or is there something i am missing?
Perhaps it will make it clearer if I modify the notation slightly. The factor theorem holds for the ring of polynomials with integer coefficients, so it applies to the polynomial $f(x) = x^{2n}-1$. Since f(–1)=0, it follows that $x^{2n}-1 = (x+1)g(x)$ for some polynomial g(x) with integer coefficients. Now we can put x=m, to get $m^{2n}-1 = (m+1)g(m)$, and therefore m+1 divides $m^{2n}-1$.