1. ## 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.

It is really difficult to get any information about higher congruence like y^32...

2. ## 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)(32)(112) = (-33)(9)(121) = (-33)(3)(3)(121) = (3)(121) = (3)(21) = 63 (mod 100).