Solve for huge linear congruence

Question

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 1

We can do a series of reductions to simplify the problem. So, we have:

• $47^1 \pmod{55} = 47$
• $47^2 \pmod{55} = 9$
• $47^3 \pmod{55} = 9 \times 47 \pmod{55} = 38$
• $47^4 \pmod{55} = (47^2)^2 \pmod{55} = 9^2 \pmod{55} = 26$
• $47^5 \pmod{55} = 47^2 \times 47^3 \pmod{55} = 9 \times 38 \pmod{55} = 12$

Now, using this approach, how can we reduce the problem for $47^{27} \pmod{55}$?

You can see additional approaches, like the Modular Exponentiation and other approaches (Montgomery and many others).