| | |
$\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:
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 Theorem Let 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$. |