Multiplication in Base 10

First I should tell you about products. A product is a number that isn't prime, but that also has no factors of 2, 3, or 5. In other words, it's a product of two or more nontrivial primes. (I might call a product in that sense an urticator.product.) It's useful for some purposes to be familiar with products, so I've studied them from time to time.

One thing that at first surprised me and even now fascinates me is that there are products that end in 99. 13 × 23 = 299 … strange! 17 × 47 = 799 … very strange! It's a completely irrational reaction. On the theoretical side, products that end in 99 aren't especially uncommon. On the practical side, many products that end in 99 aren't strange at all: 29 × 31 = 899 is just the equation (x−1)(x+1) = x²−1 in disguise, while 11 × 109 = 1199 is about as dull as can be. Nevertheless, I'm fascinated … there's just something about that 99 at the end.

As I learned more products, I noticed that there were dependencies among the ones that end in 99. For example, the fact that 7 × 257 = 1799 follows immediately from the fact that 7 × 157 = 1099, which in turn follows from the fact that 7 × 57 = 399. (Of course, 399 isn't really a product; if it were, maybe I would have noticed the pattern sooner.) By the way, similar dependencies exist for all products, not just ones that end in 99, and are very useful as mnemonic devices. The idea's the same as in small factor III (point 7 of Multiplication), but here it's just a little bit more general.

Then, one day, I ran into another dependency, another seemingly-new product that in fact sprang from a familiar root, and I got to wondering … how many of those root products were there? Was it possible that I knew all of them already? I sat down with pen and paper to investigate, and quickly realized that I'd asked the wrong question. Instead of thinking of 1099 and 1799 (say) as part of a chain of dependencies that started with the root product 399, I needed to think of all three as manifestations of the underlying fact that 07 × 57 ≡ 99 mod 100.

By the way, the dependencies don't just form chains, they form kind of a mesh structure, not unlike the structure of the integers themselves. For example, every seventh number that ends in 99 is divisible by 7, every eleventh number by 11, and so on. I haven't pursued it yet, but I bet that statement leads to some good insights about primes. If nothing else, it certainly leads to Dirichlet's theorem.

So, anyway, once I had the right question, I was able to work out the answer. How many underlying facts about multiplication mod 100 are there? Let's see … there are 100 different numbers mod 100. Of those, 60 have factors of 2 or 5, factors that never go away under multiplication, so there are only 40 that can possibly multiply to give 99. And, as it happens, all those that can, do, and in pairs, so that there are 20 underlying facts, 20 pairs of numbers that multiply to give 99 mod 100.

About that “as it happens” … the 40 numbers we're talking about are the ones that end in 1, 3, 7, and 9; together they form the group U₁₀₀. The group structure guarantees that for every number x, there's some number y such that xy ≡ 99, but it doesn't guarantee that y will be different from x. So, the interesting aspect here is that the numbers always multiply in pairs. To put it another way, there's no number x such that x² ≡ 99 mod 100; in mathematical jargon, 99 isn't a quadratic residue (mod 100). The analogous fact is true in all even bases, and in some odd ones, but not in all of them.

I'm not going to list the 20 pairs; you can work them out for yourself easily enough if you want.

From there, I could hardly help thinking about inverses. For every number x, there's also a number z such that xz ≡ 01, and that number is the multiplicative inverse of x, usually written as x⁻¹ in this context. The numbers that multiply to give 99 are closely related to inverses; in fact the number y, above, is just −x⁻¹.

xy = x(−x⁻¹) = −(xx⁻¹) ≡ −01 ≡ 99

The minus signs ought to bother you a little … U₁₀₀ is only a group under multiplication, so we shouldn't be adding or subtracting things. The reason it's OK here is that we're not really subtracting, only negating: we can think of −n as the product (−1)n instead of the difference 0−n.

I will list some of the inverse pairs.

01 × 01
11 × 91
21 × 81
31 × 71
41 × 61
51 × 51

See the pattern? Let's write it down explicitly: a1 × b1 ≡ 01 mod 100 if and only if a + b ≡ 0 mod 10. Of course, the first and last lines aren't pairs in the sense I used earlier, pairs consisting of two different numbers; that changes the count of underlying facts but doesn't affect the pattern. (The numbers 49 and 99 are also self-inverse, by the way.)

These inverse pairs are more interesting.

03 × 67
13 × 77
23 × 87
33 × 97
43 × 07
53 × 17
63 × 27
73 × 37
83 × 47
93 × 57

Again, there's a pattern: a3 × b7 ≡ 01 mod 100 if and only if a − b ≡ 4 mod 10. This time, though, it's not obvious why the pattern holds.

It's not hard to derive, actually. If we expand a3 × b7 like so,

(10a + 3) × (10b + 7) = (100ab + 70a + 30b + 21),

then clearly the condition for being inverse is that 7a + 3b + 2 ≡ 0 mod 10, or rather that 7a + 3b ≡ 8. Multiply by 3, and that's the pattern rule. Still, there's nothing in there that strikes me as a reason. Why do we subtract and not add? Why 4? Who knows, that's just how it happens to turn out.

Now I'd like to go backward for a second. I started by talking about products that end in 99, then moved to 99-pairs and 01-pairs (inverses) … but what about products that end in 01? Well, for one thing, yes, there are some; the first two are 7 × 43 = 301 and 17 × 53 = 901. For another thing, in general they don't fascinate me. The one exception is 7 × 11 × 13 = 1001, but that's not really the same thing, since I'm fascinated by its function, not its form; see for example the essay In Other Bases.

Now let's go forward again! From inverses, it was only a small step to thinking about the whole group structure of U₁₀₀. In the abstract, of course, I already knew all about the structure: just follow the rules from The Structure of U_n, and the group decomposes into a product of cyclic groups, like so.

U₁₀₀ = U_2² × U_5² = Z₂ × Z₂₀ = Z₂ × Z₄ × Z₅

I wanted something a little more down to earth, though, so I decided to make a multiplication table like the ones I'd made in Multiplication in Base 7. I couldn't use exactly the same procedure as before, because 10 isn't prime, but I was able to construct tables for base 2 and base 5 separately and then put them together to get the desired result. Yay! (That's really not something to take for granted. For higher powers of 10, there's no way to put the pieces together to get a single table … at least, not a two-dimensional one.)

Here's the table for base 5, for the group U_5².

The numbers are in base 5, of course. With appropriate changes, all the remarks I made about the U_7² table apply; I won't repeat them except to explain how the table works.

The number 01 in the lower left is the origin. The number 02 (for example) is one step over and two steps up from there, so to multiply any number by 02, you just take one step over and two steps up: 02 × 02 ≡ 04, 04 × 02 ≡ 13, 13 × 02 ≡ 31, etc.

One unusual feature of the table is that it's simple to reconstruct the bottom row. The center element is always −1 (in any base); converting that to standard form mod 25 gives 44. Then, converting it to nonstandard form gives 144, which has the obvious square root 12. That can go in the left-hand spot, then for the right-hand spot we can calculate 44 × 12 ≡ 33, or just observe that it's the other square root, −12. And, by the way, yes, 12² is 144 in any base … that's another instance of the “numbers as polynomials” idea that I discussed at the end of the essay Repunits.

For completeness, here's the table for base 2, for the group U_2².

How do we put the two tables together? Well, the combined table is going to contain numbers mod 100, and any number mod 100 is determined by its values mod 4 and mod 25, so the combined table ought to have three coordinates, two to represent the value mod 25 and one to represent the value mod 4. In short, it ought to be three-dimensional! If we imagine that the number 11 in the base-2 table lies above the number 01 instead of next to it, then the combined table will look like two parallel copies of the base-5 table, one above the other.

The values here are completely determined by the values in the previous tables! Which number goes in the 14-position on the 11-plane? Well, 14 in base 10 is 9, and 11 in base 10 is 3, so we want the number between 0 and 100 that's congruent to 9 mod 25 and to 3 mod 4. There are clever ways to solve multiple congruences, but here we can just use brute force: write down the four numbers that are congruent to 9 mod 25 …

09 34 59 84

… and pick out the one that's congruent to 3 mod 4.

That's the natural form of the multiplication table for U₁₀₀, but it's not the only possible form. As a matter of presentation I might think about rearranging the rows so that the left-hand column is in order; that's an easy change. I want to make a more radical change, though. The element 11 has order 10, so we can pick that as the vertical generator and roll the table out like dough into a nice two-dimensional form! While we're at it, we might as well pick the nice small number 07 as the horizontal generator, and voilà!

The number 07 plays a special role here. It's one of only four possible horizontal generators (pure orange), which makes it moderately interesting … until you realize that the other three possibilities can be expressed as −07 and 50±07, and then it's amazing! There's a fundamental seven-ness built into multiplication in base 10! I only realized that myself just now, as I was writing.

Here's another way to say the same thing. Because of its special position in the table, we can multiply by 07 by just taking one step to the right. If we start from 01 and multiply by 07 four times, we get right back to where we started … so the fundamental seven-ness built into multiplication is really nothing but another version of the same old fact that 7⁴ = 2401! (For more about 2401, see near the end of the essays Powers of N and The Usual Random Thoughts.)

So, there you have it … from products to pairs to group structure to 2401, which in fact is a product itself.

Finally, speaking of random thoughts, here are some.

• By strange coincidence, a friend of mine independently pointed out this little fact, which is related, and which I'd never seen before.

  1 + 7 + 49 + 343 = 400

  You can prove that the sum has to end in 00 by looking at the bottom row of the table, or by summing the geometric series to get (2401−1)/(7−1).

• Can you construct a generalized table that includes the other 60 numbers mod 100? I think it's possible, but I've only done it mod 10 so far.
• The table can be used to “compute” discrete logarithms mod 100. The group U₁₀₀ isn't cyclic, so there's no single generator g such that any number can be written as g^a for some a, but we can certainly write any number as 07^a11^b … just read off the table coordinates!