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?



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

  • $\begingroup$ The "correct" proof of Euler's theorem uses elementary group theory, and no calculations at all! (unless you're interested in the value of $\phi(n)$) $\endgroup$ – Yuval Filmus Sep 30 '12 at 0:39
  • 2
    $\begingroup$ @YuvalFilmus: But the "proof by long division" doesn't really involve any calculations either, just the facts that 1) the set of remainders mod $n$ is finite and 2) long division to find the decimal representation of $1/n$ is deterministic and requires only a remainder as input at each step. They're really not all that far apart; both of them boil down to some basic facts about permutations of a finite set... $\endgroup$ – Micah Sep 30 '12 at 0:44
  • $\begingroup$ So it is. I'm rather embarrassed that I didn't spot that - it's been a while. Thank you! $\endgroup$ – Billy Sep 30 '12 at 0:53

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

  • $\begingroup$ Yep. Unfortunately I misstated the conditions when I posted this last night, so I had no chance of proving it, but now that I've stopped being silly, it's easy. Thank you! $\endgroup$ – Billy Sep 30 '12 at 14:11

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

  • $\begingroup$ Of course, I meant to bound k above by b-1, not n-1. And thanks for pointing out that this is just Euler's totient function - I'm embarrassed not to have spotted it! $\endgroup$ – Billy Sep 30 '12 at 0:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.