Modular congruence, splitting a modulo
I can't find out, how to solve this. Will you give me some advice what to do in 4th step? Lot of thanks.
This is my example: $7^{30}\equiv x\pmod{ 100}$ I want to compute it this way.
These are my steps:
- Split $100=4\times25$ (I can do that because the greatest common divisor is 1)
- $7^{30}\equiv -1\equiv 24 \pmod {25}$
- $7^{30} \equiv 1 \pmod4$
- Don't know what to do now. The result is $49$. How to get $49$ from this two results?
Solution 1:
$$7^2=49=50-1\implies7^4=(50-1)^2=50^2-2\cdot50+1^2\equiv1\pmod{100}$$
As $\displaystyle30\equiv2\pmod4,7^{30}\equiv7^2\pmod{100}$
$\displaystyle7\equiv-1\pmod4\implies7^{30}\equiv(-1)^{30}\implies7^{30}\equiv1\pmod4\ \ \ \ (1)$
$\displaystyle7^2=49\equiv-1\pmod{25}\implies7^{30}=(-1)^{15}\implies7^{30}\equiv-1\pmod{25}\ \ \ \ (2)$
Apply Chinese Remainder Theorem on $(1),(2)$
Solution 2:
For small CRT problems there are usually many optimizations of CRT that one can use to simplify computation. Here, since one modulus $= 4$ is very small, we can reduce to checking $4$ candidate solutions, viz. $\,x\equiv 24\pmod{25}\iff x = 24+25k\iff x\equiv 24,49,74,99\pmod{100},\,$ so we reduce to checking which of these candidates $\,x\,$ also satisfies $\,x\equiv 1\pmod 4,\,$ which is easy.
The above method will generally be the quickest when one of the moduli $\,m\,$ is very small, since it involves checking only $\,m\,$ candidate solutions. Another optimization also applies to this system: the Bezout identity for the moduli $\,m,n = 25,4\,$ is obvious since $\,25\ {\rm mod}\ 4\, =\, 25-6(4) = 1,\, $ so $\ \ \color{#c00}{25}+\color{#0a0}{(-6)4} = 1,\,$ and we can easily "read off" the solution from a Bezout identity as follows:
$ \!\!\qquad\color{#c00}{j m} + \color{#0a0}{k n} = 1\ \ \ \Rightarrow\ \ \begin{eqnarray}&&x\equiv a\!\!\!\pmod m\\ &&x\equiv b\!\!\!\pmod n\end{eqnarray}$ $\!\iff\!$ $\begin{eqnarray} x&\equiv&\ a\,\color{#0a0}{kn}\, +\, b\,\color{#c00}{jm}&&({\rm mod}\ {mn})\\ &\equiv& a+(b\!-\!a)\color{#c00}{jm}&&({\rm mod}\ mn)\end{eqnarray}$
$\ \ \color{#c00}{25} + \color{#0a0}{(-6)4} = 1\ \ \ \Rightarrow\ \ \begin{eqnarray}&&x\equiv a\!\!\!\pmod{25}\\ &&x\equiv b\!\!\!\pmod 4\end{eqnarray}$ $\!\iff\!$ $\begin{eqnarray} x&\equiv&\ a\,\color{#0a0}{(-24)} + b\,\color{#c00}{(25)}&&({\rm mod}\ {mn})\\ &\equiv&\ a\ +\ (b\!-\!a)\,\color{#c00}{(25)}&&({\rm mod}\ mn)\end{eqnarray}$
For the special case $\ a,b\, =\,-1,1\ $ we obtain $\ x\equiv (-1)\color{#0a0}{(-24)}+(1)\color{#c00}{(25)} \equiv 49\pmod{100}.\,$ With a little practice, one can do the above in under a minute of mental arithmetic in most small cases.
The same optimization works generally when one of the moduli is $\pm1$ modulo the other, since that immediately yields the Bezout identity for their gcd $= 1.\,$ This essentially optimizes the extended Euclidean algorithm when it terminates in a single step. Compare the second form of the solutions above to Easy CRT.