since 10 divides 111 − 1 = 110. Some of the ten congruence classes with respect to this modulus are: and The linear congruence has no solutions since the integers that are congruent to 5 (i.e., those in ) are all odd while is always even. However, the linear congruence has two solutions, namely, and . The and 2 does not divide 5, but does divide 6. Since , the linear congruence will have solutions, that is, modular multiplicative inverses of 3 modulo 10 will exist. In fact, 7 satisfies this congruence (i.e., 21 − 1 = 20). However, other integers also satisfy the congruence, for instance 17 and −3 (i.e., 3(17) − 1 = 50 and 3(−3) − 1 = −10). In particular, every integer in will satisfy the congruence since these integers have the form for some integer and is divisible by 10. This congruence has only this one congruence class of solutions. The solution in this case could have been obtained by checking all possible cases, but systematic algorithms would be needed for larger moduli and these will be given in the next section. The product of congruence classes and can be obtained by selecting an element of , say 25, and an element of , say −2, and observing that their product (25)(−2) = −50 is in the congruence class . Thus, . Addition is defined in a similar way. The ten congruence classes together with these operations of addition and multiplication of congruence classes form the ring of integers modulo 10, i.e., . A complete residue system modulo 10 can be the set {10, −9, 2, 13, 24, −15, 26, 37, 8, 9} where each integer is in a different congruence class modulo 10. The unique least residue system modulo 10 is {0, 1, 2, ..., 9}. A reduced residue system modulo 10 could be {1, 3, 7, 9}. The product of any two congruence classes represented by these numbers is again one of these four congruence classes. This implies that these four congruence classes form a group, in this case the cyclic group of order four, having either 3 or 7 as a (multiplicative) generator. The represented congruence classes form the group of units of the ring . These congruence classes are precisely the ones which have modular multiplicative inverses. Computation Extended Euclidean algorithm A modular multiplicative inverse of modulo can be found by