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 9s. 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.)


One thought on “More on divisibility

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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