Here's one way to solve the first congruence. First, find a primitive root modulo \(19\). Obviously we could just ask Sage, or use Lemma 10.2.3 with trial and error. In the not too distant past, the back of every number theory text had a table of primitive roots!
Now what we will do is try to represent both sides of \begin{equation*}x^4\equiv 13\text{ (mod }19)\end{equation*} 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 \begin{equation*}x^4\equiv \left(2^i\right)^4\equiv 2^{4i}\; .\end{equation*} The harder part is figuring out what power of \(2\) gives \(13\). Again, there is no shortcut, though books in the past had huge tables of them and powers (for easy reference). In practice, one would have all powers of a given primitive root available for use ahead of time.
By substituting the primitive roots in for \(x^4\) and \(13\), we can say that \begin{equation*}x^4\equiv 13\text{ (mod }19)\end{equation*} becomes \begin{equation*}2^{4i}\equiv 2^{5}\text{ (mod }19)\; .\end{equation*}
This is a much more familiar type of problem. How would we have solved this in high school? You would solve it this way, with equations (not congruences): \begin{equation*}2^{4i}=2^{5}\Rightarrow 4i=5 \Rightarrow i=5/4\; .\end{equation*} We will try to do something very similar here.
What is very important is that this congruence is, in some sense, really no longer a congruence in \(\mathbb{Z}_{19}\). To be precise, 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 the same as thinking modulo eighteen! So we can take out the exponents, just like in precalculus, but do things (mod \(18\)): \begin{equation*}4i\equiv 5\text{ (mod }18)\; .\end{equation*} (See Exercise 10.6.12.)
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:
Example10.5.1
Let's try the same congruence modulo \(17\) instead – that is, can we solve \begin{equation*}x^4\equiv 13\text{ (mod }17)\; ?\end{equation*} Here, a primitive root is \(3\), and it turns out that \(3^4\equiv 13\), so we can try. This gives \begin{equation*}3^{4i}\equiv 3^4\text{ (mod }17)\Rightarrow 4i\equiv 4\text{ (mod }16)\, ,\end{equation*} which definitely does have solutions.
In fact, there are four solutions (\(1,5,9,13\)) to the reduced congruence \begin{equation*}i\equiv 1\text{ (mod }4)\end{equation*} so there are four solutions (\(3^1,3^5,3^9,3^{13}\)) to the original congruence. Let's check this:
You can even see it at work for more complicated things.
Example10.5.2
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 \(3^i\) of \(3\) yields \(8\):
So we write \(x=3^i\) for some as yet unknown \(i\), and get \begin{equation*}3^{6i}\equiv 3^{36}\text{ (mod }49)\; ,\end{equation*} which gives us \begin{equation*}6i\equiv 36\text{ (mod }\phi(49)=42)\end{equation*} and this reduces to \begin{equation*}i\equiv 6\text{ (mod }7)\; .\end{equation*} So \(i=6,13,20,27,34,41\) all work, which means that \(x=3^{i}\equiv 43,10,16,6,39,33\) all should work.
Subsection10.5.2Discrete logarithms
Similarly, we can try to solve logarithmic examples like \begin{equation*}7^x\equiv 6\text{ (mod }17)\; .\end{equation*} Indeed, solving this problem is an example of what is called a discrete logarithm problem. Such problems are apparently very, very hard to solve quickly, but (!) no one has every actually proved this.
Example10.5.3
A primitive root modulo 17 is 3, and we can check that \(7\equiv 3^{11}\text{ (mod }17)\) and \(6\equiv 3^{15}\text{ (mod }17)\). Then, replacing these, we see that \begin{equation*}3^{11x}\equiv 3^{15}\text{ (mod }17)\end{equation*} yields \begin{equation*}11x\equiv 15\text{ (mod }16)\, ;\end{equation*} 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, it checks out with Sage.
Example10.5.5
Let's try to solve \(16^x\equiv 13\text{ (mod }19)\).
Recall that \(2\) is a primitive root of \(19\), and obviously \(16=2^4\). It might look harder to represent \(13\); of course we could do it with the computer, but note that \(13+19=32=2^5\). Sometimes we really can do them by hand!
Thus our congruence becomes \begin{equation*}2^{4x}\equiv 2^{5}\text{ (mod }19)\end{equation*} which yields \begin{equation*}4x\equiv 5\text{ (mod }18)\, .\end{equation*} We already saw in Subsection 10.5.1 that this has no solutions, so neither does the original congruence.
