ABSTRACT
Fermat’s Theorem tells us then that in any congruence with a prime modulus p and a base a which is relatively prime to p, we can reduce any exponent modulo p - 1 (and of course, we know we can reduce the base a modulo p). In trying to do computations with relatively small numbers and in as few steps as possible, this theorem is a great help, but it may not be enough help if the modulus is not small. Fermat’s theorem only allows us to reduce the exponent 99 by 100, so we gain nothing in this example. Whatever multiplications we do need to do, we should always remember to immediately reduce the answer modulo p, which will guarantee that all intermediate numbers we arrive at will be smaller than p.
