2
$\begingroup$

I know it is obvious that $10^k-1$ will always be divisible by $9$ for some integer $k$, but I am curious how to actually prove this.

$$10^k - 1 \equiv 0 \bmod 9$$

$$10^k \equiv 1 \bmod 9$$

... and I have no idea where to go from here.

$\endgroup$
  • 4
    $\begingroup$ Start from $10\equiv 1\pmod{9}$. $\endgroup$ – André Nicolas Jul 25 '16 at 0:20
5
$\begingroup$

It's just that $10$ is $1$ modulo $9$, and modulo being compatible with multiplication. So $10^k \equiv 1^k \equiv 1 \mod 9$.

More generally this shows that $(a+1)^k \equiv 1 \mod a$. Indeed, writing it this way suggests another proof:

Expanding $(a+1)^k$ using the binomial theorem one see it is of the form $1+ a N$ for some integer $N$.

$\endgroup$
  • $\begingroup$ How do we know that the congruence holds in exponentiation? Is it always true that if $a \equiv b \bmod c$ then $a^k \equiv b^k \bmod c$ $\endgroup$ – KaliMa Jul 25 '16 at 0:34
  • $\begingroup$ Yes this is always true. More generally it is true that $a\equiv b \mod n$ and $c \equiv d \mod n$ then $ac \equiv bd \mod n$. See for instance this answer for basic rules for congruence $\endgroup$ – quid Jul 25 '16 at 0:38
13
$\begingroup$

Other Way $$10^k-1=(10-1)(10^{k-1}+10^{k-2}+\cdots+1)$$

$\endgroup$
  • $\begingroup$ 9999...9=9x1111...1 $\endgroup$ – Widawensen Jul 28 '16 at 8:22
4
$\begingroup$

Since you've tagged modular arithmetic: $$\begin{align*}10 \equiv 1 \pmod{9} \implies 10^k &\equiv 1^k \pmod{9} \\ 10^k &\equiv 1 \pmod{9} \\ 10^k -1 &\equiv 0\pmod{9}\end{align*}$$

$\endgroup$
3
$\begingroup$

The question seems to be:

Why is $\underbrace{ 99\dots 99}_n$ a multiple of $9$?

It is clear, since it is $\underbrace{ 11\dots 11}_n\times 9$

$\endgroup$
  • $\begingroup$ Yes, that is my question. I am asking how you'd prove this formally without noticing the obvious (that $10^k-1$ is all $9$'s) $\endgroup$ – KaliMa Jul 25 '16 at 0:24
  • $\begingroup$ I added a bit, maybe that makes it simpler to understand. $\endgroup$ – Jorge Fernández Hidalgo Jul 25 '16 at 0:27
1
$\begingroup$

When a question involves specific number (in this case $10$) one has to use special property of that number.

The special property of 10 relevant to our interest here is that it is one more than 9. Now we can use binomial theorem to expand
$10^k =(9+1)^k$. In the binomial expansion on RHS except the final term $1^k$ all other terms are multiples of powers of $9$. So moving that exceptional term to LHS we get $10^k-1$ is a multiple of $9$.

$\endgroup$
1
$\begingroup$

By induction: When $k = 1$, $10^k - 1 = 9$ is divisible by $9$.

Now suppose $k \geq 2$, and $10^{k-1}-1$ is divisible by $9$. By induction, we can write $10^{k-1} - 1 = 9a$ for some integer $a$. Then $$10^k - 10 = 90a$$ Add $9$ to both sides: $$10^k - 1 = 90a + 9 = 9(10a+1)$$ so $10^k - 1$ is divisible by $9$.

$\endgroup$

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.