[30 December 2007]

I’ve been wondering why there are no cycles longer than 4 steps in multiplication graphs.

I’m not sure that what follows counts as a reason, but it’s been interesting thinking about some properties of multiplication graphs, and the result is a chain of observations that runs like this:

1. Any number can be multiplied by any number, and produces exactly one result. So in each multiplication graph each node has one outgoing arc, and (in decimal graphs) there are exactly ten arcs.
2. Since each node has an outgoing arc, there are no dead ends: each path through the graph can be extended indefinitely. One step, two, …, nine, ten, eleven.
3. Since there are paths of length ten and greater, there must be cycles in the graph. (If a path of length n contains no cycles, then it is incident to n + 1 vertices. So any path of length ten that has no cycles must touch eleven different nodes. We only have ten nodes, so the path must necessarily contain a cycle.)
4. Multiplication of evens by evens, or evens by odds, produces even numbers. So in the even-numbered graphs (i.e. those for 0, 2, 4, 6, and 8), every arc points to an even digit. And in the odd-numbered graphs, arcs which start at even digits point to even digits.
5. Multiplication of odds by odds produces odds. So in odd-numbered graphs, arcs which start at odd digits point to odd digits. And these are the only arcs that point to odd-numbered nodes, in any (decimal) multiplication graphs. I repeat: no arcs ever run from even-numbered digits to odd-numbered digits. The even digits form a sort of black hole: once you get in, you never get out.
6. As a consequence, any cycle must either visit only even digits, or only odd digits. (If it starts on an even digit, then the path can never reach an odd digit. If the cycle starts on an odd digit, and then continues to an even digit, it can never get back to any odd digit, and therefore cannot get back to its starting point.)
7. So there is an upper bound on the length of cycles in decimal multiplication graphs: five (for the five even digits or the five odd digits). Any cycle of length five must visit either all five even digits or all five odd digits.
8. Multiplying any number by (a number ending in) zero produces (a number ending in) zero. So in any multiplication graph, the arc that starts at 0 goes to 0, creating a cycle of length 1. In other words, zero is also a kind of black hole.
9. Because zero is a black hole, no cycle of length > 1 through the even digits can visit the 0 node.
10. Any cycle of length 5 over the even digits must (as noted above in item 7) visit all the even digits, and thus must visit 0. But no cycle that visits 0 can have length > 1. So: no cycle of length 5 over the even digits can exist.
11. Multiplying a number ending in 5 by any number produces a number ending in either 0 or 5. (Or, equivalently, every arc beginning at 5 in any decimal multiplication graph goes either to 5 or to 0.) So the set {0, 5} is also a black hole.
12. Because {0, 5} is a black hole, no cycle of length > 1 through the odd numbers can visit 5.
13. Any cycle of length 5 over the odd digits must visit 5. But no cycle of length > 1 can visit 5. So: no cycle of length 5 over the odd digits can exist.

Points 6, 10, and 13 seem to prove that for decimal multiplication graphs, the upper bound on cycle length is four. (And in fact there are several cycles of length four, as may be seen by inspection.)

What about multiplication graphs for positional number systems with bases other than ten?

It seems obvious that zero will be a black hole in any positional number system, so there will never be cycles that cover all the digits in the system; for numbers written in base b, there’s an upper bound on cycle length of b – 1.

Also, if b is divisible by two, then the distinction between odds and evens will be visible in the final digit of any number written in base b, in which case there will be an upper bound on cycle length of b / 2, or possibly (b / 2) – 1.

More generally, whenever b is divisible by some number n, the set of multiples of n become a black hole and limit the length of cycles.

Several new questions now come up to occupy our thoughts.

In decimal notation, the fifth power of any number ends with the same digit as the number. Is this true of fifth powers in any positional notation? It seems unlikely.

But is there always, for any base, some power with this property? That is, for any base b is there a power p such that we can usefully write an exercise like the one from Oystein Ore from which we started?

Prove that in the [base b] number system, the [nth] power of any number has the same last digit as the number itself.

It seems plausible, but why should this be so?

And on closer examination, I find it’s not true. But why not?

Here’s the first counter-example I found. For octal numbers, there is no power with this property. In octal, no higher power of a number ending in 2 ends in 2; they all end in 4 or 0.

What property of the base determines (a) whether there is such a p, and (b) what the value of p is? (Conjecture: it has something to do with the factors and the prime factors of b. But what?)