hat if m is prime and (a, m) are co-prime, then am-1 mod m = = 1, (T13) which can be put into the equivalent form: am mod m = a. Thus, we have a mod 2 = 1 or a2 mod 3 = 1 for any a that is prime with number two or number three, and SO on with any prime modulus, for instance 1123-1 mod 23 = 1. We see that as a first benefit, Fermat's theorem makes it possible to considerably simplify calculations in modular arithmetic. Euler's theorem (named after the Swiss mathematician) states that if p and q are two primes and N = pq is their product, then we have for any integer a which is prime with n: a(p-1)(q-1) mod N 1. (T14) The factor (p - 1)(q - 1) with pq = N is also called (N). A consequence of Euler's theorem is that the inverse 1/a is readily defined as (T15) For instance, what is the inverse of 5 modulo 21? We have 21 = 3 X 7, SO (21) = (3 - 1) x (7 - 1) = 12 and 1/5 = 512-1 mod 21 = 48 828 125 mod = 17. Thus, |1/5/21 = 17, which is readily verified as (17 X 5) mod 21 = 85 mod 21 = 1. We see that the calculation of an inverse through Euler's theorem is quite straightforward, compared with the method previously described. But the requirement is that the modulus N is defined by the product of two primes, which represents a special or fortuitous case. It is important to note that if (a, N) are not co-prime to each other, the inverse a-1 does not exist. If the two are co-primes but Euler's theorem cannot apply, the inverse a-¹ can be found using the extended Euclidian algorithm. Here, I shall explain this algorithm through two representative examples: for instance, find the inverse of 7 in modulus 39, and the inverse of 5 in modulus 16 272, i.e., the values of 7-1 mod 39 and 5-1 mod 16 272. Taking the first example, the algorithm proceeds as shown in Table T1, with the steps as numbered in the first column. In steps 1 and 2, we fill out the table as shown. We first divide 39 by 7, to find that the integer part of the result is [39/7] = 5. In step 3, we multiply line 2 by 5, and in step 4 we subtract the result of line 