Let's get some more conjectures about values of $\phi(n)$. One of the neatest things about $\phi(n)$ is that it is quite useful for things we are familiar with (congruences) but is also a prototype for the many functions there are in number theory. (Indeed, much of the text is dedicated to it.) So we will look at it in a bit more depth today. Finding patterns is fun!
Click to the left again to hide and once more to show the dynamic interactive window 
We already know the first things below.
But there are some other patterns one might ask for, now that one has done some number theory.
Let's verify the latter patterns by hand for $n=15$ and $n=16$.
Quite surprisingly, there is an additive result as well  try $$\sum_{d\mid n} \phi(d)$$ for a pattern!
There are a lot of other interesting questions one can ask about this function. For instance, one can ask:
Click to the left again to hide and once more to show the dynamic interactive window 
The most interesting proof will be the proof that $\phi$ is multiplicative, a term I will not explain today but which is the third relationship/pattern.
I hope that by now we saw the pattern that $$\phi(p^e)=p^ep^{e1}=\left[1\frac{1}{p}\right]p^e\; .$$
Proof: Basically, we know from last time that any number which is not coprime to $p^e$ must share a prime factor, which must be $p$. And certainly any number divisible by $p$ is not coprime to $p^e$, so this is a necessary and sufficient condition. But all the numbers less than or equal to $p^e$ which have a factor of $p$ are just the multiples of $p$, and since they occur every $p$ and since $p^e$ itself is the $p^{e1}$th such multiple, there are exactly $p^{e1}$ such integers not coprime to $p^e$, which gives us our formula.
Proof of third property: We are trying to prove $$\phi(mn)=\phi(m)\phi(n)$$ if $m$ and $n$ are coprime. Take the integers from 1 to $mn$ and arrange them in an array like so  $n$ rows, $m$ columns: $$\begin{matrix}1 & 2 & 3 & \dots & m \\m+1 & m+2 & m+3 & \dots & 2m\\\vdots & \vdots & \vdots & \ddots & \vdots\\(n1)m+1 & (n1)m+2 & (n1)m+3 & \dots & nm\end{matrix}$$ Now notice that only some of the columns correspond to elements of $U_m$; namely, the columns with $km+\ell$ where $gcd(\ell,m)=1$. Thus there are $\phi(m)$ columns like this; focus on these, as all elements of these columns are coprime to $m$. Within each such column, there are all possible classes in $\mathbb{Z}_n$; this is because if $km+\ell\equiv k'm+\ell$ mod ($n$), then $km\equiv km'$ and we can cancel $m$, since we already know it is coprime to $n$. That means that each column has exactly $\phi(n)$ elements in it which are coprime to $n$!
It can be easier to see with an example, say $n=15$.
Click to the left again to hide and once more to show the dynamic interactive window 
The actual units modulo $mn$ are marked with exclamation points.
Since there are $\phi(m)$ columns with $\phi(n)$ elements in them, all coprime to both $m$ and $n$, that means there are $\phi(m)\phi(n)$ elements coprime to $mn$, which proves what we wanted.
Somewhat surprisingly, perhaps, this can lead us finally to a nice proof of the conductor results  one we can actually understand!
Click to the left again to hide and once more to show the dynamic interactive window 
Once again, the elements which DO have representations are marked with an exclamation point.
First, we find the largest number which does not work. Notice that in each column  that is to say, in each residue class modulo $m$  the lowest number that can be represented is a multiple of $n$. That is because if $mx+ny$ works, then since $x,y>0$ we can just subtract off $m$s until it's just a multiple of $n$, and it's still representable; these will all be in the same residue class modulo $m$. Further, all those multiples of $n$, regarded modulo $m$ are in different residue classes: $$[0],[n],[2n],[3n],\ldots,[(m2)n],[(m1)n]$$ We proved something very similar before for $m$ prime earlier, and also above; basically, if $$kn\equiv k'n\text{ mod }(m)$$ then we can just cancel $n$ since $gcd(m,n)=1$, and so $$k\equiv k'\text{ mod }(m)\; .$$ That means the very biggest number that cannot be represented must be in the residue class with the biggest of these numbers; if $m(0)+ny$ works, then $m(1)+ny$ won't. That would be $(m1)n$, so $$(m1)nm$$ is the biggest number that can't be represented, so that $$(m1)nm+1=mnnm+1=(m1)(n1)$$ is the smallest number above which all are represented, the conductor.
Next, we want to show that there are exactly half of the numbers below the conductor, including the (obviously) representable 0, which are in fact representable. We will do this by pairing up the numbers from $0$ to $(m1)nm$ that add up to $(m1)nm$. One of each pair will be representable, yielding the conclusion.
Suppose that $0\leq z\leq (m1)nm$ is representable  so that $$z=mx+ny\; , m,n>0\; .$$ Then look at $$z'=(m1)nmz=m(1x)+n(m1y)\; .$$ We know that $$m1\geq m1y\geq 0\; ,$$ because if $m1\leq y$, then $z\geq n(m1)$, but we are assuming it's less than the conductor. Certainly $(1x)<0$, so it sure looks like $z'$ is not representable.
Of course, it's possible that $z'$ could be written in a representable way by adding $m$s and subtracting $n$s. However, because $m$ and $n$ are coprime, the minimum possible to do this with would be $n$ $m$s and $m$ $n$s. That would give $$z'=m(n1x)+n(1y)\; ,$$ which of course has the same problem.
And this argument works backwards. Any positive number $z'$ which is not representable must still have a representation as $mx+ny$, just with either $x$ or $y$ (but not both) positive. Pick the representation $z'=mx+ny$ with the smallest positive $x$. Then we know that it can also be written as $m(xn)+n(y+m)$ must have $y+m>0$, and $xn<0$, so that $0<y<m$ and $0<x<n$. Then $$z = (m1)nmz' = (m1)nm[mx+ny]=m(1x)+n(m1y)$$ can be represented this way, namely by adding $mn$ to the first term and subtracting it from the second term: $$z = m(n1x)+n(1y)$$ where $n>x$ so $nx1\geq 0$, and where $y>0$ so $1y\geq 0$ as well.
Proof of summation property: We wish to prove $$n=\sum_{d\mid n} \phi(d)\; .$$ Take $\{1,2,3,\ldots,n\}$ and divide it up into subsets with different $gcd$ with $n$. The only possibilities for greatest common divisor with $n$ are the various divisors $d$ of $n$, which we will call $\{d\mid n\}$. So we get sets like $$\{a\mid gcd(a,n)=1\},\;\{a\mid gcd(a,n)=d_1\},\;\{a\mid gcd(a,n)=d_2\},\ldots,\{a\mid gcd(a,n)=n\}\, .$$ We can now look at these sets; each one consists of number sharing divisor $d_i$ with $n$, so we can divide all the numbers in the $i$th set by $d_i$, which will give the set of numbers $1\leq b\leq \frac{n}{d_i}$ coprime to $\frac{n}{d_i}$, e.g. $$\{b\mid gcd(b,n)=1\},\;\{b\mid gcd(b,n/d_1)=1\},\;\{b\mid gcd(b,n/d_2)=1\},\ldots,\{b\mid gcd(b,1)=1\}\, .$$ These sets were all disjoint, so they still are disjoint; even though the sets themselves are different, their sizes/cardinalities are the same. So $$n=\phi(n)+\phi(n/d_1)+\phi(n/d_2)+\cdots+\phi(1)\, .$$ But the numbers $\frac{n}{d_i}$ for all divisors $d_i$ of $n$ is also the set of all divisors of $n$! So what we have is really $n=\sum_{d\mid n} \phi(d)$, as desired.
To really understand this, it is best to do this with $n=15$.
Just before we go, a last teaser for the next couple of class sessions. Remember our search for patterns in the powers of $a$ mod ($n$)? That is, we looked for patterns in $a^b$ mod($n$).
One of the things we discovered was Femat's Little Theorem. There is lots left to discover, though. Can you find more?
Click to the left again to hide and once more to show the dynamic interactive window 
Remember, to get a grayscale plot, just remove the part with cmap='jet' etc.
The reason I bring this back is because of your observation that sometimes we get all colors in a single row. That is, at least sometimes $a^b$ mod ($n$) goes through every single number when we do enough powers $a^b$. It turns out that this concept has a name, and is the last of the big concepts of basic congruence number theory.
So next time we will talk about these primitive roots!
For composite $n$, this won't mean all colors per se, just all colors that represent units  so we shrink the number of rows down for this final interact. This has rows that are the elements of $U_n$, but certainly not labeled correctly.
Click to the left again to hide and once more to show the dynamic interactive window 
Homework for Wednesday, to be handed in:
