[29 December 2007]
As mentioned elsewhere, I’ve been amusing myself reading Oystein Ore,
Prove that in the decadic number system the fifth power of any number has the same last digit as the number itself.
This has led me to spend time thinking about various kinds of graphs which seem somehow related to this problem and to the more general topics of number theory it illustrates.
Exponentiation graphs
Simplest are perhaps what I’ll call ‘exponentiation graphs‘, one graph for each decimal digit. They show what happens to the last digit of a number when it’s raised to a (non-negative, integral) power. (Brief digression. Yes, to be correct I should say “the last digit in the decimal representation of a number”, not just “the last digit of the number”. But the shorter form is shorter, and in context not really less clear. So if your inner pedant was wanting to correct me just now, please forgive me this informality. And if not, please forgive me for the eighty-three words it is costing me to tell my own inner pedant to put a sock in it.)
The exponentiation graph for the digit 3, for example, starts with (a node for) the digit 1 (which is the final digit of 3, or any number ending in 3, raised to the 0th power), then a node for the digit 3 itself (the first power), then 9 (for any number ending in 3, the square ends in 9), then 7, then 1 again.
Each exponentiation graph starts with (a node for) the digit 1, and in each we can trace a path n steps long to find the digit that will end the nth power of any number which ends in the digit for which the graph is constructed.
All ten of the graphs are drawn on a separate page, if you want them.
Multiplication graphs
Each exponentiation graph is actually just part of a larger graph, which shows for (numbers ending in) each digit d what the final digit x will be when that number is multiplied by a number ending in digit y: there is an arc from y to x.
The full multiplication graph for 3 is as follows; you can see that the exponentiation graph shown above is a subgraph of this.
These graphs I’ve also drawn; they are also on a separate page, if you want them. Thank heavens for graphviz!
Power graphs
We can imagine yet another kind of graph, which I’ll call a power graph. One power graph for each non-negative integer n; each graph has ten nodes 0-9, and in each case there is an arc from x to y if and only if a number whose last digit is x, when raised to the power n, produces a result whose last digit is y.
Drawing these is an exercise left for the reader and/or the future.
Ore’s question, recast
Ore’s exercise 2-3.5, translated into graph terms, amounts to this: prove that for each of the ten exponentiation graphs (or: each of the ten multiplication graphs), the paths starting at node 1 with length 1 and length 5 end up at the same node.
This will be true whenever there is a cycle of length 1, 2, or 4 starting from the node after 1 (which is always the node for the digit whose graph this is).
Or another formulation: prove that for the fifth-power graph, each node has an outgoing arc leading back to itself.
And now I can repeat the question that struck me when I started thinking about these graphs the other day: why do all the cycles in the multiplication graphs have length 1, 2, or 4? Why do none of them have length > 4?
I don’t know exactly what a satisfactory answer to this question will look like: what I want is an explanation, any explanation, that makes me say “Oh, right. Of course.“ (In the back of my mind, I’m remembering that morning when I first encountered the proof of the formula for the sum of the interior angles of a convex polygon, and the quiet click my mind made when I understood it. But I’ll take what I can get, click or no click.)
I do have some ideas. But this post is already longer than I intended, and what with drawing the pictures it has taken a lot longer to prepare than I expected. So my current attempts at understanding why there can’t be cycles of length > 4 will have to wait for another entry.