Saturday, 20 August 2016

elementary number theory - Solve for huge linear congruence



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

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...