Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In respect to a larger proof I need to prove that $(n-m) \mid (n^r - m^r) $ (where $\mid$ means divides, i.e., $a \mid b$ means that $b$ modulus $a$ = $0$). I have played around with this for a while now but to no avail and would be grateful if you could help me.

share|improve this question

6 Answers 6

up vote 16 down vote accepted

There are several ways of proving this. For example, one can use the binomial theorem $(a+b)^r=\sum_{k=1}^r\binom{k}ra^kb^{n-k}$ with $a=n-m$ and $b=m$. (The change of variables from $n,m$ to $a,b$ is in itself a good idea in problems like this, since it tends to reduce the size of some of the expressions.)

Another way is to use the identity $$n^r-m^r=(n-m)\sum_{k=0}^{r-1}n^{r-1-k}m^k=(n-m)(n^{r-1}+n^{r-2}m+\dots+nm^{r-2}+m^{r-1}).$$

Both of these identities are proved by induction on $r$.

Or, one can do directly an inductive argument: The result is clear if $r=0$, since $n^r-m^r=0$. Given the result for $r$, prove it for $r+1$ using, for example, that $n^{r+1}-m^{r+1}=n(n^r-m^r)+m^r(n-m)$.

share|improve this answer
    
+1 for more methods of proof. –  Callum Rogers Jan 17 '11 at 0:21

This is a simple telescopic sum trick: \[ n^{r} - m^{r} = (n-m) \sum_{k=1}^{r} n^{r-k}m^{k-1} = (n - m)(n^{r-1} + n^{r-2}m + \cdots +nm^{r-2} + m^{r-1}). \]

share|improve this answer
    
Very nice, was trying some very similar to this but not with enough terms. Thanks. –  Callum Rogers Jan 17 '11 at 0:20

HINT $\ $ modulo $\rm\ n-m\ $ one has $\rm\ n\equiv m\ \Rightarrow\ n^r \:\equiv\: m^r\ $ by the congruence product rule.

share|improve this answer
    
Nice, this seems to me the most elegant and simple answer! +1 –  wildildildlife Apr 30 '11 at 20:46

If $r$ is a positive integer, simply notice that $x^r - y^r = (x-y)(x^{r-1} + x^{r-2}y + \cdots + xy^{r-2} + y^{r-1})$ as polynomials.

share|improve this answer

HINT $\ $ For $\rm\ n\to n+m\ $ it is $\rm\ n\ |\ (n+m)^r - m^r\ $ which is obvious by the binomial theorem.

Note $\ $ The above proof arises from the following trivial symmetry-inspired proof of the

Factor Theorem $\rm\ \ \ \ x - m \ |\ P(x) - P(m)\ $ in $\rm\: R[x]\:,\ $ for every ring $\rm\:R\:.$

Proof $\ $ Clear if $\rm\ m = 0\::\ \ x\ |\ P(x)-P(0)\:.\: $ Else reduce to $\rm\ m = 0\ $ by the shift $\rm\ x\to x+m\:.\ $ QED

The proof exploits an innate symmetry - the problem is invariant under shift automorphisms. Hence, with luck, we can apply these symmetries to reduce the problem to a much simpler one.

share|improve this answer

HINT $\ $ Put $\rm\ P(x) = x^r,\ \ x = n\ $ in $\rm\ x-m\ |\ P(x)-P(m)\ $ in $\rm\ \mathbb Z[x]\ $ (the Factor Theorem)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.