Some notation: the integers, as a set, are frequently given the name Z (for Zahlen, German for "numbers"). The integers mod n are called Zn. The 'n' reminds you that it is 'mod n'. The multiplicative group of invertible elements in Zn is called Zn*. The '*' is supposed to remind you of multiplication.
Here is a connection between "invertible elements" and the Euclidean algorithm. When you use the Euclidean algorithm to determine whether a and n are relatively prime, the algorithm is actually computing the inverse of a in Zn*, if it exists. If it doesn't exist, the algorithm tells you this! How does it do all this??? Here is an example. If we compute gcd(17,8), we find ourselves doing the following:
17 = 2*8 + 1
Since the remainder was 1, gcd(17,8)=1. But rearranging this we find
1=17-2*8
This is obviously true. But reducing it mod 17 we find
1=(-2)*8 (mod 17)
This is because 17=0 mod 17. The Euclidean algorithm has computed the inverse of 8 mod 17. It is -2. Since this is mod 17, a more usual name for -2 is 15 (I added 17). Thus we find the inverse of 8 is 15 (mod 17). Check: 8*15=120=119+1=1 mod 17, since 119 is a multiple of 17.
This example does not show the most general thing that can happen. An example which is a little more complicated computationally is the inverse of 7 mod 11. We start out computing gcd(11,7):
11=1*7 + 4
7=1*4 + 3
4=1*3 + 1
Thus gcd(11,7)=1. Now we rearrange to express that final '1' in terms of the original '11' and '7'. The first and second lines tell us that 4=11-7 and 3=7-4=7-(11-7)=2*7-11, so the intermediate numbers 4 and 3 are expressed in terms of 11 and 7. Then, from the last line, 1=4-3=(11-7)-(2*7-11)=2*11-3*7. Reducing mod 11 this says 1=(-3)*7 mod 11. Thus the inverse of 7 is (-3), mod 11, or, as we would usually say , 8 (rather than -3). Check: 8*7=56=55+1=1 mod 11.
The Euclidean algorithm computes the inverse when it produces a '1' at the end, i.e., when the two numbers are relatively prime. Conversely, when a has an inverse mod n, then gcd(a,n)=1. Thus these two notions are identical: (1) a and n are relatively prime, (2) a is in Zn*. If you compute gcd(a,n) and it is not 1, then (1) a and n are NOT relatively prime, and (2) a is not invertible mod n, and hence is NOT in Zn*.
This connection between invertibility and relatively prime numbers makes it easy to figure out which elements are in Zn*. For example,
Z8*={1, 3, 5, 7}
Z9*={1, 2, 4, 5, 7, 8}
Z10*={1, 3, 7, 9}
Z11*={1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Z12*={1, 5, 7, 11}
Z13*={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12},
etc.
A number connected with each integer n is Euler's phi(n), which is just the number of elements in Zn*, or, equivalently, the number of positive integers less than n and relatively prime to n. Examples like Z11* and Z13* illustrate that phi(p)=p-1 for every prime integer p. For non-primes, though, there is no obvious formula for phi(n), short of actually counting up the relatively prime numbers. We note from the examples above, phi(8)=4, phi(9)=6, phi(10)=4, phi(11)=10, phi(12)=4, phi(13)=12. There are hints that phi has a curious multiplicative property. For example, phi(15)=phi(5)*phi(3), because phi(15)=8, and phi(5)=4, phi(3)=2 (CHECK THIS). This is suggestive: 15=5*3, and the "phi's" are 8=4*2. Your assignment is to check other examples like this.
Compute the relevant phi(n)'s to show
phi(35)=phi(7)*phi(5)
phi(36)=phi(9)*phi(4)
BUT: also show that phi(9) is not phi(3)*phi(3)!