2
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – André Nicolas May 5 '14 at 15:40
1
$\begingroup$

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

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

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.