Chinese Remainder Theorem Application Question

Question

How to find the remainder of $10^{5^{102}}$ mod $35$, in this question I cannot find "$a$" such that $10^a$ congruent to $1$ and use the basic trick. This makes me pretty confused, any help is really appreciated!

Answer 1

Hint: Find the quantity $\bmod 5$ (shouldn't be hard given that the base is $10$) and then find it $\bmod 7$ (using some $a$ so that $10^a\equiv 1\bmod 7$ like you mentioned). From here, splice them together with the Chinese remainder theorem.

Answer 2

$$10^{\large 25^{\LARGE n}}\!\!\bmod 35\, =\, \overbrace{5\left[ 10^{\large\color{#c00}{ 25}^{\LARGE n}}\!\!/5\bmod 7\right]\, =\, 5\left[10^{\large \color{#c00}{\bf 1}^{\LARGE n}}\!\!/5\bmod 7\right]}^{ \Large 10^{\LARGE \color{#0a0} 6}\equiv\, 1\!\pmod{\!7};\ \ \ \ \color{#c00}{25\ \equiv\ 1}\pmod{\!\color{#0a0}6}} =\, 5[2]\, =\, 10\qquad$$

Answer 3

Set $x= 10^{5^{102}}$. Clearly $$ x=0 \mod 5. $$ You have to solve now: $$ x=10^{5^{102}} \mod 7, $$ that is: $$ x=3^{5^{102}} \mod 7. $$ Since $7$ is prime and $7$ is not a divisor of $3$ , Fermat's little theorem says $$ 3^6=1 \mod 7, $$ therefore: $$ 3^{5^{102}}=3^y \mod 7 \quad \text{ if }\quad 5^{102}=y \mod 6. $$ Now, $$ y=5^{102} \mod 6,\\ y=(-1)^{102} \mod 6,\\ y=1 \mod 6. $$ This means: $$ x=3^1=3 \mod 7.\\ $$ Now, using: $$ x=0 \mod 5,\\ x=3 \mod 7,\\ $$ you should be able to prove: $$ x = 10 \mod 35. $$ (Chinese remainder theorem tells you that this solution is unique mod 35)

Answer 4

You can't find it because $10$ and $35$ are not relatively prime and there is none.

As $\gcd(10, 35)= 7$ every $10^k$ will be equivalent to a multiple of $5$. we can attempt to find $10^k \equiv 10\pmod {35}$....

But the Chinese Remeander Theorem is much easier.

CRT says: If $10^{5^{102}} \equiv j \pmod {5}$ and $10^{5^{102}} \equiv m \pmod 7$, there is unique equivalence class $n \pmod{5*7}$ so that $n\equiv j \equiv 10^{5^{102}} \pmod 5$ and $n\equiv m \equiv 10^{5^{102}}\pmod 5$. And from $m,j$ will be able to find that $n$.

$10\equiv 0 \pmod 5$ so $10^{5^{102}} \equiv 0 \pmod 5$.

Now by Fermat Little Theorem $10^6 \equiv 1 \pmod 7$. And so "the trick" is if $a = 6b + r$ or in other words is $a \equiv r \pmod 6$ then $10^a = (10^6)^b10^r \equiv 10^r \pmod 7$ so

$10^{5^{102}} = 10^{(6-1)^{102}} \equiv 10^{(-1)^{102}} =10^1\equiv 3 \pmod 7$.

So we nee to solve $n \equiv 0 \pmod 5$ and $n\equiv 3 \pmod 7$. By CRT there is one and also by CRT there is only one and as $10^{5^{102}}$ is a solution, $n \equiv 10^{5^{102}} \pmod 35$.

And as $10^k \equiv 0 \equiv 10 \pmod 5$ and $10^{5^{102}}\equiv 10 \pmod 7$ we know.... $n \equiv 10 \mod 35$ is that solution. $10 \equiv 0 \pmod 5$ and $10\equiv 3 \pmod 7$.

So $10^{5^{102}}\equiv 0 \pmod 5$ and $10^{4^{102}}\equiv 3\pmod 7\iff 10^{5^{102}} \equiv 10 \pmod 35$.