# MAT 338 Day 15 2011

## 2981 days ago by kcrisman

There were two somewhat theoretical things on the homework for today.  They are worth talking about briefly.

First, a formula for $$\phi(N)=\phi\left( \prod_{k=1}^n p_i^{e_i}\right)$$  Did you get one?  Here it is! $$\phi\left( \prod_{k=1}^n p_i^{e_i}\right)=\prod_{k=1}^n \phi\left(p_i^{e_i}\right)=\prod_{k=1}^n \left[1-\frac{1}{p_i}\right]p_i^{e_i}=N\cdot \prod_{k=1}^n \left[1-\frac{1}{p_i}\right]$$  The moral of the story is that being relatively prime makes up for many omissions.

@interact def _(n=24): list = prime_divisors(n) html("We compare this formula and Sage's implementation.") html("Sage says: $\phi(%s)=%s$"%(n,euler_phi(n))) html("The prime factors of $%s$ are %s"%(n,list)) ns = n*prod([1-1/p for p in list]) nums = ["%s"%n]+["(1-1/%s)"%p for p in list] html("Formula says: $"+"\cdot".join(nums)+"=%s$"%ns)

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

The other main component was related to a new function.  (Much later in the semester we will see lots of new and interesting functions!)  This function was $$f(n)=\frac{\phi(n)}{n}\; .$$  Some thing are very easy to prove about this if you have the formula for $\phi(n)$.  For instance, $$f\left(p^k\right)=\frac{p^k\left(1-1/p\right)}{p^k}=\left(1-1/p\right)$$ which does not depend on $k$.  So in particular it's true for $k=1$, which is $f(p)$.

On the other hand, some things are a little harder to spy.  Such as when $f(n)=1/2$.

def f(n): return euler_phi(n)/n # this is how we define functions in Python @interact def _(n=range_slider(1,1025,1,(1,20))): for i in [n[0]..n[1]]: if f(i)==1/2: html("$\phi(%s)=1/2$ - yes!"%i)

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

But hopefully easy to prove!

Another example of this we didn't put on the homework, but which was mentioned last time, is when $\phi(n)\mid n$.  (Notice that if $\phi(n) \mid n$, then $f(n)=\frac{1}{k}$ for some integer $k$.)  First, some exploration:

@interact def _(n=range_slider(1,200,1,(1,20))): for i in [n[0]..n[1]]: if mod(i,euler_phi(i))==0: html("$\phi(%s)=%s$ divides $%s$"%(i,euler_phi(i),i))

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

As you noted last time, it seemed like all the numbers involved were multiples of six.  Well, also the powers of two!  But not every multiple of six worked (30 and 42 didn't), and not even every even multiple of six worked (for instance, 60).

So in this case, we again make the point that the FTA is useful for many things - maybe I should factor some of the $n$ that do work!  Let's do this BY HAND right now.

Okay, now we can check it with Sage.

@interact def _(n=range_slider(1,200,1,(1,20))): for i in [n[0]..n[1]]: if mod(i,euler_phi(i))==0: html("$\phi(%s)=%s$ divides $%s$"%(i,euler_phi(i),i)) html("And $%s$ factors as $%s$<hr>"%(i,factor(i)))

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

Aha!  It looks like anything with only powers of two works, as well as anything with a power of three as long as it also has a power of two!  Nothing else seems to.

Now let's try to prove it.  I will do it with a sort of cases approach.  You may wish to notice how the fact that $p-1=2$ precisely for $p=3$ works into this.

1. If $n>2$ and $n$ is odd, then this is impossible because $\phi(n)$ is even.  (Proof left to the reader!  Think about the formula for $\phi\left(p^e\right)$ and what it implies for them.)
2. If $n=2^k 3^{\ell}$, with $k\geq 1$, then $$\phi(n)=2^{k-1}(3^{\ell}-3^{\ell-1})=2^{k-1}(3-1)3^{\ell-1}=2^k 3^{\ell-1}\, .$$  This certainly divides $n$.
3. If $n$ is even but not of the form above, then there is at least one prime factor $p\neq 2,3$.  Let $$n=2^k p^{\ell} \bar{n}\; ,$$ where $\bar{n}\neq 1$ is coprime to $2$ and $p$.  Then $$\phi(n)=2^{k-1}(p-1)p^{\ell-1}\phi(\bar{n})\; .$$  But $p$ is odd, so $p-1=2m$ for some $m$, and $\phi(\bar{n})$ is also even, so $\phi(\bar{n})=2m'$.  That means $$\phi(n)=2^{k-1}(p-1)p^{\ell-1}\phi(\bar{n})=2^{k+1}(p-1)p^{\ell-1}mm'$$ which is definitely not a factor of $n$.
4. Okay, it is possible that $\bar{n}=1$ above!  In that case $n=2^k p^{\ell}$, where $p\neq 3$.  This doesn't work either, because then $$\phi(n)=2^{k-1}(p-1)p^{\ell-1}=2^k \left(\frac{p-1}{2}\right)p^{\ell-1}\; ,$$ but there is no way that $\left(\frac{p-1}{2}\right)$ divides $p$, since $p$ is prime and greater than 3.  Case closed.

Remember, there are still other interesting questions to tackle.  The first two I mentioned last time.

• Given $m$, for how many integers $n$ is it true that $\phi(n)=m$?  Are there infinitely many, for instance?
• Are there infinitely many $n$ for which $\phi(n)$ ends in zero?
• When does $\phi(m)$ divide $\phi(n)$?
@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

You now have the tools you need to tackle such questions.  The structure of $\phi$ is very regular!

Now, let's get back to primitive roots.   Remember, there are two equivalent ways to characterize/define a primitive root of $n$ among numbers such that $gcd(a,n)=1$:

1. We say that $a$ is a primitive root of $n$ if $a^b$ yields every element of $U_n$.  Recalling the terminology from our introductory groups handout, this means that $U_n$ is a cyclic group (one all of whose elements are powers of a specific element), and that $a$ is a generator of that group. This is the more advanced point of view.
2. We say that $a$ is a primitive root of $n$ if the order of $a$ is $\phi(n)$.  This also uses the group idea of the order of an element - the smallest number of times you can multiply something by itself and get 1 as a result.  But this idea doesn't have to be understood in terms of groups; $k$ is the order of $a$ if $a^k\equiv 1$ mod ($n$) and $a^b\not \equiv 1$ for $1\leq b<k$.

Take a second and figure out the orders of some elements of some small groups of units.  One person each do $U_n$ for $n\in \{5,7,8,9,10,12,14,15\}$; I'll take $n=5$ and $n=15$, if you don't mind.  Did we find any primitive roots?

It's useful to try looking for primitive roots by hand, and you'll do some of that in the homework over the weekend.  It is also useful to try to prove things about orders in general, and you'll do some of that and we'll do some in class.

One approach for this is to try to find a better way of testing for primitiveness than trying all powers of $a$.  As it turns out, there is a very useful lemma for doing this.  First, an example to think about it by hand.

Take some number $n$ with a $\phi(n)$ with a few factors - say, $n=11$ and $\phi(11)=10$.  Okay, we know that every element $a\in U_{11}$ will have $a^{10}\equiv 1\text{ mod }(11)\; ,$ but which ones don't have it before?

Well, we know that the order of an element has to divide $\phi(11)=10$, so we could try $a^{2}$ and $a^5$.  If those aren't $\equiv 1$, there aren't any other possible orders out there, so it would work as a primitive root.  You can try this out to discover that $$2^2\equiv 4\not\equiv 1\text{ mod }(11)\text{ and }2^5=32\equiv -1\not\equiv 1\text{ mod }(11)\;,$$ so $2$ must be a primitive root, while $$3^5=9\cdot 9\cdot 3\equiv (-2)^2\cdot 3\equiv 12\equiv 1\text{ mod }(11)$$ so $3$ is not a primitive root modulo eleven.

Now we formalize this, and in fact rephrase it in a slightly more efficient way.  As far as I understand the code this is how even Sage tests for finding primitive roots.

Lemma for testing primitive roots: An element $a\in U_n$ is a primitive root if and only if $a^{\phi(n)/q}\not\equiv 1$ in $U_n$ for each prime $q$ dividing $\phi(n)$.

Essentially, two things change from trying all divisors of $\phi(n)$.

• Instead of trying divisors of $\phi(n)$, we try $\phi(n)$ divided by divisors.  So $2^5$ becomes $2^{10/2}$ and $3^2$ becomes $3^{10/5}$.  Which seems like it's not doing anything other than rewriting...
• But now instead of having to try all $\phi(n)/d$, we will use a trick to just need prime $d$.  See the proof below.

This lemma is probably still a little hard to understand, but with some examples it will make sense.

@interact def _(n=(19,[2..100]),a=3): phi=euler_phi(n) pds=prime_divisors(phi) a = mod(a,n) if gcd(a,n)!=1: html("Make sure $a$ and $n$ are relatively prime!") else: html("Is $%s$ a primitive root of $%s$?"%(a,n)) html("The prime divisors of $\phi(%s)$ are $%s$"%(n,','.join([str(pd) for pd in pds]))) html("The powers are "+''.join(['$$%s^{%s/%s}\equiv %s$$'%(a,phi,pd,a^(phi/pd)) for pd in pds])) html("And the order of a=$%s$ is a.multiplicative_order()=$%s$"%(a,a.multiplicative_order()))

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

If you try various $n$ and various attempts at primitive roots $a$, you will see that this really works.  Make sure you are trying $a$ that are actually coprime to $n$, though!  As it turns out, there aren't very many things to try, since $\phi(n)$ in general doesn't have a lot of prime divisors, even if $n$ is a fairly large prime.

Proof:

• If $a$ is in fact a primitive root, then $\phi(n)$ is the smallest number $k$ such that $a^{k}\equiv 1$, so certainly for numbers smaller than $\phi(n)$, like $\phi(n)/q$, those powers shouldn't be $\equiv 1$.
• On the other hand, if $a$ isn't a primitive root, then its order $k$ must be a proper divisor of $\phi(n)$; now look at the prime divisors $q$ of $\phi(n)/k$.  For such a divisor, $$q\mid \phi(n)/k$$ so $$qk\ell=\phi(n)\text{ for some }\ell$$ which means $$k\ell=\phi(n)/q\; .$$  But then $\phi(n)/q$ is a multiple of $k$, and if $a^k\equiv 1$, then certainly $$a^{k\ell}=a^{\phi(n)/q}\equiv 1\text{ mod }(n)$$ as well.

Why not try it by hand for $n=17$?  There is only one prime divisor of $\phi(17)$, which makes things easier.

This lemma makes easy some statements that would otherwise be quite hard.  For instance, you should see how to prove that if $a$ is a primitive root of $n$, then so is $a^{-1}$ (modulo $n$).   Here's something harder:

• If $a$ is a primitive root of $n$, then so is $n-a$ if $4|\phi(n)$.  After all, if $$a^{\phi(n)/q}\not\equiv 1$$, then $$(n-a)^{\phi(n)/q}\equiv (-a)^{\phi(n)/q}\equiv (-1)^{\phi(n)/q}a^{\phi(n)/q}\; ,$$ so that as long as $\phi(n)/q$ is even for all prime divisors of $\phi(n)$, the two powers are the same.  Since $\phi(n)$ is already even, the only possible odd $\phi(n)/q$ comes from $q=2$.

(It turns out that nearly all numbers fit this criterion - the only exceptions are $2$, perfect powers $p^e$ of primes of the form $p=4n+3$, and products of those two things.  There would be a little more work needed to do the converse.)

For next time you should also try to explore what sort of numbers have primitive roots.  Look for all the colors!

@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

Today we'll start this investigation (and end class) by proving that most powers of 2 do not have primitive roots.

power=25 primitive_root(2^power)
 Traceback (click to the left of this block for traceback) ... ArithmeticError: There is no primitive root modulo n Traceback (most recent call last): File "", line 1, in File "_sage_input_76.py", line 10, in exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("cG93ZXI9MjUKcHJpbWl0aXZlX3Jvb3QoMl5wb3dlcik="),globals())+"\\n"); execfile(os.path.abspath("___code___.py")) File "", line 1, in File "/private/var/folders/Yy/YytEJm5VEB0+pBRD7JNLe++++TQ/-Tmp-/tmpMnjxTO/___code___.py", line 4, in exec compile(u'primitive_root(_sage_const_2 **power) File "", line 1, in File "/Users/karl-dietercrisman/Downloads/sage-4.6.2.rc0/local/lib/python2.6/site-packages/sage/rings/arith.py", line 3288, in primitive_root raise ArithmeticError, "There is no primitive root modulo n" ArithmeticError: There is no primitive root modulo n

By the way, there are elements of $U_{2^n}$ that have order $2^{n-2}$, just not primitive roots (which would have order $\phi(2^n)=2^{n-1}$).  In fact, it turns out that $\pm 5$ have this order.  (This is Theorem 6.10 in the book - we won't say more about it, but it definitely relates to group theory.)

@interact def _(power=5): a = mod(5,2^power) html("Powers of 5 modulo $2^{%s}$ are"%power) print [a^i for i in [1..2^(power-1)]]

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

Proof: For $n=2$ and $n=4$, there are primitive roots.  So assume $n=2^k$ for $k>2$.

• We already saw that $n=8$ does not have a primitive root. In particular, each element of $U_8$ has order 2, so that $a^2\equiv 1$ mod (8) for all $a\in U_8$.
• Rethink this as saying that the highest order for $n=2^3$ is $2^1=2^{3-2}$.  That would be equivalent to not having a primitive root.
• Now assume (i.e. via induction) that for $n=2^k$ it is true that no element has order higher than $2^{k-2}$, i.e. $a^{2^{k-2}}\equiv 1$ mod ($2^k$).  By definition of divisibility, that means for any odd number $a$, we have that $$a^{2^{k-2}}=1+2^k\cdot m$$ for some integer $m$.
• Then let's look at modulus $2^{k+1}$.  We want that $$a^{2^{(k+1)-2}}=a^{2^{k-1}}\equiv 1\text{ mod }(2^{k+1})\, .$$  While it's easy to get $2^{k+1}$ from $2^k$, the only way to easily get $a^{2^{k-1}}$ from $a^{2^{k-2}}$ is by squaring (remember our strategy for finding huge powers modulo $n$ quickly?  We saw that $(a^{2^e})^2=a^{2^{e+1}}$.).
• So we do that.  $$a^{2^{k-1}}=\left(a^{2^{k-2}}\right)^2=(1+2^k m)^2=1+2^{k+1}m+2^{2k}m^2=1+2^{k+1}(m+2^{k-1}m^2)\equiv 1\text{ mod }2^{k+1}$$
• So by induction we are done; there are no primitive roots modulo $2^k$ for $k>2$.

Homework for next time:

1. Prove whether there are infinitely many values of $\phi$ that end in zero.
2. Conjecture whether there are any relations between $m$ and $n$ that might lead $\phi(m)$ to divide $\phi(n)$.
3. Suppose $p$ is prime and the order of $a$ modulo $p$ is $d$.  Prove that if $b$ and $d$ are coprime, then $a^b$ also has order $d$ modulo $p$. (Hint: actually write down the powers of $a^b$, and figure out which ones could actually be 1.)
4. Suppose $p$ is prime and $d$ divides $p-1$ (and hence is a possible order of an element of $U_p$).  Prove that at most $\phi(d)$ incongruent integers modulo $p$ have order $d$ modulo $p$.  (Hint: Lagrange's theorem (the polynomial one).)
5. Find the orders of all elements of $U_{13}$, including of course the primitive roots, if they exist.  Then verify the above statement.
6. Challenge: prove that exactly $\phi(p-1)$ primitive roots of $p$ if there is at least one.
7. Find primitive roots of 18, 23, and 27 using the criterion above to test various numbers.
8. If $a$ is a primitive root of $n$, prove that $a^{-1}$ is also a primitive root of $n$.
9. Challenge: Assume that $a$ is an odd primitive root modulo $p^e$, where $p$ is an odd prime (that is, both $a$ and $p$ are odd).  Prove that $a$ is also a primitive root modulo $2p^e$.