Generally addition is easier than multiplication. The logarithm and exponent are important tools because they can translate problems about multiplication to problems about addition. They are functions such that \[ a^{x+y}=a^x\cdot a^y\text{ and }\log_a(xy)=\log_a(x)+\log_a(y), \] and the 17th century mathematician Napier used them to simplify complicated computations. For example, if he wanted to compute \(145940^3\), he would look up through a table of logarithms to see \[ \log_{10}(1.4594)=0.164,\text{ so }\log_{10}(145940)=5.164. \] He would then use properties of logarithms to see \[ \log_{10}(145940^3)=5.164\cdot3=15.492, \] then look back at his table of logarithms to see \(10^{0.492}=3.104\), so \[ 145940^3=3.104\times10^{15}, \] approximately.
Moreover, we could have chosen any base instead of \(10\). For example logarithms and exponentials with base \(2\) can be translated to logarithms and exponentials with base \(10\) since \[ 2^x=10^{\log_{10}(2)x}\text{ and }\log_2(x)=\log_2(10)\cdot\log_{10}(x). \]
In number theory we are interested in working modulo a prime number \(p\). There are crucial differences from exponentials and logarithms in calculus:
To illustrate this second point, let's see how different bases work modulo \(p=7.\)
| n=0 | n=1 | n=2 | n=3 | n=4 | n=5 | n=6 | |
|---|---|---|---|---|---|---|---|
| 2ⁿ mod 7 | 1 | 2 | 4 | 1 | 2 | 4 | 1 |
| 3ⁿ mod 7 | 1 | 3 | 2 | 6 | 4 | 5 | 1 |
This table shows a sampling of two particular bases. Note that, when we use the base \(2,\) the numbers \(3, 5,\) and \(6\) are never hit, so \(2\) is not a very good base for the exponential. However, when we use base \(3\), we find that every possible nonzero residue \(1, 2, 3, 4, 5, 6\) modulo 7 is hit. This means that, if we want to use logarithms to perform mod 7 arithmetic, the same Napier did with usual arithmetic, then we can't use base 2 logarithms, but we can use base 3 logarithms.
We say \(g\) is a primitive root modulo the prime \(p\) if the exponentials \(g^n\) cover all residues \(1, 2, ..., p-1\) modulo \(p.\) For example, when \(p=7,\) we saw above that \(3\) was a primitive root, but \(2\) was not. Mod 7 arithmetic has another primitive root, 5, because the powers of 5 also hit every residue modulo 7, as shown in the below table.
| n=0 | n=1 | n=2 | n=3 | n=4 | n=5 | n=6 | |
|---|---|---|---|---|---|---|---|
| 5ⁿ mod 7 | 1 | 5 | 4 | 6 | 2 | 3 | 1 |
| 3ⁿ mod 7 | 1 | 3 | 2 | 6 | 4 | 5 | 1 |
It is known that primitive roots always exist, modulo any prime \(p\)! With the calculator below, you can find primitive roots modulo a few small primes, as an example.
| n |
|---|
Notice how, whenever you do have a primitive root \(g,\) you always have \(g^{p-1} = 1.\) In other words, the last power of a primitive root is always 1.
Primitive roots, like logarithms, are a great tool for turning questions about multiplication (hard) into questions about addition (easy).
For example, when is a number \(a\) a square modulo \(p\), i.e., when does the equation \(x^2\equiv a\pmod p\) have a solution?
This is a question about multiplication, because of this \(x^2.\) So to answer it, let's use a primitive root. Take \(g\) a primitive root modulo \(p.\) Then any \(x\) can be written as \(x=g^k\) for some number \(k,\) so that \[ x^2=(g^k)^2=g^{2k}. \] Note that \(a = g^n,\) for some integer \(n.\) So the question of when \[x^2 \equiv a \pmod{p}\] has a solution is equivalent to the question of if \(n\) is even or odd. Checking if a number is even or odd is much easier than checking if a number is a perfect square!
As an example of this procedure, let's compute some square roots modulo \(17.\) One example of a primitive root modulo 17 is \(3\); so, all the even powers of 3 are square roots modulo 17, and all the odd powers of 17 are not squares modulo 17.
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 3ⁿ mod 17 | 1 | 3 | 9 | 10 | 13 | 5 | 15 | 11 | 16 | 14 | 8 | 7 | 4 | 12 | 2 | 6 | 1 |
| Perfect square mod 17? | Yes | No | Yes | No | Yes | No | No | No | Yes | Yes | Yes | No | Yes | No | Yes | No | Yes |
From this table, we can see that \(3^{10} \equiv 8\pmod{17},\) so that 8 is a perfect square modulo 17, with square root \[3^{10/2} \equiv 3^5 \equiv 5\pmod{17}.\] And indeed, \[5^2 - 8 = 17\] is a multiple of 17, so \(8 \equiv 5^2\pmod{17},\) just as our table predicted!
This method has one downside, though: finding a primitive root \(g,\) and writing \(a\) as a power of \(g,\) can be quite hard computationally! (This is called the discrete logarithm problem, and in fact is so computationally hard that its difficulty is exploited in cryptography.) However, Euler still found a remarkable theoretical application of this procedure.
When is \(-1\) a perfect square modulo \(p\)? Over the real numbers, \(-1\) isn't a perfect square... this is why we had to invent the imaginary number \(i.\) But sometimes in modular arithmetic, it is the case that \(-1\) is a perfect square! For example, \(2^2 \equiv 4 \equiv -1\pmod{5}.\)
Euler wanted to know when \(-1\) is a square modulo a prime \(p.\) It sometimes is (like for \(p=5\)), and sometimes isn't (like when \(p=3\)). To answer this, Euler observed that if there was some integer \(i\) so that \[i^2 \equiv -1\pmod{p},\] then \(i^4 \equiv +1 \pmod{p}.\) Thus, if we write \[i = g^k,\] for \(k\) some integer and \(g\) a primitive root modulo \(p,\) then \[1 = g^{4k}.\]
We can always write \(1 = g^{p-1},\) whenever we have a primitive root \(g,\) as we observed at the end of the last section. So, \(-1\) is a perfect square modulo \(p\) precisely when \(p-1\) is a multiple of 4!
Let me end by explaining why should you care whether or not \(\sqrt{-1}\) exists modulo \(p\).
The existence of \(\sqrt{-1}\) is related to the following gem, discovered by Fermat in the 1600s: an odd prime number \(p\) can be written a sum of two perfect squares exactly when \(p\equiv1\pmod4\). For example: \[ 5=1^2+2^2,\ 13=2^2+3^2,\ 17=1^2+4^2,\ 29=2^2+5^2,\ 37=1^2+6^2,\cdots, \] but \(7, 11, 19\), etc. cannot be expressed in this way. How on earth is this related to \(\sqrt{-1}\)? Well, if we know \(x^2+y^2=p\) then modulo \(p\), we know \[ x^2+y^2\equiv0\pmod p, \] or in other words, \[ x^2\equiv -y^2\pmod p. \] Dividing both sides by \(y^2\), we see that \[ (x/y)^2\equiv -1\pmod p! \]
For example, \(17=1^2+4^2\) is saying that \(4\) is a square root of \(-1\) modulo \(17\).
When \(p = 13,\) something a little more interesting happens. In this case, the equation would read \[ (3/2)^2\equiv-1\pmod{13}, \] but what does \(3/2\) mean modulo \(13\)?
There is a very clever slight of hand which mathematicians performed here. Recall the story of exponents: \(2^3\) means \(2 \times 2 \times 2,\) and generally \(2^n\) means ``multiply \(2\) by itself \(n\) times." But then how do \(2^{-1}\) or \(2^{1/2}\) make sense? The idea is to define them using the exponent rule \[2^{a+b} = 2^a \cdot 2^b.\] It follows that, whatever \(2^{-1}\) means, it should obey \[2^{1 + (-1)} = 2^1 \cdot 2^{-1},\] and whatever \(2^{1/2}\) means, it should obey \[2^{(1/2) + (1/2)} = 2^{1/2} \cdot 2^{1/2}.\] From these equations, you see that \(2^{-1}\) has to be \(1/2,\) and \(2^{1/2}\) has to be \(\sqrt{2}.\)
Following this idea, we will interpret \(3/2\) modulo \(13\) to be some number such that \[2 \cdot \frac{3}{2} \equiv 3 \pmod{13}.\] You can check that \[2 \cdot 8 \equiv 3 \pmod{13},\] so we can say \(3/2 \equiv 8 \pmod{13}.\) Thus the expression \(13 = 2^2 + 3^2\) is telling us that \(3/2 \equiv 8\pmod{13}\) is a square root of \(-1\) modulo \(13.\)