The modulus of the product of  two numbers equals the modulus of the product of the same modulus of each of the two numbers. You can prove this for yourself by writing out this statement mathematically, plugging in (substituting) the definition of the remainder as a modulus and doing a little algebra. Similarly the modulus of the sum of  two numbers equals the modulus of the sum of the same modulus of each of the two numbers (with basically the same method useful as proof). Note that this means you can take the modulus of very large numbers quite easily by breaking them down into factors: eg, you can take the modulus of, say, (2^100) mod 13 by multiplying 2^5 mod 13 (=6) by itself 20 times mod 13, or by successive multiplication by 2, taking mod 13 every step, etc. Note that Fermat's theorem says that a^(n-1) mod n = 1 if* gcd(a,n) = 1. (* I don't think it's "iff"), so if you don't get 1 after n-1 multiplications, a and n are not relatively prime or you have made a mistake.

Defn: the identity element wrt an operator is that value that will give the original number when the number is operated on by the given operation with its identity element. Eg the identity element wrt addition is zero and wrt multiplication is 1.
Defn: the inverse of a number wrt an operation is the number that will give the identity element when it operates on, by the given operation, with the original number. Eg the additive inverse of a number is the negative of the number and the multiplicative inverse of a number is the reciprocal (one over) the number.
Therefore in modular mathematics the multiplicative inverse of a number is the number that when multiplied to the original number will give 1 when the modulus is taken. Eg the multiplicative inverse of 3 mod 5 is 2 because 3*2 = 6 = 1 mod 5 (remainder 1 when 5 is divided into 6).

Last updated May 23, 2005