ive identity 0. Then = 0=0 for all r E R. Property R2. Let r1 and r2 be elements of a ring R. Then ).12= = -(r1 r2) = =(-1).(r1.r2) for all r1,N2ER. Henceforth, the following notational simplifications will be observed: (5A.8) (5A.9) Lack of multiplicative inverses precludes use of the cancellation law. That is, if r1 is a rang element which does not have a multiplicative inverse, then r1r2 = r1r3 does not imply r2 = r3. Example 5A.4. The ring of integers 0, 1, ,7 under addition and multi- plication mod 8 exhibits the following relation: 4.1 = 4.3 = 4.5 = 4.7, Yet 1, 3, 5, and 7 are distinct elements of the ring. In the ring of integers it is possible to define a process called division, which is akin to multiplication by a multiplicative inverse. The result of the Euclidean division algorithm is: If n1 and N2 are any two real integers, N2 # 0, then n1 can be represented by (5A.10) where q and r integers and 0 < ,,N2. If r = 0, we say that N2 divides N1, and denote this by n2n2 The remainder r is often called (the value of) n1 modulo N2, or in abbreviated fashion n1 mod N2. The greatest common divisor gcd(m,n) of two integers m and n, defined as the largest integer dividing both m and n, can be determined by repeated application of the Euclidean division algorithm. Furthermore, it can be shown that gcd(m,n) = am + bn = (5A.11) where a and b are also elements of the ring of integers. If gcd(m,n) = 1, then m and n are said to be relatively prime. The relation (5A.11) is extremely important in the sections to follow SO we will review it here and indicate an algorithm for determining it. Reviewing briefly, Euclid's division algorithm states that (5A.12) Pseudonoise Generators From this relation, it follows that if g divides any two of the three quanti- ties, Mi, aini, and ri, then it divides the third also. Hence, gcd(mi,Ni)gcd(ni,ri). (5A.13) Let's suppose we wish to compute gcd(m, n), m > N. Then the algorithm's structure is as follows. Euclid's Greatest Common Divisor Algorithm (a) Let m1 = m, n1 =n,i=1. (b) Compu