# 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:

1. Split $100=4\times25$ (I can do that because the greatest common divisor is 1)
2. $7^{30}\equiv -1\equiv 24 \pmod {25}$
3. $7^{30} \equiv 1 \pmod4$
4. Don't know what to do now. The result is $49$. How to get $49$ from this two results?
• There is a general procedure (for details please google Chinese Remainder Theorem). But in our case we want $x\equiv -1\pmod{25}$. Try $24,49, 74, 99$ and see which one is congruent to $1$ modulo $4$. (The CRT guarantees exactly one of them will be.) – André Nicolas May 5 '14 at 15:40

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

• Thank you but I'm trying to compute it using results of 2nd a 3rd step. Is that possible? – Mill May 5 '14 at 15:37
• @Mill, Please find the edited version. Also by observation for $k=2,25k-1\equiv1\pmod4$ – lab bhattacharjee May 5 '14 at 15:40
• Wish I know the mistake here? – lab bhattacharjee May 6 '14 at 3:06

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.

The problem is to reduce 7^30 to a manageable form. Start by reducing powers of 7 to mod 100. It turns out that 7^10 = 49 mod 100.

Therefore (7^10)^3 = 49^3 mod 100. 49^3 mod 100 turns out to be 49 mod 100.

So 7^30 = 49 mod 100.