If $a, b, c$ are any three integers, then show that $$(abc)(a^3-b^3)(b^3-c^3)(c^3-a^3)$$ is divisible by $7$.

If you know a bit about number theory, one of the first methods we can guess might work on this problem would be modular arithmetic.

Basically, through a bit of magic, it turns out that if you're only considering the reminders of some expression against, say, $7$, you can replace all the numbers with their remainders by $7$.

So, as an example, if we want to find out the remainder of $15 \cdot 37$ by $7$, we can replace the $15$ by a $1$ (since $15$ gives $1$ as a remainder when divided by $7$) and we can replace the $35$ by a $2$.

Of course, mathematicians don't go about writing long sentences every time they want to use modular arithmetic, so, they use a short notation. The example just discussed can be represented by $$15 \cdot 37 \equiv 1 \cdot 2 \equiv 2 (\pmod{7})$$

(notice the number of lines in equivalence sign, and notice how the calculation breaks down)

And, sure enough, $15*37=555$, which gives a remainder of $2$ when divided by $7$.

Now, back to the problem.

Basically, the problem is saying that we must prove $$(abc)(a^3-b^3)(b^3-c^3)(c^3-a^3) \equiv 0 (\pmod 7)$$

Firstly, we notice that we can replace each of $a$, $b$ and $c$ with their respective remainders by $7$ (often called residues mod $7$).

So, we only have to consider $$6 \ge a, b, c \ge 0$$

Hey, that's not too shabby! Can we just brute force it? Um... not quite, if you crunch some numbers (i.e. $6^3$), we see we'd still have to try $216$ different a's, b's and c's.

Let's try narrowing this down.

Well, if any of $a$, $b$ or $c$ are $0$ (remember, by that we mean divisible by $7$!), then $$(abc)(a^3-b^3)(b^3-c^3)(c^3-a^3) \equiv 0 (\pmod 7)$$

And, notice that the equation we're dealing with is symmetric; if you switch around $a$, $b$ and $c$, it doesn't make any difference! So, we only need to consider combinations of numbers, which means that $a=1$, $b=2$, $c=3$ will give the same result as $a=2$, $b=1$, $c=3$.

Also, if $a=b$, $a=c$ or $c-a$, then our expression is still divisible by $7$, because the difference of cubes expressions will turn out to be $0$.

Now, we've weeded out most of what we can just by looking at the equation, now, we have to do a bit of work to see if we can get the rest of what's missing.

What about these $a^3$, $b^3$ and $c^3$ terms? Can't we do something about those?

Let's take a bit of detour (solving a problem is a bit like climbing a mountain; you've got to retrace your steps, take detours, maybe even start over to reach the top).

What are values can $a$ take on? $$0, 1, 2, 3, 4, 5, 6$$

Of course, we don't really care when its $0$, because that means our expression is divisible by $7$, so, the ones to consider: $$1, 2, 3, 4, 5, 6$$

We can also represent these are negative remainders: $$1, 2, 3, -3, -2, -1$$

What happens when we cube these (to get $a^3$)? We get: $$1, 8, 27, -27, -8, -1$$

And, these give these residues mod $7$: $$1, 1, 6, 1, 6, 6$$

But, since there are only two distinct residues, that means in order to pick three, we'll have to repeat one, so, we've proved $$(abc)(a^3-b^3)(b^3-c^3)(c^3-a^3) \equiv 0 (\pmod 7)$$!

What you just saw (i.e. looking at $a^3$) is known as a cubic residue; there are also quadratic residues and all kinds of other interesting structures derived from these.

In order to gain the most out of this problem, you'll probably want to read this discussion again. We had a few very important moves; firstly, only considering the remainders (since its a divisibility problem) was essential, then, observing the expression to see what we could do with it was also incredibly important, and then, by looking at the cubic residues (and using the symmetric nature of the problem), we finished the problem.

blog comments powered by Disqus
Mobile and Web Analytics