# Solution to puzzle 144: Difference of two nth powers

Let a, b, and n be positive integers, with a b.  Show that n divides an − bn n divides (an − bn)/(a − b).

Of the two approaches below, the one using Fermat's Little Theorem is more elementary, while the binomial theorem solution is perhaps easier to find.

## Solution using the binomial theorem

Let p be a prime factor of n and k be the largest positive integer such that pk divides n.  It suffices to show that pk divides (an − bn)/(a − b).

If p does not divide a − b, then (since pk divides an − bn) pk must divide (an − bn)/(a − b) and we are done.
So we may assume, without loss of generality, that p divides a − b; that is, a b (mod p).

### Lemma

If p is a prime and A, B, M are positive integers such that A B (mod pM), then Ap Bp (mod pM+1).

#### Proof

Writing A = B + rpM, where r is an integer, and using the binomial theorem, we obtain:

 Ap − Bp = (B + rpM)p − Bp = pBp−1rpM + C(p, 2)·Bp−2(rpM)2 + ... + C(p, t)·Bp−t(rpM)t + ... + (rpM)p,

where C(p, t) = p! / [t! (p − t)!] is a binomial coefficient.

In each of the above terms, the exponent of p is at least M + 1.
Hence Ap Bp (mod pM+1).

Now suppose a b (mod pm), where m 1 is the largest integer for which this congruence holds.
Applying the above lemma with A = a, B = B, M = m, we get ap bp (mod pm+1).
Then, applying the lemma with A = ap, B = bp, M = m + 1, we get (ap)p (bp)p (mod pm+2).
That is, ap2 bp2 (mod pm+2).
Similarly, after another application of the lemma, we get ap3 bp3 (mod pm+3).
Applying the lemma k times in all, we obtain apk bpk (mod pm+k).

Since n = pks, for some integer s, an bn (mod pm+k).  That is, pm+k divides an − bn.
Hence pm+k/pm = pk divides (an − bn)/(a − b).

Therefore, n divides an − bn n divides (an − bn)/(a − b).

## Solution using Fermat's Little Theorem

Again, we let p be a prime factor of n and k be the largest positive integer such that pk divides n.  It suffices to show that pk divides (an − bn)/(a − b).
Again, we may assume, without loss of generality, that a b (mod p).

Consider (Ap − Bp)/(A − B) = Ap−1 + Ap−2B + ... + ABp−2 + Bp−1.
By Fermat's Little Theorem, up u (mod p), for all integers u.
Hence (Ap − Bp)/(A − B) Ap−1 + Ap−1 + ... + Ap−1 + Ap−1 pAp−1 0 (mod p).
That is, A B (mod p) Ap Bp (mod p) and (Ap − Bp)/(A − B) 0 (mod p).

Setting A = a and B = b, we obtain a b (mod p) ap bp (mod p) and (ap − bp)/(a − b) 0 (mod p).
Setting A = ap and B = bp, we get ap bp (mod p) ap2 bp2 (mod p) and (ap2 − bp2)/(ap − bp) 0 (mod p).
...
Finally, setting A = apk−1 and B = bpk−1, we get apk−1 bpk−1 (mod p) apk bpk (mod p) and (apk − bpk)/(apk−1 − bpk−1) 0 (mod p).

Since a b (mod p), all of the above implied results hold.
Multiplying the k results of the form (apt − bpt)/(apt−1 − bpt−1) 0 (mod p), we obtain (apk − bpk)/(a − b) 0 (mod pk).

Since n = pks, for some integer s, (an − bn)/(a − b) 0 (mod pk).  That is, pk divides (an − bn)/(a − b).

Therefore, n divides an − bn n divides (an − bn)/(a − b).

## Remarks

Notice that in the proof of the above lemma we did not use the fact that p is prime.  Hence, a more general result is:

If a, b, n, and m are positive integers such that a b (mod nm), then an bn (mod nm+1).

Source: Introduction to Analytic Number Theory, by Tom M. Apostol. See exercise 5.13.