# Number Theory: Show that $10^{3^n}\equiv 1\pmod{3^{n+2}}$ but $3^{n+3}\not\mid 10^{3^n}-1$

Show that for all $n\in\mathbb{N}$, $10^{3^n}\equiv 1\pmod{3^{n+2}}$ but $3^{n+3}\not\mid 10^{3^n}-1$.

I think I've proved this problem, but I was unsure if my proof was correct:

Proof

Let $n=1$. Then, $10^3=1000\equiv1\pmod{3^3}$ since $3^2=9\mid999$ and $3\mid111\implies 3^3\mid999$; but, $3^4\not\mid999$.

Now, assume $10^{3^n}\equiv1\pmod{3^{n+2}},3^{n+3}\not\mid10^{3^n}-1$.

We want to prove that this is true for $n+1$:

$10^{3^{n+1}}\equiv1\pmod{3^{n+3}}$

$10^{3^{n+1}}-1\equiv0\pmod{3^{n+3}}$

$(10^{3^n})^3-1\equiv0\pmod{3^{n+3}}$

$(10^{3^n}-1)((10^{3^n})^2+10^{3^n}+1)\equiv0\pmod{3^{n+3}}$.

By our assumption, $3^{n+2}\mid(10^{3^n}-1)$ but $3^{n+3}\not\mid10^{3^n}-1$, so $\gcd(3^{n+3},10^{3^n}-1)=3^{n+2}$. So,

$((10^{3^n})^2+10^{3^n}+1)\equiv0\pmod3$.

But $((10^{3^n})^2+10^{3^n}+1)$ is of the form $100\dots00100\dots001$, so the sum of its digits is $3$, so it can be divided by $3\implies ((10^{3^n})^2+10^{3^n}+1)\equiv0\pmod3$. (Just added this:) However, it cannot be divided by $3^2=9$ since the sum of these digits is not divisible by $9$.

Thus, $10^{3^{n+1}}\equiv1\pmod{3^{n+3}}$ and $3^{n+4}\not\mid 10^{3^{n+1}}-1$.

So, by induction, $10^{3^n}\equiv 1\pmod{3^{n+2}}$ but $3^{n+3}\not\mid 10^{3^n}-1$ for all $n\in\mathbb{N}$.

The "divides" part is fine. You have enough machinery set up to prove that $3^{n+3}$ does not divide $10^{3^n}-1$, but you have not proved it explicitly. Hint: You showed that a certain expression is divisible by $3$. Show it is not divisible by any higher power of $3$.

• Oh I see, I just edited the proof. Thank you! That was the part I was unsure if I had proved or not. – MathQuestion Dec 8 '15 at 1:42
• You are welcome. Yes, this does it, as I said the machinery was all set up. Each time $n$ is incremented by $1$, the exponent of the highest power of $3$ that divides is incremented by precisely $1$. Instead of referring to the decimal expansion, it would use a bit less space if one worked modulo $9$. – André Nicolas Dec 8 '15 at 1:48
• I see, I will look into working it out modulo 9. Thank you very much! – MathQuestion Dec 8 '15 at 1:55
• The point is that $((10^{3^n})^2+10^{3^n}+1)$ is trivially congruent to $3$ modulo $9$, so we don't need to bring in decimal digits. – André Nicolas Dec 8 '15 at 2:03

You can simply apply one of the Lifting The Exponent (LTE) Lemmas.

Let $\upsilon_p(m)$ denote the exponent of the highest power of $p$ that divides $m$.

If $a,b\in\Bbb Z,n\in\Bbb Z^+$, $p$ is prime, $a\equiv b\not\equiv 0\pmod{p}$, then $$\upsilon_p\left(a^n-b^n\right)=\upsilon_p(a-b)+\upsilon_p(n)$$

In this case, $10\equiv 1\not\equiv 0\pmod{3}$, so

$$\upsilon_3\left(10^{3^n}-1\right)=\upsilon_3(10-1)+\upsilon_3\left(3^n\right)=2+n$$