# MAT 338 Day 14 2011

## 2821 days ago by kcrisman

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!

@interact def _(n=range_slider(2,150,1,(2,20))): top = n[1] bottom = n[0] cols = ((top-bottom)//10)+1 T = [cols*['$n$','$\phi(n)$']] list = [[i,euler_phi(i)] for i in range(n[0],n[1])] list.extend((10-(len(list)%10))*['','']) for k in range(10): t = [item for j in range(cols) for item in list[k+10*j] ] T.append(t) html.table(T,header=True)

## Click to the left again to hide and once more to show the dynamic interactive window

We already know the first things below.

• If $gcd(a,n)=1$, then $a^{\phi(n)}\equiv 1$ mod ($n$).

But there are some other patterns one might ask for, now that one has done some number theory.

• Given a prime $p$, is there a formula for $\phi(p^e)$?
• If $m$ and $n$ are coprime, is there a relation between $\phi(mn)$ and $\phi(m)$ and $\phi(n)$?

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!

• When does $\phi(n)\mid n$?
• Given $m$, for how many integers $n$ it is true that $\phi(n)=m$?
• Are there infinitely many $n$ for which $\phi(n)$ ends in zero?
@interact def _(n=range_slider(2,150,1,(2,20))): top = n[1] bottom = n[0] cols = ((top-bottom)//10)+1 T = [cols*['$n$','$\phi(n)$']] list = [[i,euler_phi(i)] for i in range(n[0],n[1])] list.extend((10-(len(list)%10))*['','']) for k in range(10): t = [item for j in range(cols) for item in list[k+10*j] ] T.append(t) html.table(T,header=True)

## 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^e-p^{e-1}=\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^{e-1}$th such multiple, there are exactly $p^{e-1}$ 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\\(n-1)m+1 & (n-1)m+2 & (n-1)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$.

@interact def _(m=(5,[2..10]),n=(3,[2..10])): T = [['$[%s]$'%i for i in [1..m]]] for k in range(n): t = [] for i in [1+k*m..m+k*m]: if gcd(i,m*n)==1: t.append('$%s$ !'%i) else: t.append('$%s$'%i) T.append(t) html.table(T,header=True)

## 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!

@interact def _(m=(3,[2..10]),n=(4,[2..10])): them = set([m*x+n*y for x in srange(n) for y in srange(m)]) T = [['$[%s]$'%i for i in [0..m-1]]] for k in range(n): t = [] for i in [0+k*m..m-1+k*m]: if i in them: t.append('%s !'%i) else: t.append('$%s$'%i) T.append(t) html.table(T,header=True)

## 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,[(m-2)n],[(m-1)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 $(m-1)n$, so $$(m-1)n-m$$ is the biggest number that can't be represented, so that $$(m-1)n-m+1=mn-n-m+1=(m-1)(n-1)$$ 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 $(m-1)n-m$ that add up to $(m-1)n-m$.  One of each pair will be representable, yielding the conclusion.

Suppose that $0\leq z\leq (m-1)n-m$ is representable - so that $$z=mx+ny\; , m,n>0\; .$$  Then look at $$z'=(m-1)n-m-z=m(-1-x)+n(m-1-y)\; .$$  We know that $$m-1\geq m-1-y\geq 0\; ,$$ because if $m-1\leq y$, then $z\geq n(m-1)$, but we are assuming it's less than the conductor.  Certainly $(-1-x)<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(n-1-x)+n(-1-y)\; ,$$ 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(x-n)+n(y+m)$ must have $y+m>0$, and $x-n<0$, so that $0<-y<m$ and $0<x<n$.  Then $$z = (m-1)n-m-z' = (m-1)n-m-[mx+ny]=m(-1-x)+n(m-1-y)$$ can be represented this way, namely by adding $mn$ to the first term and subtracting it from the second term: $$z = m(n-1-x)+n(-1-y)$$ where $n>x$ so $n-x-1\geq 0$, and where $-y>0$ so $-1-y\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?

@interact def power_table_plot(p=(7,range(2,50))): P=matrix_plot(matrix(p-1,[mod(a,p)^b for a in range(1,p) for b in srange(euler_phi(p)+1)]),cmap='jet') show(P)

## Click to the left again to hide and once more to show the dynamic interactive window

Remember, to get a gray-scale 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.

• We say that $a\in U_n$ is a primitive root of $n$ when $a^b$ runs through all elements of $U_n$ for $1\leq b\leq \phi(n)$.  Or, you can say it hits all the possible colors in the interact!

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.

@interact def _(modulus=(7,range(2,50))): show(matrix_plot(matrix(euler_phi(modulus),[mod(a,modulus)^b for a in range(1,modulus) for b in srange(euler_phi(modulus)+1) if gcd(a,modulus)==1]),cmap='jet'))

## Click to the left again to hide and once more to show the dynamic interactive window

Homework for Wednesday, to be handed in:

1. Prove Fermat's Little Theorem as a corollary of Euler's Theorem.
2. Get the inverse of 29 modulo 31, 33, and 34 using Euler's Theorem.
3. Solve the system $4x\equiv 2\text{ mod }(6)$, $3x\equiv 5\text{ mod }(7)$, $2x\equiv 4\text{ mod }(11)$ using Euler's Theorem to implement the CRT, as much as you can.
4. Create a general formula for $\phi(N)$ where $N=\prod_{i=1}^k p_i^{e_i}$ and prove it by induction, using the things we learned today.
5. Compute the $\phi$ function evaluated at 1492, 1776, and 2001.
6. Solve the congruence $33x\equiv 29$ mod (127) and mod (128).
7. Evaluate without a calculator $12^{49}$ mod (15) and $139^{112}$ mod (27).
8. Let $f(n)=\phi(n)/n$.
• Show that $f(p^k)=f(p)$ if $p$ is prime.
• Find the smallest $n$ such that $f(n)<1/5$.
• Find all $n$ such that $f(n)=1/2$.