# MAT 338 Day 16 2011

## 2647 days ago by kcrisman

Our first item for today is just the coolest result.  I hope you conjectured it, but it could be quite challenging to do so.  Yet once you see it, it seems obvious to at least try it!

Proposition: If $m\mid n$, then $\phi(m)\mid \phi(n)$.

@interact def _(n=(50,[2..100])): L=[(m,euler_phi(m),euler_phi(n)) for m in divisors(n)] for item in L: html("$%s|%s$ and $\phi(%s)=%s|%s=\phi(%s)$"%(item[0],n,item[0],item[1],item[2],n))

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

This quick and clever proof is in fact from the text.

Proof: Since $m\mid n$, we can write $n/m$ as as product of the prime factors of $n$ which are not in $m$.  Then since all prime divisors of $m$ are prime divisors of $n$ as well, $$\phi(n)/\phi(m)=(n/m)\left(\prod_{p\mid n} (1-1/p) / \prod_{p\mid m} (1-1/p) \right)=(n/m)\prod_{p\mid (n/m)}(1-1/p)=(n/m)\prod_{p\mid (n/m)}\frac{p-1}{p}\, .$$  This is not self-evidently an integer, of course!  But note that $n/m$ is an integer, and every $p$ in the denominator is a (different) factor of $n/m$, so in fact we can cancel all the denominators and this is an integer!  Thus $\phi(n)$ is an integer multiple of $\phi(m)$.

Two of the other homework problems are actually quite important lemmas for being able to do more work with primitive roots.  I want you to keep trying to prove these.  However, we will also use them today.

1. Lemma: 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.)
2. Lemma: 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).)

In the first one, if the order is $p-1$, then if $a$ is a primitive root modulo $p$, then so is $a^b$ for all $b$ coprime to $p-1$ - which implies that if there is a primitive root modulo $p$, then there are in fact $\phi(p-1)$ of them!  (This turns out to be true for general $n$, replacing $p-1$ by $\phi(n)$, in fact.)  It works; let's check this out.

@interact def _(p=(41,prime_range(100))): a=mod(primitive_root(p),p) html("$%s$ is a primitive root of $%s$, with order $%s$"%(a,p,p-1)) L=[(i,a^i,(a^i).multiplicative_order()) for i in range(2,p-1) if gcd(i,p-1)==1] for item in L: html("$%s^{%s}\equiv %s$ also has order $%s$ (and $gcd(%s,%s)=1$)"%(a,item[0],item[1],item[2],item[0],p-1))

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

Today's biggest proof is that every prime number $p$ has a primitive root, and it uses both of the above as lemmas.  In order to understand that proof, let's see in what sense these lemmas fail (or don't).

Let's pick a non-prime number we know something about.  Last time we saw that powers of 2 don't have cyclic groups of units, but they do have lots of elements with the next smallest possible order.  So for $n=32$, we can look at whether powers $b$ coprime to that order of such an element are in fact also elements with the same order.

n=32 a=mod(5,n) L=[(i,a^i,(a^i).multiplicative_order()) for i in range(1,a.multiplicative_order()) if gcd(i,a.multiplicative_order())==1] for item in L: html("$%s^{%s}\equiv %s$ has order $%s$ (and $gcd(%s,%s)=1$)"%(a,item[0],item[1],item[2],item[0],a.multiplicative_order()))
 5^{1}\equiv 5 has order 8 (and gcd(1,8)=1) 5^{3}\equiv 29 has order 8 (and gcd(3,8)=1) 5^{5}\equiv 21 has order 8 (and gcd(5,8)=1) 5^{7}\equiv 13 has order 8 (and gcd(7,8)=1) 5^{1}\equiv 5 has order 8 (and gcd(1,8)=1) 5^{3}\equiv 29 has order 8 (and gcd(3,8)=1) 5^{5}\equiv 21 has order 8 (and gcd(5,8)=1) 5^{7}\equiv 13 has order 8 (and gcd(7,8)=1)

So it works; indeed, the first lemma should be true whether $p$ is prime or not, though I won't ask you to prove it.  The second lemma also seems to be working; there are exactly $\phi(8)=4$ powers here, which have order eight.

The problem, though, is that there might be some element of the same order as the ones above which is not actually one of them!

a=mod(-5,n) L=[(i,a^i,(a^i).multiplicative_order()) for i in range(1,a.multiplicative_order()) if gcd(i,a.multiplicative_order())==1] for item in L: html("$%s^{%s}\equiv %s$ has order $%s$ (and $gcd(%s,%s)=1$)"%(a,item[0],item[1],item[2],item[0],a.multiplicative_order()))
 27^{1}\equiv 27 has order 8 (and gcd(1,8)=1) 27^{3}\equiv 3 has order 8 (and gcd(3,8)=1) 27^{5}\equiv 11 has order 8 (and gcd(5,8)=1) 27^{7}\equiv 19 has order 8 (and gcd(7,8)=1) 27^{1}\equiv 27 has order 8 (and gcd(1,8)=1) 27^{3}\equiv 3 has order 8 (and gcd(3,8)=1) 27^{5}\equiv 11 has order 8 (and gcd(5,8)=1) 27^{7}\equiv 19 has order 8 (and gcd(7,8)=1)

In some sense, then, there are "extra" elements with order $8$ in the above example.  If you have eight elements of order eight, and obviously at least one element of order 1, in $U_{32}$, then it is impossible to have the required eight elements of order sixteen one would need for there to be a primitive root modulo $32$ (because $8+1+8>16=|U_{32}|$).  In essence, the fact that this can't happen for a prime modulus is why primitive roots do exist in that case.

L=[(p,primitive_root(p)) for p in prime_range(100)] for item in L: html("A primitive root of $%s$ is $%s$"%(item[0],item[1]))
 A primitive root of 2 is 1 A primitive root of 3 is 2 A primitive root of 5 is 2 A primitive root of 7 is 3 A primitive root of 11 is 2 A primitive root of 13 is 2 A primitive root of 17 is 3 A primitive root of 19 is 2 A primitive root of 23 is 5 A primitive root of 29 is 2 A primitive root of 31 is 3 A primitive root of 37 is 2 A primitive root of 41 is 6 A primitive root of 43 is 3 A primitive root of 47 is 5 A primitive root of 53 is 2 A primitive root of 59 is 2 A primitive root of 61 is 2 A primitive root of 67 is 2 A primitive root of 71 is 7 A primitive root of 73 is 5 A primitive root of 79 is 3 A primitive root of 83 is 2 A primitive root of 89 is 3 A primitive root of 97 is 5 A primitive root of 2 is 1 A primitive root of 3 is 2 A primitive root of 5 is 2 A primitive root of 7 is 3 A primitive root of 11 is 2 A primitive root of 13 is 2 A primitive root of 17 is 3 A primitive root of 19 is 2 A primitive root of 23 is 5 A primitive root of 29 is 2 A primitive root of 31 is 3 A primitive root of 37 is 2 A primitive root of 41 is 6 A primitive root of 43 is 3 A primitive root of 47 is 5 A primitive root of 53 is 2 A primitive root of 59 is 2 A primitive root of 61 is 2 A primitive root of 67 is 2 A primitive root of 71 is 7 A primitive root of 73 is 5 A primitive root of 79 is 3 A primitive root of 83 is 2 A primitive root of 89 is 3 A primitive root of 97 is 5

The previous cell shows us that we get a primitive root for the first 25 primes.  Now let's use our lemmas to prove that every prime has a primitive root - or, in other words, that the order $p-1$ group $U_p$ is always cyclic.

The key is to try to write $\phi(p)=p-1$ in two different ways:

1. $p-1=\phi(p)=\sum_{d\mid p-1} \phi(d)$
2. $p-1=\sum_{d\mid p-1} \mid\{a\in U_p \mid a\text{ has order }d\}\mid$

The first one we have already proved, of course.  The second makes sense too, though; after all, we already proved (the other Lagrange's Theorem) that the order of any element of a group divides the order of the group, so the only possible orders of elements in $U_p$ are positive divisors of $p-1$.  We know that every element of $U_p$ has some order, so that $p-1$ is divided up into (disjoint) sets of different orders as above.

Let's see what that looks like for two examples - one where we know we have a primitive root, and one where we know we don't.

Here is the list of sets of different order elements for $n=41$:

for d in divisors(40): L=[] for a in range(1,41): if mod(a,41).multiplicative_order()==d: L.append(a) html("There are $%s=\phi(%s)$ elements of order $%s$ - "%(len(L),d,d)+str(L))
 There are 1=\phi(1) elements of order 1 - [1] There are 1=\phi(2) elements of order 2 - [40] There are 2=\phi(4) elements of order 4 - [9, 32] There are 4=\phi(5) elements of order 5 - [10, 16, 18, 37] There are 4=\phi(8) elements of order 8 - [3, 14, 27, 38] There are 4=\phi(10) elements of order 10 - [4, 23, 25, 31] There are 8=\phi(20) elements of order 20 - [2, 5, 8, 20, 21, 33, 36, 39] There are 16=\phi(40) elements of order 40 - [6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35] There are 1=\phi(1) elements of order 1 - [1] There are 1=\phi(2) elements of order 2 - [40] There are 2=\phi(4) elements of order 4 - [9, 32] There are 4=\phi(5) elements of order 5 - [10, 16, 18, 37] There are 4=\phi(8) elements of order 8 - [3, 14, 27, 38] There are 4=\phi(10) elements of order 10 - [4, 23, 25, 31] There are 8=\phi(20) elements of order 20 - [2, 5, 8, 20, 21, 33, 36, 39] There are 16=\phi(40) elements of order 40 - [6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35]

But here is the list of sets for $n=32$; there aren't any for the highest possible order, and all the other sets have orders exact multiples of $\phi(d)$.

for d in divisors(euler_phi(32)): L=[] for a in range(1,32): if mod(a,2)==1 and mod(a,32).multiplicative_order()==d: L.append(a) if len(L)==euler_phi(d): html("There are $%s=\phi(%s)$ elements of order $%s$ - "%(len(L),d,d)+str(L)) else: html("There are $%s\\neq\phi(%s)$ elements of order $%s$ - "%(len(L),d,d)+str(L))
 There are 1=\phi(1) elements of order 1 - [1] There are 3\neq\phi(2) elements of order 2 - [15, 17, 31] There are 4\neq\phi(4) elements of order 4 - [7, 9, 23, 25] There are 8\neq\phi(8) elements of order 8 - [3, 5, 11, 13, 19, 21, 27, 29] There are 0\neq\phi(16) elements of order 16 - [] There are 1=\phi(1) elements of order 1 - [1] There are 3\neq\phi(2) elements of order 2 - [15, 17, 31] There are 4\neq\phi(4) elements of order 4 - [7, 9, 23, 25] There are 8\neq\phi(8) elements of order 8 - [3, 5, 11, 13, 19, 21, 27, 29] There are 0\neq\phi(16) elements of order 16 - []

So what is going on here? Let's go back to our assumption that $p$ is prime.  Well, for any of the divisors $d$ of $p-1$ (not just $p-1$ itself), the size of the set $$|\{a\in U_p \mid a\text{ has order }d\}|$$ certainly can't be bigger than $\phi(d)$, by our second lemma.  That should be clear.  On the other hand, as we just pointed out, every element of $U_p$ has some order!  And once we find one $a$ with order $d$, then all the powers of $a$ coprime to $d$ also have that order, so there are $\phi(d)$ of them - and no more than $\phi(d)$ of them - once we find such an $a$.

This means that if any of the sets for $d$ (such as the set of primitive roots! for $d=p-1$) is empty, then the orders of $\phi(d)$ elements of our group of units have to be distributed among the other sets.  But we know that none of the sets is bigger than $\phi(d)$, and $$\sum_{d\mid p-1, d<p-1} \phi(d)<p-1\; ;$$ yet all $p-1$ elements must be in one of the sets.  This doesn't make sense unless there is at least one element in each of the sets of elements with order $d$, so in particular there is at least one (and in fact $\phi(p-1)$) with order $p-1$, as we suspected all along!

If you are curious, you can explore more below.

@interact def _(n=(25,[0..100])): for d in divisors(euler_phi(n)): L=[] for a in range(1,n): if gcd(a,n)==1 and mod(a,n).multiplicative_order()==d: L.append(a) if len(L)==euler_phi(d): html("There are $%s=\phi(%s)$ elements of order $%s$ - "%(len(L),d,d)+str(L)) else: html("There are $%s\\neq\phi(%s)$ elements of order $%s$ - "%(len(L),d,d)+str(L))

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

There is more to the story, but we won't cover the rest in detail.  The complete story of which $n$ have groups of units $U_n$ that are cyclic is given by Sage here:

a=pari(5) a.znprimroot?
 File: /Applications/MathApps/sage/devel/sage/sage/libs/pari/gen.pyx Type: Definition: a.znprimroot() Docstring: Return a primitive root modulo self, whenever it exists. This is a generator of the group (\ZZ/n\ZZ)^*, whenever this group is cyclic, i.e. if n=4 or n=p^k or n=2p^k, where p is an odd prime and k is a natural number. INPUT: self - positive integer equal to 4, or a power of an odd prime, or twice a power of an odd prime OUTPUT: gen EXAMPLES: sage: pari(4).znprimroot() Mod(3, 4) sage: pari(10007^3).znprimroot() Mod(5, 1002101470343) sage: pari(2*109^10).znprimroot() Mod(236736367459211723407, 473472734918423446802)  File: /Applications/MathApps/sage/devel/sage/sage/libs/pari/gen.pyx Type: Definition: a.znprimroot() Docstring: Return a primitive root modulo self, whenever it exists. This is a generator of the group (\ZZ/n\ZZ)^*, whenever this group is cyclic, i.e. if n=4 or n=p^k or n=2p^k, where p is an odd prime and k is a natural number. INPUT: self - positive integer equal to 4, or a power of an odd prime, or twice a power of an odd prime OUTPUT: gen EXAMPLES: sage: pari(4).znprimroot() Mod(3, 4) sage: pari(10007^3).znprimroot() Mod(5, 1002101470343) sage: pari(2*109^10).znprimroot() Mod(236736367459211723407, 473472734918423446802) 

(Chapter 6.7 tells the complete algebraic story of how to interpret this, culminating in Corollary 6.14, which is way more algebra than we will do in this course but which is satisfyingly complete.)

To make this result plausible, the following cell demonstrates yet another of the exercises from last time - that an odd primitive root for a prime power is also a primitive root for twice that modulus.

@interact def _(n=(7^2,prime_range(100)+[i^2 for i in prime_range(3,25)]+[i^3 for i in prime_range(3,12)])): a=mod(primitive_root(n),n) if mod(a,2)==0: for i in range(1,euler_phi(n)): if gcd(i,euler_phi(n))==1: a=a^i if mod(a,2)==1: break html("$%s$ is a primitive root of $%s$, hence has order $%s$"%(a,n,euler_phi(n))) html("The order of $%s$ in $\mathbb{Z}_{%s}$ is also $%s$"%(a,2*n,mod(a,2*n).multiplicative_order())) html("Compare the powers:") print [a^i for i in range(1,euler_phi(n)+1)] a = mod(a,2*n) print [a^i for i in range(1,euler_phi(2*n)+1)]

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

Obviously this is consistent, since $\phi(2p^e)=\phi(p^e)$.   Does this pattern help you think how you might prove it?

We will soon begin talking about cryptography and related matters.  Before we do so, we will preview our computational needs by using primitive roots to solve some congruences in a cool way.

Suppose you want to solve a more mysterious congruence than the basic ones we have tackled thus far.  Here are two examples:

• $x^4 \equiv 13$ mod (19)
• $7^x \equiv 6$ mod (17)

You can think of the first one as finding a higher root modulo $n$, and the second one as finding a logarithm modulo $n$.  Indeed, solving the second problem is an example of what is called a discrete log problem.  Such problems are apparently very, very hard to solve quickly, but (!) no one has every actually proved this.

Here's one way to solve the first one.  First we find a primitive root modulo $19$.  Obviously we could just ask Sage, or use the criterion from last time with trial and error; in the not too distant past (such as my own undergraduate days), the back of every number theory text had a table of primitive roots!

primitive_root(19)
 2 2

Now what we will do is try to represent both sides of $$x^4\equiv 13\text{ mod }(19)$$ as powers of that primitive root!

The easy part is representing $x^4$; we just say that $x\equiv 2^i$ for some (as yet unknown) $i$, so $$x^4\equiv \left(2^i\right)^4\equiv 2^{4i}\; .$$  The harder part is figuring out what power of $2$ gives $13$.  Again, there is no shortcut, though books in the past would have huge tables of these things.

a=mod(2,19) L=[(i,a^i) for i in range(2,19)] for item in L: if item[1]!=13: html("$%s^{%s}\equiv %s\\not\equiv 13$"%(a,item[0],item[1])) else: html("$%s^{%s}\equiv %s$ - hooray!"%(a,item[0],item[1])) break
 2^{2}\equiv 4\not\equiv 13 2^{3}\equiv 8\not\equiv 13 2^{4}\equiv 16\not\equiv 13 2^{5}\equiv 13 - hooray! 2^{2}\equiv 4\not\equiv 13 2^{3}\equiv 8\not\equiv 13 2^{4}\equiv 16\not\equiv 13 2^{5}\equiv 13 - hooray!

So we can say that $$x^4\equiv 13\text{ mod }(19)$$ becomes $$2^{4i}\equiv 2^{5}\text{ mod }(19)\; .$$  Now we can use some insight from precalculus.  You would solve it this way, with equations (not congruences): $$2^{4i}=2^{5}\Rightarrow 4i=5 \Rightarrow i=5/4\; .$$  We will try to do the same thing here.

What is very important is that this is really no longer a congruence in $\mathbb{Z}_{19}$; after all, everything in sight is really in $U_{19}$, a cyclic group of order $\phi(19)=18$.   But a cyclic group of order $18$ would just be modulo 18!  So we take the exponents, but mod (18):  $$4i\equiv 5\text{ mod }(18)\; .$$

Sadly, this does not have a solution.  But we figured it out without taking every fourth power out there!  Indeed, doing that confirms our result:

[mod(i,19)^4 for i in range(2,19)]
 [16, 5, 9, 17, 4, 7, 11, 6, 6, 11, 7, 4, 17, 9, 5, 16, 1] [16, 5, 9, 17, 4, 7, 11, 6, 6, 11, 7, 4, 17, 9, 5, 16, 1]

Let's try the same thing modulo $17$ instead - that is, can we solve $$x^4\equiv 13\text{ mod }(17)\; ?$$  Here, a primitive root is $3$, and it turns out that $3^4\equiv 13$, so we can try.  This gives $$3^{4i}\equiv 3^4\text{ mod }(17)\Rightarrow 4i\equiv 4\text{ mod }(16)\, ,$$ which definitely does have solutions - in fact, four solutions ($1,5,9,13$) to the reduced congruence $$i\equiv 1\text{ mod }(4)$$ so there are four solutions ($3^1,3^5,3^9,3^{13}$) to the original congruence.  Let's check this:

a = mod(3,17) [(a^b)^4 for b in [1,5,9,13]]
 [13, 13, 13, 13] [13, 13, 13, 13]

You can even see it at work for more complicated things.  If we try solving $x^6\equiv 8$ mod (49), we'll need a primitive root of 49; 3 works.  I can find out what power of 3 is 8:

x=mod(primitive_root(49),49) L=[(i,x^i) for i in range(2,euler_phi(49))] for item in L: if item[1]!=8: html("$%s^{%s}\equiv %s\\not\equiv 8$"%(a,item[0],item[1])) else: html("$%s^{%s}\equiv %s$ - hooray!"%(a,item[0],item[1])) break
 3^{2}\equiv 9\not\equiv 8 3^{3}\equiv 27\not\equiv 8 3^{4}\equiv 32\not\equiv 8 3^{5}\equiv 47\not\equiv 8 3^{6}\equiv 43\not\equiv 8 3^{7}\equiv 31\not\equiv 8 3^{8}\equiv 44\not\equiv 8 3^{9}\equiv 34\not\equiv 8 3^{10}\equiv 4\not\equiv 8 3^{11}\equiv 12\not\equiv 8 3^{12}\equiv 36\not\equiv 8 3^{13}\equiv 10\not\equiv 8 3^{14}\equiv 30\not\equiv 8 3^{15}\equiv 41\not\equiv 8 3^{16}\equiv 25\not\equiv 8 3^{17}\equiv 26\not\equiv 8 3^{18}\equiv 29\not\equiv 8 3^{19}\equiv 38\not\equiv 8 3^{20}\equiv 16\not\equiv 8 3^{21}\equiv 48\not\equiv 8 3^{22}\equiv 46\not\equiv 8 3^{23}\equiv 40\not\equiv 8 3^{24}\equiv 22\not\equiv 8 3^{25}\equiv 17\not\equiv 8 3^{26}\equiv 2\not\equiv 8 3^{27}\equiv 6\not\equiv 8 3^{28}\equiv 18\not\equiv 8 3^{29}\equiv 5\not\equiv 8 3^{30}\equiv 15\not\equiv 8 3^{31}\equiv 45\not\equiv 8 3^{32}\equiv 37\not\equiv 8 3^{33}\equiv 13\not\equiv 8 3^{34}\equiv 39\not\equiv 8 3^{35}\equiv 19\not\equiv 8 3^{36}\equiv 8 - hooray! 3^{2}\equiv 9\not\equiv 8 3^{3}\equiv 27\not\equiv 8 3^{4}\equiv 32\not\equiv 8 3^{5}\equiv 47\not\equiv 8 3^{6}\equiv 43\not\equiv 8 3^{7}\equiv 31\not\equiv 8 3^{8}\equiv 44\not\equiv 8 3^{9}\equiv 34\not\equiv 8 3^{10}\equiv 4\not\equiv 8 3^{11}\equiv 12\not\equiv 8 3^{12}\equiv 36\not\equiv 8 3^{13}\equiv 10\not\equiv 8 3^{14}\equiv 30\not\equiv 8 3^{15}\equiv 41\not\equiv 8 3^{16}\equiv 25\not\equiv 8 3^{17}\equiv 26\not\equiv 8 3^{18}\equiv 29\not\equiv 8 3^{19}\equiv 38\not\equiv 8 3^{20}\equiv 16\not\equiv 8 3^{21}\equiv 48\not\equiv 8 3^{22}\equiv 46\not\equiv 8 3^{23}\equiv 40\not\equiv 8 3^{24}\equiv 22\not\equiv 8 3^{25}\equiv 17\not\equiv 8 3^{26}\equiv 2\not\equiv 8 3^{27}\equiv 6\not\equiv 8 3^{28}\equiv 18\not\equiv 8 3^{29}\equiv 5\not\equiv 8 3^{30}\equiv 15\not\equiv 8 3^{31}\equiv 45\not\equiv 8 3^{32}\equiv 37\not\equiv 8 3^{33}\equiv 13\not\equiv 8 3^{34}\equiv 39\not\equiv 8 3^{35}\equiv 19\not\equiv 8 3^{36}\equiv 8 - hooray!

So we write $x=3^i$ for some as yet unknown $i$, and get $$3^{6i}\equiv 3^{36}\text{ mod }(49)\; ,$$ which gives us $$6i\equiv 36\text{ mod }(\phi(49)=42)$$ and this reduces to $$i\equiv 6\text{ mod }(7)\; .$$  So $i=6,13,20,27,34,41$ all work, which means (from our little info above) that $x=3^{i}\equiv 43,10,16,6,39,33$ all should work.

[mod(d,49)^6 for d in [43,10,16,6,39,33]]
 [8, 8, 8, 8, 8, 8] [8, 8, 8, 8, 8, 8]

Similarly, we can try to solve logarithmic guys like $$7^x\equiv 6\text{ mod }(17)\; .$$  A primitive root modulo 17 is 3, and we can check that $7\equiv 3^{11}\text{ mod }(17)$ and $5\equiv 3^{15}\text{ mod }(17)$.  Then, replacing these, we see that $$3^{11x}\equiv 3^{15}\text{ mod }(17)\text{ yields }11x\equiv 15\text{ mod }(16)\, ;$$ since $3\cdot 11=33=32+1$, we see that 3 and 11 are inverses modulo 16, so $x\equiv 3\cdot 15\equiv 45\equiv 13$ mod (16).  And indeed:

mod(7,17)^13==6
 True True

Homework:

1. 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.)
2. 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).)
3. Prove that an odd primitive root modulo an odd prime power is still a primitive root for twice that modulus.
4. Solve $x^6\equiv 4$ mod ($23$).
5. Solve $x^4\equiv 4$ mod ($99$) by using the backwards CRT to write this as the product of two congruences which CAN be solved with primitive roots, and then putting them back together.
6. Find all primitive roots of 18, 23, and 27 (last time you just found one each).
7. Find all solutions to the following.  Making a little table of powers of a primitive root modulo 23 first would be a good idea.
• $3x^5\equiv 1$ mod (23)
• $3x^{14}\equiv 2$ mod (23)
• $3^x\equiv 2$ mod (23)
• $13^x\equiv 5$ mod (23)
8. For which positive integers $a$ is the congruence $ax^4\equiv 2$ mod (13) solvable?
9. Conjecture what the product of all primitive roots modulo $p$ (for an odd prime $p$) is, modulo $p$.  Prove it!  (Hint: one of the lemmas and thinking in terms of the computational homeworks might help.)