Prove that every positive integer having $3^m$ equal digits is divisible by $3^m$

Question

Prove that every positive integer having $3^m$ equal digits is divisible by $3^m$

I haven't really done anything substantial to solve this but here's what I have:

Let the positive integer be $aaa....aaa$ or simply $A$.

$A=a\cdot10^{3^m}+a\cdot10^{3^m-1}+a\cdot10^{3^m-2}+....+a$
This forms a GP, hence, $A=x\frac{10^{3^m+1}-1}{10-1}=\frac{x}{9}\ [10^{3^m+1}-1]$

Now the question wants us to prove
$3^m|A$
$3^m|\frac{x}{9}\ [10^{3^m+1}-1]$
$3^{m+2}|\ x (10^{3^m+1}-1)$
But x can be any digit so,
$3^{m+2}|\ 10^{3^m+1}-1$

I can't figure out a way to solve further. Can I get a hint as to how I can proceed with this question

I have tried induction too, but didn't really reach the conclusion:

Let P(n) be
$10^{3^n+1}-1=3^{n+2}a$

P(1):
$10^{3+1}-1$
$=10^4-1$
$=10,000-1$
$=9999$, which is divisible by $3^3=27$

Let p(m) be true,
$10^{3^m+1}-1=3^{m+2}b$

To prove: P(m+1) is also true
$10^{3^{m+1}+1}-1$
$=10^{3*3^m+1}-1$
$=10^{2*3^m}\cdot10^{3^m+1}-1$
$=10^{2*3^m}(3^{m+2}b+1)-1$

I am not able to go further...

Answer 1

We will proceed by induction on $m$ starting from $m=0$. Let $d$ be any digit from 1 to 9. We need to prove this statement for all $m\ge0$: $$S(m): 3^m\mid\underbrace{ddd\dots ddd}_{3^m}$$ Clearly $S(0)$ is true: $$3^0\mid d\to1\mid d$$ Now assume that $S(n)$ for some $n$ is true. $$3^n\mid\underbrace{ddd\dots ddd}_{3^n}$$ The concatenation of three copies of $\underbrace{ddd\dots ddd}_{3^n}$ can be represented as a product: $$\underbrace{ddd\dots ddd}_{3^{n+1}}=\underbrace{ddd\dots ddd}_{3^n}×(10^{2\cdot3^n}+10^{3^n}+1)$$ The term $\underbrace{ddd\dots ddd}_{3^n}$ is divisible by $3^n$, while $(10^{2\cdot3^n}+10^{3^n}+1)$ is divisible by 3: $$\begin{align} 10^{2\cdot3^n}+10^{3^n}+1&\equiv 1^{2\cdot3^n}+1^{3^n}+1\bmod3\\ &\equiv1+1+1\bmod3\\ &\equiv0\bmod3 \end{align}$$ Putting these terms together, we see that $$(3×3^n)\mid\underbrace{ddd\dots ddd}_{3^{n+1}}$$ $$3^{n+1}\mid\underbrace{ddd\dots ddd}_{3^{n+1}}$$ but this is precisely the statement $S(n+1)$. Thus if $S(n)$ is true then $S(n+1)$ is true. Since $S(0)$ is true, by induction $S(m)$ is true for all $m\ge0$.

Answer 2

Your idea for an inductive proof can be made to work as follows:

$\begin{eqnarray} 3^m\mid 11\cdots 11 = (10^{\large 3^{\Large m}}\!\!-1)/9\iff&\! 10^{\large 3^{\Large m}} =&\ 1 + 3^{\large m+2} k,\,\ \ \ {\rm i.e.}\ \ P(m)\\ \Rightarrow\ & 10^{\large 3^{\Large m+1}}\!\! =& (1 + 3^{\large m+2} k)^{\large 3}\\ &\qquad\ =&\ 1+ 3^{\large m+3}\, k', \ \ {\rm i.e.}\ \ P(m\!+\!1) \end{eqnarray}$

Remark $\ $ This is a special case of LTE = Lifting The Exponent Lemma