2
$\begingroup$

I can't even make sense of this question. Isn't this just like asking, "Prove that 3 is divisible by 3." Isn't any number divisible by itself? Is this all there is to this question—it seems like there must be more to it.

$\endgroup$
  • 2
    $\begingroup$ If $n = 1$, then the number that consists of $3^n$ ones is $111 = 3 \times 37$. $\endgroup$ – user153918 Feb 26 '15 at 16:49
  • 2
    $\begingroup$ "Consists of" is unclear. They intend "whose decimal representation consists of". $\endgroup$ – André Nicolas Feb 26 '15 at 16:51
  • 1
    $\begingroup$ The problem is to show that $3^n \mid {10^{3^n}-1 \over 9}$. $\endgroup$ – copper.hat Feb 26 '15 at 16:53
  • $\begingroup$ It's congruence arithmetic. $\endgroup$ – MadScientist Feb 26 '15 at 17:06
4
$\begingroup$

We can use induction. I prefer to show that the number that "consists of" $3^n$ $9$'s is divisible by $9\cdot 3^n$.

The number whose decimal representation consists of $3^n$ consecutive $9$'s is $10^{3^n}-1$.

For the induction step, note that $10^{3^{k+1}}-1=x^3-1$ where $x=10^{3^k}$. This factors as $(x-1)(x^2+x+1)$. By the induction assumption, $x-1$ is divisible by $9\cdot 3^k$. Also, $3$ divides $x^2+x+1$, so $9\cdot 3^{k+1}$ divides $x^3-1$.

Remark: Or else we could show that the number whose decimal representation consists of $3^{k+1}$ consecutive $1$'s is the number with $3^k$ consecutive $1$'s, times a number of the shape $1000\cdots 01000\cdots 01$. The second number is divisible by $3$ by the usual divisibility test.

$\endgroup$
2
$\begingroup$

What is meant is show that $111$ (so onehundred eleven) is divisible by $3^1$, and $111111111$ (the number with $3^2= 9$ times the digit $1$) is divisible by $3^2 = 9$ and so on.

The number is written using $3^n$ times the digit $1$.

Not, as you assume, $1+1+1$ and so on. This would indeed be obvious.

$\endgroup$
  • 1
    $\begingroup$ I see, thanks for the correct interpretation. $\endgroup$ – Sargon Feb 26 '15 at 16:53
1
$\begingroup$

Generalization :

If modulo order ord$_{p^k}a=d\implies a^d\equiv1\pmod{p^k},a^d=1+p^k\cdot c$ for some integer $c$ and $p$ is any integer

$\implies a^{pd}=(a^d)^p=(1+p^k\cdot c)^p\equiv1\pmod{p^{k+1}}$

Here $a=10,p=3,k=2,d=1$

So by mathematical induction, $10^n\equiv1\pmod{3^{n+1}}$ for integer $n\ge1$

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