Intereting Posts

How one should solve $x^2+\frac{81x^2}{(x+9)^2}=40$
Split exact sequences
Prove that a metric space is countably compact if and only if every infinite sequence in $X$ has a convergent subsequence.
Primary ideals of Noetherian rings which are not irreducible
Idea behind definitions in math
Finding the unique rock with its weight
Rudin Theorem 3.27
Proof $\int_{-\infty}^\infty\frac{dx}{\left(e^x+e^{-x}+e^{ix\sqrt{3}}\right)^2}=\frac{1}{3}$
Characterize the integers $a,b$ satisfying: $ab-1|a^2+b^2$
If $n^2+4n+10$ is a perfect square, then find the possible integer values of $n$.
Linear independence of $\sin(x)$ and $\cos(x)$
Definition of the $\sec$ function
A ‘strong’ form of the Fundamental Theorem of Algebra
What is closed-form expression for $F(n)$ when $F(n)=F(n-1)+F(n-2)$ and $F(0)=a$,$F(1)=b$ and $a,b>0$?
Sobolov Space $W^{2,2}\cap W^{1,2}_0$ norm equivalence

I stumbled across this problem

Find the remainder when $10^{5^{102}}$ is divided by 35

Beginning, we try to find a simplification for $10$ to get:

$$10 \equiv 1 \text{ mod } 7\\ 10^2 \equiv 2 \text{ mod } 7 \\ 10^3 \equiv 6 \text{ mod } 7$$

- Prove the following: If $a \mid bc$, then $a \mid \gcd(a, b)c$.
- Prove $7$ divides $13^n- 6^n$ for any positive integer
- Multiplication Table with a frame and picture of equal sum
- Can a finite sum of square roots be an integer?
- Solving a little Diophantine equation:$(n-1)!+1=n^m$
- Number of permutations which fixes a certain number of point

..As these problems are meant to be done without a calculator, calculating this further is cumbersome. The solution, however, states that since $35 = 5 \cdot 7$, then we only need to find $10^{5^{102}} \text{ mod } 7$. I can see (not immediately) the logic behind this. Basically, since $10^k$ is always divisible by $5$ for any sensical $k$, then:

$$10^k – r = 5(7)k$$

But then it’s not immediately obvious how/why the fact that $5$ divides $10^k$ helps in this case.

My question is, is in general, if we have some mod system with $a^k \equiv r \text{ mod } m$ where $m$ can be decomposed into a product of numbers $a \times b \times c \ \times …$, we only need to find the mod of those numbers where $a, b, c…..$ doesn’t divides $a$? (And if this is the case why?) If this is not the case, then why/how is the solution justified in this specific instance?

- Is a vector of coprime integers column of a regular matrix?
- How do you find all $n$ such that $\phi(n)|n$
- What is a residue class?
- For prime $p>2: 1^23^25^2\cdot\cdot\cdot(p-2)^2 \equiv (-1)^{\frac{p+1}{2}} \pmod p$
- Prove $\frac{a^3+b^3+c^3}{3}\frac{a^7+b^7+c^7}{7} = \left(\frac{a^5+b^5+c^5}{5}\right)^2$ if $a+b+c=0$
- Euclidean Algorithm - find $\gcd(172, 20)$ and solve $172a + 20b = 1000$.
- Prove that the product of primes in some subset of $n+1$ integers is a perfect square.
- Prove that there are infinitely many natural numbers $n$, such that $n(n+1)$ can be expressed as sum of two positive squares in two distinct ways.
- Can we prove this inequality in another way?
- Find all the numbers $n$ such that $\frac{12n-6}{10n-3}$ can't be reduced.

The “logic” is that we can us a **mod distributive law** to pull out a common factor $\,c=5,\,$ i.e.

$$ ca\bmod cn =\, c(a\bmod n)\quad\qquad $$

This decreases the modulus from $\,cn\,$ to $\,n, \,$ simplifying modular arithmetic. Also it may eliminate CRT = Chinese Remainder calculations, eliminating needless inverse computations, which are much more difficult than above for large numbers (or polynomials, e.g. see this answer).

This distributive law is often more convenient in congruence form, e.g.

$$\quad \qquad ca\equiv c(a\bmod n)\ \ \ {\rm if}\ \ \ \color{#d0f}{cn\equiv 0}\ \pmod{\! m}$$

because we have: $\,\ c(a\bmod n) \equiv c(a\! +\! kn)\equiv ca+k(\color{#d0f}{cn})\equiv ca\pmod{\!m}$

e.g. in the OP: $\ \ I\ge 1\,\Rightarrow\, 10^{\large I+N}\!\equiv 10^{\large I}(10^{\large N}\!\bmod 7)\ \ \ {\rm by}\ \ \ 10^I 7\equiv 0\,\pmod{35}$

Let’s use that. First note that exponents on $10$ can be reduced mod $\,6\,$ by little Fermat,

i.e. notice that $\ \color{#c00}{{\rm mod}\,\ 7}\!:\,\ 10^{\large 6}\equiv\, 1\,\Rightarrow\, \color{#c00}{10^{\large 6J}\equiv 1}.\ $ Thus if $\ I \ge 1\ $ then as above

$\phantom{{\rm mod}\,\ 35\!:\,\ }\color{#0a0}{10^{\large I+6J}}\!\equiv 10^{\large I} 10^{\large 6J}\!\equiv 10^{\large I}(\color{#c00}{10^{\large 6J}\!\bmod 7})\equiv \color{#0a0}{10^{\large I}}\,\pmod{\!35} $

Our power $\ 5^{\large 102} = 1\!+\!6J\ $ by $\ {\rm mod}\,\ 6\!:\,\ 5^{\large 102}\!\equiv (-1)^{\large 102}\!\equiv 1$

Therefore $\ 10^{\large 5^{\large 102}}\!\! = \color{#0a0}{10^{\large 1+6J}}\!\equiv \color{#0a0}{10^{\large 1}} \pmod{\!35}\ $

**Remark** $\ $ For many more worked examples see the complete list of linked questions. Often this distributive law isn’t invoked by name. Rather its trivial proof is repeated inline, e.g. from a recent answer, using $\,cn = 14^2\cdot\color{#c00}{25}\equiv 0\pmod{100}$

$\begin{align}&\color{#c00}{{\rm mod}\ \ 25}\!:\ \ \ 14\equiv 8^{\large 2}\Rightarrow\, 14^{\large 10}\equiv \overbrace{8^{\large 20}\equiv 1}^{\rm\large Euler\ \phi}\,\Rightarrow\, \color{#0a0}{14^{\large 10N}}\equiv\color{#c00}{\bf 1}\\[1em]

&{\rm mod}\ 100\!:\,\ 14^{\large 2+10N}\equiv 14^{\large 2}\, \color{#0a0}{14^{\large 10N}}\! \equiv 14^{\large 2}\!\! \underbrace{(\color{#c00}{{\bf 1} + 25k})}_{\large\color{#0a0}{14^{\Large 10N}}\!\bmod{\color{#c00}{25}}}\!\!\! \equiv 14^{\large 2} \equiv\, 96\end{align}$

First, note that $10^{7}\equiv10^{1}\pmod{35}$.

Therefore $n>6\implies10^{n}\equiv10^{n-6}\pmod{35}$.

Let’s calculate $5^{102}\bmod6$ using Euler’s theorem:

- $\gcd(5,6)=1$
- Therefore $5^{\phi(6)}\equiv1\pmod{6}$
- $\phi(6)=\phi(2\cdot3)=(2-1)\cdot(3-1)=2$
- Therefore $\color\red{5^{2}}\equiv\color\red{1}\pmod{6}$
- Therefore $5^{102}\equiv5^{2\cdot51}\equiv(\color\red{5^{2}})^{51}\equiv\color\red{1}^{51}\equiv1\pmod{6}$

Therefore $10^{5^{102}}\equiv10^{5^{102}-6}\equiv10^{5^{102}-12}\equiv10^{5^{102}-18}\equiv\ldots\equiv10^{1}\equiv10\pmod{35}$.

Carrying on from your calculation:

$$\begin{align}

10^3&\equiv 6 \bmod 7 \\

&\equiv -1 \bmod 7 \\

\implies 10^6 = (10^3)^2&\equiv 1 \bmod 7

\end{align}$$

We could reach the same conclusion more quickly by observing that $7$ is prime so by Fermat’s Little Theorem, $10^{(7-1)}\equiv 1 \bmod 7$.

So we need to know the value of $5^{102}\bmod 6$, and here again $5\equiv -1 \bmod 6 $ so $5^{\text{even}}\equiv 1 \bmod 6$. (Again there are other ways to the same conclusion, but spotting $-1$ is often useful).

Thus $10^{\large 5^{102}}\equiv 10^{6k+1}\equiv 10^1\equiv 3 \bmod 7$.

Now the final step uses the Chinese remainder theorem for uniqueness of the solution (to congruence):

$$\left .\begin{align}

x&\equiv 0 \bmod 5 \\

x&\equiv 3 \bmod 7 \\

\end{align}

\right\}\implies x\equiv 10 \bmod 35 $$

- Limit of $\sqrt{4x^2 + 3x} – 2x$ as $x \to \infty$
- Question about homomorphism of cyclic group
- Levi civita and kronecker delta properties?
- Is this determinant identity true?
- Is there an intuitive way to see this property of random walks?
- A constrained extremum problem
- How many ways to divide group of 12 people into 2 groups of 3 people and 3 groups of 2 people?
- Simplify $\int_{0}^{1}\ln(x-a)\ln x\,\mathrm{d}x$, for $a<0$
- Gardner riddle on mathemagicians
- How many ways to do n chose k such that the picks are non-decreasing?
- Prove that $\exists \{c_n\}$ monotonically increasing to $\infty$ such that $\sum_{i=1}^\infty a_nc_n$ coverges.
- Closed form for $\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{(k+1)^2}$
- Why is the 2 norm “special”?
- How to explain that division by $0$ yields infinity to a 2nd grader
- Intuition for the Cauchy-Schwarz inequality