I am having trouble, I tried using the fact that the gcd(30,22)=2 but I have been stuck here for a bit now.
22^{201} \equiv x \mod (30)
22^{201} \equiv 22*22^{200} mod (30)
How can I proceed?
Answer
We have 22^2=484\equiv 4\pmod{30}
Then 4^3\equiv 4\pmod{30} and this means 22^6\equiv 4\pmod{30} and 201=33\times 6+3 so 22^{201}=(22^6)^{33}+22^3. This gives 22^{201}\equiv 4^{33}\times 22^3\pmod{30} Using the above 4^{33}\equiv 4^{11}\equiv (4^3)^{3}\times 4^2\equiv 4 and 22^3\equiv4\times22\equiv 28\pmod{30} and we can conclude that 22^{201}\equiv 4\times 28\equiv -8\equiv 22 \pmod{30}
No comments:
Post a Comment