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, 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 \[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.

So, just by substituting the primitive roots in for \(x^4\) and \(13\), we can say that \[x^4\equiv 13\text{ mod }(19)\] becomes \[2^{4i}\equiv 2^{5}\text{ mod }(19)\; .\]

How would we have solved this in 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 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\)): \[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:

Let's try the same congruence 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, there are 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:

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 \(3^i\) of \(3\) yields \(8\):

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.

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 \(6\equiv 3^{15}\text{ mod }(17)\). Then, replacing these, we see that \[3^{11x}\equiv 3^{15}\text{ mod }(17)\] 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: