Skip to main content.

Solution to puzzle 144: Difference of two nth powers

Skip restatement of puzzle.Let a, b, and n be positive integers, with a not equal to b.  Show that n divides an − bn implies 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 congruent to b (mod p).

Lemma

If p is a prime and A, B, M are positive integers such that A congruent to B (mod pM), then Ap congruent to 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 congruent to Bp (mod pM+1).

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

Since n = pks, for some integer s, an congruent to 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 implies 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 congruent to b (mod p).

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

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

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

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

Therefore, n divides an − bn implies 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 congruent to b (mod nm), then an congruent to bn (mod nm+1).

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

Back to top