Which property of modular arithmetic is being used here?

Question

I came across this example in a video lecture on modular arithmetic. I need to calculate (99^99) modulo 100. It says that since modulo is preserved under multiplication we can just replace 99 in the base by a congruent number that is -1. AFAIK, this is neither modular multiplication or exponentiation.

Answer 1

You can not replace both $99$'s with $-1$, this is only possible for the base. This is simply provable using the fact that

modulo is preserved under multiplication

Let $a \equiv b$ (mod $m$), and we need to prove $a^k \equiv b^k$ (mod $m$). Perform an induction on $k$.

• for $k=1$ this is trivial.
• for $k>1$ we know $a^{k-1} \equiv b^{k-1}$ (mod $m$) by the induction hypothesis, and since modulo is preserved under multiplication, we have $a \cdot a^{k-1} \equiv b \cdot b^{k-1}$, therefore $a^k \equiv b^k$.

For instance $99 \equiv -1$ (mod $100$) implies $99^{99} \equiv -1^{99}$ (mod $100$). which is easy to calculate $-1^{99} = -1$.

Answer 2

Instead of doing $99^{99}$, try this:

$(100-1)^{99}$

Expanding that would bring $100$ terms with a power of $100$ and the last term would be $(-1)^{99}$

That's the real magic of modular arithmetic.