
Congruence
Hi, Masters!
Can I have some questions?
1) Why is it that (the inverse of 3)^3 will be 33 * 3 * 11^2 * 3 = 121 * 3 = 21 * 3 = 63 mod 100?
I assume 3*33 = 99 so it is 1 mod 100. So 33 came from here. But I don't know where 3* 11^2 * 3 come from..
2) y^31 = 3 mod 100.
I just memorised it should be y = 3^31^1 mod 100. And 31^1 is 9, so the equation should be 3^9 mod 100.
How can I calculate 3^9 mod 100...?
I guess I am poor at calculating the inverse.
Please help me out masters.
It is really difficult to get any information about higher congruence like y^32...

Re: Congruence
Well if 3*33 = 1 (mod 100), then it stands to reason that:
3*(33) = 1 (mod 100), that is, the inverse of 3 (mod 100) is 33 = 67.
If we cube this, we get:
(67)^{3} = (33)^{3} = (33)(33)^{2} = (33)(3^{2})(11^{2}) = (33)(9)(121) = (33)(3)(3)(121) = (3)(121) = (3)(21) = 63 (mod 100).
Your second question is harder to answer.
Assuming the answer IS 3^{9} mod 100, we calculate:
3^{9} = (3^{1})^{9} = 67^{9} = [(67)^{2}]^{4}(67) = (89)^{4}(67) = (11)^{4}(67) = (11)^{4}(67) = (21)^{2}(67) = (41)(67) = 47.