Relatively prime numbers

As an example, suppose the modulus is m=12. The numbers which are not relatively prime to 12 are those that are divisible by 2 or 3, since they make up the factors of 12. If we just consider the numbers from 0 to 11 (since these represent all numbers modulo 12), the ones which avoid 2's and 3's are

1,5,7,11

There are only four such numbers. Those are the only numbers a for which we have to consider $a^k \equiv 1 \pmod {12}$. Moreover, those are the only numbers that can occur in the cycle of powers of any one of these a's. That alone tells us that the cycle has at most four terms. It's actually less than that: each a has square congruent to 1 modulo 12:

$$1^2\equiv 5^2 \equiv 7^2 \equiv 11^2 \equiv 1 \pmod{12}$$

Each modulus m has only so many congruence classes of numbers; they correspond to the numbers from 0 to m-1. There is therefore a definite number of these which are relatively prime to m. That number is usually written as $\phi(m)$ and is called Euler's totient function or phi function. (The word totient has something vaguely to do with counting, which is how it came up, but let's face it: it's just another one of those weird math terms.) We have just seen that $\phi(12)=4$.

Computing the Euler function for a prime modulus p is especially simple. Every number from 1 to p-1 is relatively prime to p; that's what being a prime means. So we conclude $\phi(p)=p-1$.

A prime power m=pⁿ is just a little more complicated. A number ais relatively prime to pⁿ provide p is not a divisor of a, because p is the only prime divisor of pⁿ. So the numbers that have to be ruled out are 0, p, 2p, 3p, ... , (p^n-1 -1)p. There are exactly p^n-1 of those. That means the number of relatively prime classes is $\phi(p^n) = p^n - p^{n-1}$.

That leads to a general modulus m. In that case, what we do is first factor m into prime powers, and amazingly $\phi(m)$ is the product of the $\phi$ function for each one of those prime powers. For example, 12 = $2^2\cdot 3^1$. Then $\phi(12) = (2^2-2^1)(3^1-3^0) = (4-2)(3-1) =4$. This makes it quite easy to compute $\phi(m)$ for larger numbers, provided we know the factorization of m. For example, for $m=120 = 2^3 \cdot 3\cdot 5$, we have $\phi(120) = (2^3-2^2)(3-1)(5-1) = 32$.