If m and n are natural numbers, prove that m^(2*n) is congruent to 1(mod m+1)
Note, if is odd then ,
We need to show . Thus, . If is odd then is divisible by and use the result above. If is even then . Now if is odd then is a factor by above result. Otherwise it is even and then factor and apply the same argument. Since we cannot go indefinitely it means at some point is odd and at that point has as a factor,
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 . Since f(–1)=0, it follows that for some polynomial g(x) with integer coefficients. Now we can put x=m, to get , and therefore m+1 divides .