Prove that $\frac{10^n-1}{9n}$ is integer when $n=3^k$

Question

I have no idea how to go about proving this. The furthest I've gotten is to say that the sequence equals 1/1, 11/2, 111/3, etc.

So that means that $\frac{10^a-1}{9}$ must be divisible by 3.

$\frac{10^a-1}{9} = 3b \implies 10^a-1 = 27b \implies 27b+1 = 10^a$.

When is that last statement true?

Answer 1

You can use induction to prove

$$\frac{10^n-1}{9n} \tag{1}\label{eq1A}$$

is an integer when $n = 3^k$. The base case of $k = 0$ gives $3^k = 1$, with \eqref{eq1A} becoming $\frac{10-1}{9} = 1$. Next, assume \eqref{eq1A} is an integer for $k = m$ for some integer $m \ge 0$. Then, for $k = m + 1$,

$$\begin{equation}\begin{aligned} \frac{10^{3^{m+1}} - 1}{9(3^{m+1})} & = \frac{\left(10^{3^{m}}\right)^3 - 1}{\left(9(3^{m})\right)3} \\ & = \frac{(10^{3^{m}} - 1)(10^{3^{2m}} + 10^{3^{m}} + 1)}{\left(9(3^{m})\right)3} \\ & = \left(\frac{10^{3^{m}} - 1}{9(3^{m})}\right)\left(\frac{10^{3^{2m}} + 10^{3^{m}} + 1}{3}\right) \end{aligned}\end{equation}\tag{2}\label{eq2A}$$

The first factor above is an integer based on the induction hypothesis, i.e., \eqref{eq1A} being an integer for $n = 3^{m}$. For the second factor, note

$$10 \equiv 1 \pmod{3} \implies 10^{3^{2m}} \equiv 10^{3^{m}} \equiv 1 \pmod{3} \tag{3}\label{eq3A}$$

This means

$$10^{3^{2m}} + 10^{3^{m}} + 1 \equiv 3 \equiv 0 \pmod{3} \implies 3 \mid 10^{3^{2m}} + 10^{3^{m}} + 1 \tag{4}\label{eq4A}$$

i.e., the second factor is also an integer. With the product of $2$ integers being an integer, \eqref{eq2A} shows \eqref{eq1A} is an integer for $n = 3^{m+1}$. This proves by induction that \eqref{eq1A} is an integer for $n = 3^k$ for all integers $k \ge 0$.

Answer 2

Using induction,

If $10^r=1+3^sk$ where $3\nmid k$

$$10^{3r}=(10^r)^3=(1+3^sk)^3=1+3^{s+1}k+3^{2s+1}k^2+3^{3s}k^3\equiv1\pmod{3^{s+1}}$$

for $s+1\le2s+1\iff s\ge0,3s\ge s+1\iff 2s\ge1$

Now for the base case $r=1=3^0, s=2$

So, by using weak induction, $$10^{3^a}-1$$ is divisible by $3^{a+2}$ for $a\ge0$

Answer 3

Recall a simple form (with simple proof) of LTE = Lifting The Exponent is

$$a\equiv b\!\!\! \pmod{kn}\,\Rightarrow\, a^k\equiv b^k\!\!\!\! \pmod{k^2n}$$

Applied inductively for $\,k=3\,$ (i.e. repeatedly cubing) yields the claim as follows $$\begin{align} &10^{\large 3^\color{#c00}0}\! \equiv 1\!\!\! \pmod{3^{2+\color{#c00}0}}\\ \Rightarrow\ &10^{\large 3^\color{#c00}1}\! \equiv 1\!\!\! \pmod{3^{2+\color{#c00}1}}\ \ \rm by\ \ LTE\\ \Rightarrow\ &10^{\large 3^\color{#c00}2}\! \equiv 1\!\!\! \pmod{3^{2+\color{#c00}2}}\ \ \rm by\ \ LTE\\ &\ \ \ \ \ \ \ \ \ \vdots\\ \Rightarrow\ &10^{\large 3^\color{#c00}k}\! \equiv 1\!\!\! \pmod{3^{2+\color{#c00}k}}\ \ \rm by\ \ LTE\\[.1em] \Rightarrow\ &9\cdot 3^k\mid 10^{3^k}\!\!-1\\[.1em] \Rightarrow\ & 9\cdot n\ \mid 10^n-1 \end{align}\qquad$$

Answer 4

The statement is equivalent to proving $$10^{3^k}-1\equiv_{3^{k+2}}0$$ Notice that $\phi(3^{k+2})=3^{k+2}-3^{k+1}=2\cdot 3^{k+1}$, so that for a unit $a$ we have $$a^{2\cdot 3^{k+1}}\equiv_{3^{k+2}}1$$ We also have

Claim: $$10^{3^k}\equiv_{3^{k+2}}10^{3^{k+1}}$$

Proof: $$10^{3^k}\equiv_{3^{k+2}}10^{3^{k+1}-2\cdot 3^{k}}\equiv_{3^{k+2}}10^{3^{k+1}}$$

Let $t=10^{3^k}$, then the above claim may be written as $$t^3\equiv_{3^{k+2}}t\iff t(t+1)(t-1)\equiv_{3^{k+2}}0$$ Both $t,t+1$ are units since $t,t+1\not\equiv_{3}0$, therefore we must have $t-1\equiv_{3^{k+2}}0$.