Why (directly!) does every number divide 9, 99, 999, … or 10, 100, 1000, …, or their product?

Question

A curiosity that's been bugging me. More precisely:

Given any integers $b\geq 1$ and $n\geq 2$, there exist integers $0\leq k, l\leq b-1$ such that $b$ divides $n^l(n^k - 1)$ exactly.

The question in the title is obviously the case when n = 10. This serves as a motivating example: if we take b = 7 and n = 10, then k = 6, l = 0 works (uniquely), and if we calculate $\dfrac{n^k - 1}{b}$, we see that it turns out to be 142857 - the repeating part of the decimal expansion of 1/7. A (very sketchy, but correct!) sketch proof, which I've included for completeness:

• Notice that $\dfrac{1}{99\dots 9} = 0.00\dots 01\; 00\dots 01\; 00\dots 01\dots$.
• Notice that $1/7$ must have either a repeating or a terminating decimal expansion: just perform the long division, and at each stage you will get remainders of 0 (so it terminates) or 1, 2, ..., 6 (so some of these will cycle in some order). It turns out the decimal expansion is repeating, and the 'repeating part' is 142857. This has length (k=)6.
• $\dfrac{1}{10^6 - 1} = 0.000001\;000001\dots$, so $\dfrac{142857}{10^6 - 1} = 0.142857\;142857\dots = 1/7$, and so $7\times 142857 = 10^6 - 1$.
• And we can do the same thing with $\dfrac{1}{10\dots 0} = 0.00\dots 01$ and terminating decimals. And the same proof of course holds in my more general setting.

But this (using the long division algorithm after spotting an unwieldy decimal expansion) feels a little artificial to me, and the statement is sufficiently general that I'm sure there must be a direct proof that I'm missing. Of course, the $n^k$ part is easy, but the $n^k-1$ part has me a little stumped. My question is: is there a direct proof of the latter part?

Thanks!

Answer 1

The statement as you've given it isn't quite true. For example, $6$ doesn't divide $10^k$ or $10^k-1$ for any $n$. What is true, however, is that every integer divides $10^a(10^b-1)$ for some $a,b$ (and similarly if you replace $10$ by any other $n$).

The "$10^k-1$" part of this (which you've correctly noticed is the more interesting half) is basically a version of Euler's totient theorem, so any proof of that would be a proof of your statement. On the other hand, if you squint at the standard proofs of Euler's theorem in the right light, they start looking an awful lot like your long division argument, so I personally wouldn't worry too much about finding a more direct proof...

Answer 2

Hint $\ $ By the pigeonhole (box) principle, the map $\rm\:k\mapsto n^k\ (mod\ b)\:$ from $\,\Bbb N\,$ to $\rm\,\Bbb Z/b\Bbb Z\:$ is not $1$-$1,$ therefore there exist naturals $\rm\:j\!+\!k > j\:$ such that $\rm\: n^{\,j+k}\equiv\,n^{\,j}\ (mod\ b),\ $ i.e. $\rm\ b\:|\:n^j(n^k-1).$

Answer 3

The claim is false as stated. Take $n = 2$, then the claim states that every number $b$ divides either $2$ or $1$. Perhaps you meant not to limit $k$. But then it's still false. Take for example $b = 6$ and $n = 2$. Certainly $6$ divides no power of $2$ (since $3$ divides no power of $2$), and also no power of $2$ minus one (since they are all odd).

However, suppose $(n,b)=1$, that is $n$ and $b$ are relatively prime. Then $b|n^{\phi(b)-1}-1$, where $\phi(b)$ is Euler's totient function. This is because $n^{\phi(b)-1} \equiv 1 \pmod{b}$. For example, if $(7,n)=1$ then $7$ divides $n^6-1$. This generalizes your example. Note $\phi(b)-1$ need not be the minimal exponent; if it is, then we say that $n$ is a primitive root modulo $b$. As an example, $7$ divides $11^3-1$. The minimal exponent always divides $\phi(b)$.