Jan 122016
 

It is no big secret that exponentiation is just multiplication in disguise. It is a short hand way to write an integer times itself multiple times and is especially space saving the larger the exponent becomes. In the same vein, a serious problem with calculating numbers raised to exponents is that they very quickly become extremely large as the exponent increases in value. The following rule provides a great computational advantage when doing modular exponentiation.

The rule for doing exponentiation in modular arithmetic is:

a^b \bmod{c} = ((a \bmod{c})^b) \bmod{c}

This states that if we take an integer a, raise it to an integer power b and calculate the result modulo c we will get the same result as if we had taken a modulo c first, raise it to b, and calculate that product modulo c.

Continue reading »

Jan 022016
 

I must stay focused. I must stay focused. I must stay … I wonder what’s new on Facebook.

I don’t really feel like writing this post mostly because I know that it will be very similar to the other two I have already done: modular addition rule proof and modular subtraction rule proof, but my New Year’s Resolution is to follow things through to completion. Well, that would’ve been my News Years resolution if I had made one. Either way, it’s back to modular arithmetic.

The rule for doing multiplication in modular arithmetic is:

(a * b) \bmod{c} = (a \bmod{c} * b \bmod{c}) \bmod{c}

This says that if we multiply integer a times integer b and take the product modulo c, we get the same answer as if we had first taken a modulo c and multiplied by b modulo c and taken that product modulo c.

Continue reading »