Thread: Help Understanding Modular Exponentiation

I've come across an example that I can't understand. Can somebody explain what is happening here?



So, I get that if I can get the base to be something that is equal to 1 (mod 3), then I know that the overall answer is also 1 mod 3. What I don't understand is the simplification that is used.

The example just shows one more step before jumping to the final answer. Here is what it shows:



I can see that they got the base to be 4, which is 1 (mod 3), but I just can't follow the math for how they were able to make this leap. Can anybody tell me the exponentiation rule used?

Thank you!

Hey joatmon.

I'm not sure given only this amount of information, but one thing that may help is to note that if a is congruent 1 MOD 3 then a^2 is also congruent to 1 MOD 3.

So a = 3b + 1 for some b. This means

a^2 = (3b+1)^2 = (3b)^2 + 6b + 1 = 3*(3b^2 + 2b) + 1 = 3c + 1 so a^2 is congruent to 1 MOD 3.

Thanks for the reply, Chiro. That might be part of it. The usual procedure is that we try to get the base down to something that is 1 mod N, because we know that repeated multiplication of anything that is 1 mod N will always remain congruent to 1 since 1 x 1 x 1 x ... is still 1. I'm pretty sure that they somehow extracted a from the exponent, but I don't see how they can bring this into the base.

My guess is that they did something like this for the next two steps (which weren't shown):



And then somehow brought down 4 into the base, but I don't see how this can be legally done. I'm sure that there is some exponential rule being applied that I am just not seeing, but this is as far as I can get.

The simplest way to do this is to note that "1234" is larger than 3 so start by reducing that "modulo 3".
1234= what (mod 3)?

Hello, joatmon!

You're on the right track . . . keep going!

My guess is that they did something like this for the next two steps (which weren't shown):

. Good!

You have: .