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:


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$:





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,


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

  • $\begingroup$ Oh I see, I just edited the proof. Thank you! That was the part I was unsure if I had proved or not. $\endgroup$ – MathQuestion Dec 8 '15 at 1:42
  • $\begingroup$ 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$. $\endgroup$ – André Nicolas Dec 8 '15 at 1:48
  • $\begingroup$ I see, I will look into working it out modulo 9. Thank you very much! $\endgroup$ – MathQuestion Dec 8 '15 at 1:55
  • $\begingroup$ 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. $\endgroup$ – 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



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.