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?
Answer
$$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)$
No comments:
Post a Comment