$\phi(n)$ is defined to be the number of positive integers less than or equal to $n$ that are relatively prime to $n$.

Proving that for prime $p$, $\phi(p)=p-1$ is trivial, as every positive integer less than a prime is relatively prime to that prime.

Further experimentation suggests that it is also true that $\phi(p^k)=p^k-p^{k-1}$.

This, too, is easily verified by noticing that of the $p^k$ positive integers less than or equal to $p^k$, only the multiples of $p$ are not relatively prime to $p^k$. As there are $p^k/p = p^{k-1}$ of these, $\phi(p^k)$ must be the difference $p^k-p^{k-1}$.

With a little more investigation, we stumble upon a key behavior of $\phi(n)$ -- it is *multiplicative* in the sense that

$$\phi(mn)=\phi(m)\phi(n) \quad \textrm{ if $m$ and $n$ are relatively prime}$$

We need to prove this, of course. To do so, we apply a counting argument. Basically, our intent is to construct two sets of integers, one with $\phi(mn)$ elements, and another with $\phi(m)\phi(n)$ elements. If we can establish a one to one correspondence between the elements of the two sets, then we will have shown that $\phi(mn)=\phi(m)\phi(n)$.

To this end, consider set $S_1$ defined as follows:

$$S_1 = \{a: 1 \le a \le mn \textrm{ and } \gcd(a,mn) = 1\}$$

So, $S_1$ consists of precisely those positive values less than or equal to $mn$ and relatively prime to $mn$. This, of course, by definition, must have $\phi(mn)$ elements.

Let us also define set $S_2$ as

$$\begin{array}{rlcrcl}

S_2 = \{(b,c): &1 \le b \le m &\textrm{ and }& \gcd(b,m) &=& 1\\

\textrm{and} &1 \le c \le n &\textrm{ and }& \gcd(c,n) &=& 1\}

\end{array}$$

We can count the elements of $S_2$ by considering how the ordered pairs are constructed. We must first choose the first coordinate of the ordered pair, which we can do in $\phi(m)$ ways.

Then, we must choose the second coordinate of the ordered pair, which we can do in $\phi(n)$ ways.

Thus, the total number of ways we could construct an ordered pair in $S_2$ is the product of these two values, $\phi(m)\phi(n)$ ways. It remains to show that there is a one-to-one correspondence between these two sets.

Consider associating any value $(a \mod mn)$ from $S_1$ with the ordered pair $(a \mod m, a\mod n)$ in $S_2$.

For example, if $m=4$ and $n=5$, we have:

$$S_1 = \{1, 3, 7, 9, 11, 13, 17, 19\}$$

$$S_2 = \{(1,1),(1,2),(1,3),(1,4),(3,1),(3,2),(3,3),(3,4)\}$$

and we have the following associations:

$$\begin{array}{ccc}

1 &\rightarrow& (1,1)\\

3 &\rightarrow& (3,3)\\

7 &\rightarrow& (3,2)\\

9 &\rightarrow& (1,4)\\

11 &\rightarrow& (3,1)\\

13 &\rightarrow& (1,3)\\

17 &\rightarrow& (1,2)\\

19 &\rightarrow& (3,4)\\

\end{array}$$

To show these associations are one-to-one, we need to show:

- Different numbers in $S_1$ get sent to different pairs in $S_2$
- Every pair in $S_2$ is associated with some element of $S_1$

To show the first claim holds, we argue indirectly. Suppose $a_1$ and $a_2$ are distinct elements of $S_1$ and are mapped to the same pair in $S_2$. If this is the case, then $a_1 \equiv a_2 \pmod{m}$ and $a_1 \equiv a_2 \pmod{n}$. But then $m \mid (a_1 - a_2)$ and $n \mid (a_1 - a_2)$. So, recalling that $m$ and $n$ are relatively prime, it must then be the case that $mn \mid (a_1 - a_2)$. Thus $a_1 \equiv a_2\pmod{mn}$, which contradicts the assumption that $a_1$ and $a_2$ were distinct.

To show the second claim holds, we need to show for any $(b,c)$ seen in $S_2$, we can find an $a$ in $S_1$ so that

$$a \equiv b\pmod{m} \quad \textrm{and} \quad a \equiv c\pmod{n}$$

This is best argued by example. Suppose we wish to solve

$$x \equiv 8 \pmod{11} \quad \textrm{and} \quad x \equiv 3\pmod{9}$$

We know from the first congruence that $x=11y+8$. Substituting this into the second gives us

$$11y+8 \equiv 3\pmod{9}$$

or equivalently,

$$11y \equiv -5\pmod{9}$$

We have, of course, solved such things before. If a simpler method does not present itself, we can always solve this via the multiplicative inverse of $11\pmod{9}$ given through the Euclidean Algorithm. For this to work, however, we must have 11 and 9 relatively prime to each other (which they are), as otherwise, no multiplicative inverse exists. In general, however, 11 and 9 are the values $m$ and $n$. Thus we can only be assured we can do this if $\gcd(m,n)=1$.

Proceeding with the example, we find $y \equiv 2\pmod{9}$, which in turn gives as its solution for $x$ the following:

$$x = 11y + 8 = 11(9k+2) + 8 = (11 \cdot 9)k + 30$$

Generalized, this technique results in a proof of the following very important result in number theory:

The Chinese Remainder TheoremLet m and n be integers where gcd(m,n)=1, and let b and c be any integers. Then the simultaneous congruences.
$$x \equiv b\pmod{m} \quad \textrm{and} \quad x \equiv c\pmod{n}$$ have exactly one solution with $0 \le x \lt mn$ |

Armed with this theorem, showing the existence of the $a \in S_1$ previously discussed becomes trivial -- and this, of course, finishes the proof of the multiplicative nature of $\phi$.