mod Distributive Law, factoring $\!\!\bmod\!\!:$ $\ ab\bmod ac = a(b\bmod c)$

Question

I stumbled across this problem

Find $\,10^{\large 5^{102}}$ modulo $35$, i.e. the remainder left after it is divided by $35$

Beginning, we try to find a simplification for $10$ to get: $$10 \equiv 3 \text{ mod } 7\\ 10^2 \equiv 2 \text{ mod } 7 \\ 10^3 \equiv 6 \text{ mod } 7$$

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?

Answer 1

The "logic" is that we can use a mod distributive law to pull out a common factor $\,\color{#c00}{c=5},\,$ i.e.

$$ \bbox[1px,border:3px solid #c60]{\bbox[8px,border:1px solid #c00]{\color{#c00}ca\bmod \color{#c00}cn\:\! =\, \color{#c00}c(a\bmod n)}} $$

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

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

$$ \ \ \bbox[1px,border:3px solid #c60]{\bbox[8px,border:1px solid #c00] {ca\equiv c(a\bmod n)\ \ \ {\rm if}\ \ \ \color{#0a0}{cn\equiv 0}\ \pmod{\! m}}}$$

since we have: $\,\ c(a\bmod n) \equiv c(a\! +\! kn)\equiv ca+k(\color{#0a0}{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. Recall 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}.\, $ So if $\ I \ge 1\ $ then as above

$\ \phantom{{\rm mod}\,\ 35\!:\,\ }\color{#90f}{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} $

but $\ 5^{\large 102} = \color{#90f}{1\!+\!6J}\ $ by $\ {\rm mod}\,\ 6\!:\,\ 5^{\large 102}\!\equiv (-1)^{\large 102}\!\equiv 1$

So $\ 10^{\large 5^{\large 102}}\!\! = \color{#90f}{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}$

This distributive law is actually equivalent to CRT as we sketch below, with $\,m,n\,$ coprime

$\begin{align} x&\equiv a\!\!\!\pmod{\! m}\\ \color{#c00}x&\equiv\color{#c00} b\!\!\!\pmod{\! n}\end{align}$ $\,\Rightarrow\, x\!-\!a\bmod mn\, =\, m\left[\dfrac{\color{#c00}x-a}m\bmod n\right] = m\left[\dfrac{\color{#c00}b-a}m\bmod n\right]$

which is exactly the same form solution given by Easy CRT. But the operational form of this law often makes it much more convenient to apply in computations versus the classical CRT formula.

---

Fractional extension of the mod distributive law: e.g. from here

notice: $\,\ \ \dfrac{\color{#c00}{11}}{35}\bmod \color{#c00}{11}(9)\,=\, \color{#c00}{11}(\color{#0a0}8)\,$ by $\color{#0a0}{\bmod 9\!:\ \dfrac{1}{35}\equiv \dfrac{1}{-1}\equiv 8},\ $ by

Theorem $\ \ \dfrac{\color{#c00}ab}d\bmod \color{#c00}ac\, =\, \color{#c00}a\left(\color{#0a0}{\dfrac{b}d\bmod c}\right)\ \ $ if $\ \ (d,ac) = 1$

${\bf Proof}{\bf \:\!_1}\ $ Bezout & $(d,ac)\!=\!1 \Rightarrow$ exists $\, d' \equiv d^{-1}\!\pmod{\!ac}.\,$ Factoring out $\,\color{#c00}a\,$ by mDL

$\qquad\qquad\ \ \ \ \dfrac{\color{#c00}ab}d\bmod \color{#c00}ac \,=\,\color{#c00}abd'\bmod \color{#c00}ac\, =\ \color{#c00}a(bd'\bmod c) = \color{#c00}{a}\left( \dfrac{b}d\bmod c\right)$

by inverses persist at modulus factors: $\ dd' \equiv 1\pmod{\!ac}\,\Rightarrow\, dd' \equiv 1\pmod{\!c}$

$\begin{align}{\bf Proof\:\!_2}\qquad\qquad \color{#0a0}x \,&\:\color{#0a0}{\equiv b/d \pmod c}\\[.2em] \iff\ \ \ dx&\equiv b\ \ \ \ \pmod{c},\ \ \ \ {\rm by}\ \ (d,c)=1\\[.2em] \smash[t]{\overset{\times\ a}\iff}\ \ dax&\equiv ab\ \ \pmod{ac}\\[.2em] \iff\ \ \ \color{#c00}a\color{#0a0}x &\equiv \color{#c00}ab/d\!\!\!\pmod{\color{#c00}ac},\ \ {\rm by}\ \ (d,ac)=1 \end{align}$

Answer 2

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

Answer 3

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