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

Solution 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...

Solution 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).$

Solution 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)$.