Another in an occasional series of “problem-solving aloud” – this one is from Loren C Larson’s Problem-solving Through Problems.

4.2.22 If $a, b, c,$ and $d$ are positive integers, show that 30 divides $a^{4b+d} - a^{4c+d}$.

I raised my eyebrows at this; it surprises me that this is true. I assume it’s true. I haven’t worked it through yet. I’m going to call the expression $N$. (Give things names.)

Let’s start with a simplification: we can write it as $a^d \left( a^{4b} - a^{4c}\right)$.

That bracket is the difference of two squares, so $N=a^d\left( a^{2b}- a^{2c}\right)\left( a^{2b}+ a^{2c}\right)$

Again, there’s a difference of two squares, so $N = a^d\left( a^{b}- a^{c}\right)\left(a^{b}+a^{c}\right)\left( a^{2b}+ a^{2c}\right)$

It’s not immediately clear why this would be a multiple of 30. But my first thought is…

Modular arithmetic

Thirty is $2 \times 3 \times 5$, so if I can show that $N$ is a multiple of all three (no matter what the numbers are) then the problem is solved.

Let’s start with two. This is almost trivial:

  • if $a$ is even, then then first term is certainly even (and I think all of them are) – so $N$ has an even factor and is a multiple of 2.
  • if $a$ is odd, then the second term is the difference of two odd numbers and so $N$ has an even factor.

Whether $a$ is even or odd, $N$ is even. That’s progress!

What about three? That’s a bit more work. What do powers look like modulo 3?

  • $(3k)^p$ is a multiple of 3
  • $(3k+1)^p$ is one more than a multiple of 3.
  • $(3k-1)^p$ alternates between one less and one more than a multiple of 3. It’s one more for even powers, one less for odd.

That means $a^{2p}$ and $a^{2q}$ have the same remainder when divided by $3$, no matter what (positive integers) $a,p$ and $q$ are.

So I think the clever thing to do here is look at the second simplification, $N=a^d\left( a^{2b}- a^{2c}\right)\left( a^{2b}+ a^{2c}\right)$ – the middle factor is definitely a multiple of 3, so $N$ is a multiple of 3.

How about modulo 5?

Enlightenment

I almost jumped into another exhaustion when I realised what the question was poking at all along: we’re looking at Fermat’s Little Theorem! $a^{p-1} \pmod{p}\equiv 1$ for all primes $p$, when $a$ is a positive integer coprime to $p$.

In particular:

  • $a^1 \equiv 1 \pmod 2$ if $a$ is odd
  • $a^2 \equiv 1 \pmod 3$ is $a$ is not a multiple of 3
  • $a^4 \equiv 1 \pmod 5$ if $a$ is not a multiple of 5.

And the upshot of that is that if $p$ is 2, 3 or 5, then $a^{4k} \equiv 1 \pmod p$ if $a$ and $p$ are coprime, and equivalent to 0 if not.

That means we didn’t need to simplify beyond the first line: $a^{4b}-a^{4c}\equiv 0\pmod p$ for $p = 2, 3, 5$, so $N$ is a multiple of 2, 3 and 5 $\blacksquare$

Post-mortem

The interesting thing for me is that my instinct kind of led me along the wrong path – I didn’t need to expand all of those brackets – but at the same time, the wrong path took me to the insight that put me on the right path.

It was also interesting that the thing that made me look for the right path was laziness – I didn’t really fancy enumerating all of the possibilities modulo 5 and wondered if there was a shortcut. Noticing that $a^{2k}\pmod3$ was always 1 or 0 was the spark.

I like this one a lot. Did you approach it a different way? I’d love to hear about it!