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 $\displaystyle (m+1)|(m^{2n}-1)$

rewriting we get...

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

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

define q

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

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

$\displaystyle (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..

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

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

Then we get...

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

This show s that

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

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

We need to show $\displaystyle (m+1)|(m^{2n}-1)$. Thus, $\displaystyle (m+1)|(m^n-1)(m^n+1)$. If $\displaystyle n$ is odd then $\displaystyle m^n+1$ is divisible by $\displaystyle m+1$ and use the result above. If $\displaystyle n$ is even then $\displaystyle m^n - 1 = (m^{n/2} - 1)(m^{n/2}+1)$. Now if $\displaystyle n/2$ is odd then $\displaystyle m+1$ is a factor by above result. Otherwise it is even and then factor $\displaystyle 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 $\displaystyle n/2^i$ is odd and at that point $\displaystyle m^{n/2^i}+1$ has $\displaystyle 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 $\displaystyle 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 $\displaystyle (-1)^{2n}=1$.

5. Originally Posted by Opalg
To show that m+1 divides $\displaystyle 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 $\displaystyle (-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 $\displaystyle f(x) = x^{2n}-1$. Since f(–1)=0, it follows that $\displaystyle x^{2n}-1 = (x+1)g(x)$ for some polynomial g(x) with integer coefficients. Now we can put x=m, to get $\displaystyle m^{2n}-1 = (m+1)g(m)$, and therefore m+1 divides $\displaystyle m^{2n}-1$.