How to solve a linear congruence with a very huge number.
For example, 47^27 congruent to x (mod 55)
My idea is to first break this into
47^27 congruent to x (mod 5)
and 47^27 congruent to x (mod 11)
then, by FlT, I can reduce this to:
47^3 congruent to x(mod 5)
and 47^5 congruent to x(mod 11)
However, I don't know how to continue.
Answer
We can do a series of reductions to simplify the problem. So, we have:
- 471(mod55)=47
- 472(mod55)=9
- 473(mod55)=9×47(mod55)=38
- 474(mod55)=(472)2(mod55)=92(mod55)=26
- 475(mod55)=472×473(mod55)=9×38(mod55)=12
Now, using this approach, how can we reduce the problem for 4727(mod55)?
You can see additional approaches, like the Modular Exponentiation and other approaches (Montgomery and many others).
No comments:
Post a Comment