# More on divisibility

Based on my students’ reactions, I gave my best math joke in years as I went over the proofs for checking that an integer was a multiple of 3 or a multiple of 9. I started by proving a lemma that 9 is always a factor of $10^k - 1$. I asked my students how I’d write out $10^k - 1$, and they correctly answered $99{\dots}9$, a numeral with $k$ consecutive $9$s. So I said, “Who let the dogs out? Me. See: $k$ nines.”

Some of my students laughed so hard that they cried.

There are actually at least three ways of proving this lemma. I love lemmas like these, as they offer a way of, in the words of my former professor Arnold Ross, to think deeply about simple things.

(1) By subtracting, $10^k - 1 = 99{\dots}9 = 9 \times 11{\dots}1$, which is clearly a multiple of 9.

(2) We can use the rule

$a^k - b^k = (a-b) \left(a^{k-1} + a^{k-2} b + \dots + a b^{k-2} + b^{k-1} \right)$

The conclusion follows by letting $a = 10$ and $b =1$.

From my experience, my senior math majors all learned the rule for factoring the difference of two squares, but very few learned the rule for factoring the difference of two cubes, while almost none of them learned the general factorization rule above. As always, it’s not my students’ fault that they weren’t taught these things when they were younger.

I also supplement this proof with a challenge to connect Proof #2 with Proof #1… why does $11{\dots}1 = \left(a^{k-1} + a^{k-2} b + \dots + a b^{k-2} + b^{k-1} \right)$?

(3) We can use mathematical induction.

If $k = 0$, then $10^k - 1 = 0$, which is a multiple of 9.

We now assume that $10^k - 1$ is a multiple of 9.

To show that $10^{k+1}-1$ is a multiple of 9, we observe that

$10^{k+1}-1 = \left(10^{k+1} - 10^k \right) + \left(10^k - 1\right) = 10^k (10-1) + \left(10^k - 1\right)$,

and both terms on the right-hand side are multiples of 9. (I also challenge my students to connect the right-hand side with the original expression $99{\dots}9$.)

$\hbox{QED}$

## One thought on “More on divisibility”

This site uses Akismet to reduce spam. Learn how your comment data is processed.