1
$\begingroup$

This should be rather straightforward, but the goal is to prove that $$3^{10^n}\equiv 1\pmod{10^n},\, n\ge 2.$$ A possibility is to use $$\begin{align*}3^{10^{n+1}}-1&=\left(3^{10^n}-1\right)\left(1+\sum_{k=1}^9 3^{10^n k}\right)\\&=\left(3^{10^n}-1\right)\left(3^{9\cdot 10^n}-1+3^{8\cdot 10^n}-1+\cdots +3^{10^n}-1+10\right),\end{align*}$$ but I don't see how this proves the equality in the question. I got only $$3^{10^{n}}\equiv 1\pmod{3^{10^{n-1}}-1}.$$ Perhaps someone here can explain.

$\endgroup$
  • $\begingroup$ Yes, corrected now. $\endgroup$ – groundlark Sep 28 at 17:44
1
$\begingroup$

Use induction

Basis $$3^{100}\equiv (3^{10})^{10}$$ $$\equiv 59049^{10}$$ $$\equiv 49^{10}$$ $$\equiv 2401^5$$ $$\equiv 1\pmod {100}$$

Induction hypothesis $$\frac{3^{10^{n}}-1}{10^n}\in\mathbb Z$$

Inductive step $$\frac{3^{10^{n+1}}-1}{10^{n+1}}$$ $$=\frac{3^{10^{n}}-1}{10^n}\times \frac{1+\sum_{k=1}^9 3^{10^nk}}{10}$$ But of the terms multiplied are integers, as the first one directly follows from induction hypothesis and second one by $$\forall 1\leq k\leq 9, 10|10^n|(3^{10^n}-1)|(3^{10^nk}-1)$$ $$\Longrightarrow 3^{10^nk}\equiv 1\pmod {10}\forall 1\leq k\leq 9$$ $$\Longrightarrow 1+\sum_{k=1}^9 3^{10^nk}\equiv 0\pmod {10}$$

Hence proved

$\endgroup$
2
$\begingroup$

The identity you used leads to a proof of the desired result by induction as follows. So suppose that $10^n$ divides $3^{10^n}-1$ for all $n=2,\ldots,N$. Applying the identity yields $$ \frac{3^{10^{N+1}}-1}{3^{10^N}-1}=10 + \sum_{k=1}^9(3^{k\cdot 10^N}-1), $$ and the right side is a multiple of $10$ since each term in the sum is a multiple of $3^{10^N}-1$.

Thus, since $10^N$ divides $3^{10^N}-1$ by the inductive hypothesis, we see that $10^{N+1}$ divides $3^{10^{N+1}}-1$ and this completes the inductive step. All that is left is to check the base case $n=2$, that $3^{100}-1$ is divisible by $100$. This is straightforward using standard modular arithmetic techniques, for instance by checking modulo $4$ and modulo $25$ separately.

$\endgroup$
0
$\begingroup$

Hint

Using the Carmichael function,

$$\lambda(10^n)=5^{n-1}(5-1)2^{n-2}$$ for $n\ge3$

So, if $(a,10)=1,$ $$a^{2^n5^{n-1}}\equiv1\pmod{10^n}$$

$\endgroup$
0
$\begingroup$

Hint:

To get to your goal $3^{10^n}\equiv 1\pmod{10^n},\, n\ge 2,$

can you prove using binomial expansion with $9=10-1$ that $9^{10^{n-1}}\equiv1\mod 10^n $?

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