0.1 Number Theory
There are quite a few important that I wish to discuss before we do Diophantine equations. I don’t think some of the contents come out in the actual exam as many are focused on Diophantine equations, but let’s go over them anyways as a review.
Definition 0.1.1
A residue class of \(a\) mod \(n\) is the collection of all numbers that are congruent to \(a \pmod {n}\). The complete residue system mod \(n\) is the set of exactly one representative from each of the \(n\) residue classes. The reduced residue system is a set of all elements from the complete residue system that only contains the elements that are relatively prime to \(n\).
An example for modulo \(6\) is that the complete residue system is \(\{ 0, 1, 2, 3, 4, 5 \}\) while the reduced residue system is \(\{ 1, 5 \}\). The reduced residue system for modulo \(6\) does not have to be \(\{ 1, 5 \}\), but \(\{ 7, -1 \}\) too.
With this definition, we can also define a very special and important function.
Definition 0.1.2: Euler’s Totient Function
Euler’s Totient Function, denoted as \(\phi (n)\) is the number of elements in the reduced residue system mod \(n\).
By definition, there are few ways to think about this function.
\(\phi (n)\) can be interpreted as the number of integers from \(1\) to \(n\) that are relatively prime to \(n\).
As you can see from our previous example of residue systems, we can see that \(\phi (6) = 2\). Another very important topic about Euler’s Totient function is its formula. Consider the following equation for prime \(p\). \[ \phi \left ( p^\alpha \right ) = p^\alpha - \left \lfloor \frac {p^\alpha }{p} \right \rfloor = p^\alpha - p^{\alpha - 1} = p^\alpha \left ( 1 - \frac {1}{p} \right ) \] This holds because the floor function, or Gauss function, represents the number of elements that are multiples of \(p\) and \(p\) is relatively prime to other numbers that are not multiple of \(p\). Before deriving the formula, let’s briefly take a look at its multiplicative property.
\(\phi (ab) = \phi (a) \phi (b)\) for \((a, b) = 1\).
There are few ways to prove this property, but let’s prove with the following arrangement. \[ \begin {array}{ccccc} 1 & 2 & 3 & \cdots & b \\ b + 1 & b + 2 & b + 3 & \cdots & 2b \\ 2b + 1 & 2b + 2 & 2b + 3 & \cdots & 3b \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \cdots & \cdots & \cdots & \cdots & ab \end {array} \] As you can see, \(\phi (b)\) is the number of integers that are relatively prime to \(b\) in the first row. In other words, there exists exactly \(\phi (b)\) columns that contain the integers that are relatively prime to \(b\). Let \(j\) be a relatively prime integer to \(b\). Because \((a, b) = 1\), it is self-evident that there exists \(\phi (a)\) numbers that are relatively prime to \(a\) in \(j^\text {th}\) column. Because there exists \(\phi (b)\) such columns, the total number of integers that are relatively prime to both \(a\) and \(b\), or relatively prime to \(ab\), is \(\phi (a) \phi (b)\) and \(\phi (ab) = \phi (a) \phi (b)\) holds for \((a, b) = 1\).
Continuing with this property, we can see that the same applies if we prime factorize \(n\) as \(n = p_1^{\alpha _1} p_2^{\alpha _2} \cdots p_k^{\alpha _k}\) for prime \(k\). In other words, we can write the formula as the following. \[ \phi (n) = p_1^{\alpha _1} \left ( 1 - \frac {1}{p_1} \right ) \cdots p_k^{\alpha _k} \left ( 1 - \frac {1}{p_k} \right ) = n \prod _{i=1}^k \left ( 1 - \frac {1}{p_i} \right ) \]
There is also very important property \[ \sum _{d \mid n} \phi (d) = n \] but maybe we can discuss this later.
Continuing, we can define another very important term.
Definition 0.1.3
For integers \(n\) and \(a\) such that \((a, n) = 1\), the order of \(a\) mod \(n\), denoted as \(\ord _n a\) is the least positive integer \(k\) such that \(a^k \equiv 1 \pmod {n}\).
Some examples of this would include \(\ord _n 1 = 1\) and \(\ord _n (-1) = 2\) for all \(n > 3\). We will discuss more on primitive roots and the properties of the order of \(a\) mod \(n\) later in the notes. Continuing with the totient function, we can derive two important theorems.
Proof.
Let \(\{ r_1, r_2, \ldots , r_{\phi (n)} \}\) be the set of integers that are relatively prime to \(n\). Note that for positive integer \(a\) such that \((a, n) = 1\), \(\{ ar_1, ar_2, \ldots , ar_{\phi (n)} \}\) is the same set since \(ar_i \not \equiv ar_j \pmod {n}\) for \(i \neq j\).
Therefore, \[ r_1 r_2 \ldots r_{\phi (n)} \equiv ar_1 ar_2 \ldots ar_{\phi (n)} \pmod {n} \] holds and \(a^{\phi (n)} \equiv 1 \pmod {n}\).
The next theorem Fermat’s Little Theorem can be proven with multiple ways, but let’s use Euler’s Theorem to prove it. They are frequently introduced together and some say Fermat’s Little Theorem is a corollary of Euler’s Theorem, but let’s consider it as a standalone theorem because there are plenty of other ways to prove the theorem.
Theorem 0.1.5: Fermat’s Little Theorem
For prime \(p\) and positive integer \(a\) such that \((a, p) = 1\), \(a^{p-1} \equiv 1 \pmod {p}\).
Proof.
By Euler’s Theorem, \(a^{\phi (p)} \equiv 1 \pmod {p}\). Because \(\phi (p) = p - 1\), the theorem holds.
Another very common way of representing this theorem is \(a^p \equiv a \pmod {p}\). Before we move on to the final theorem that we will discuss in this section, let’s take a look at an example of how they are used.
Exercise 0.1.6
Show that \(8^{43} \equiv 2 \pmod {10}\).
Solution.
We can use CRT for this, but let’s use Fermat’s Little Theorem here. How can we use it if \((8, 10) \neq 1\)? Well, we can force it. Consider the following congruences with \(8^{43} \equiv 0 \pmod {2}\) in mind. \begin{align*} 8^4 &\equiv 1 \pmod {5} \\ 8^{43} &\equiv 8^3 \equiv 2^9 \equiv 2 \pmod {5} \end{align*}
In other words, \(8^{43} = 5m + 2 = 2n\) for some integers \(m\) and \(n\). Because \(2 \mid m\), \(8^{43} \equiv 2 \pmod {10}\).
Like this, we can split the modulo \(n\) for our appropriate need. Before moving on to the final one and concepts related to the theorem, here is another example.
Exercise 0.1.7
Show that \(2009^{2008^{2007}} \equiv 81 \pmod {1000}\) [MATH01-5].
Solution.
First, notice that \((2009, 1000) = 1\) and \(\phi (1000) = 400\). Therefore, \(2009^{400} \equiv 1 \pmod {1000}\) and the following congruence holds for some \(n\) and \(k\). \[ 2009^{2008^{2007}} \equiv 2009^{400n + k} \equiv 2009^{k} \equiv 9^k \pmod {1000} \] Continuing, note that \(2008^{2007} \equiv k \pmod {400}\). Consider the following congruences. \begin{align*} 2008^{2007} &\equiv 2008^7 \equiv 8^7 \equiv 2^{21} \equiv 2 \pmod {25} \\ 2008^{2007} &\equiv 0 \pmod {16} \end{align*}
Therefore for some integer \(p\) and \(q\), \(2008^{2007} = 25p + 2 = 16q\). In other words, \(2008^{2007} = 25(16p' + 14) + 2 = 400p' + 352\) for some integer \(p'\). Therefore \(k = 352\) and it suffices to find \(9^{352}\) modulo \(1000\).
Continuing, \(2009^{2008^{2007}} \equiv 9^{352} \equiv 3^{704} \pmod {1000}\). Therefore, we can consider the following congruences with \(3^4 \equiv 1 \pmod {8}\) and \(3^{100} \equiv 1 \pmod {125}\). \begin{align*} 3^{704} &\equiv 81 \pmod {125} \\ 3^{704} &\equiv 1 \pmod {8} \end{align*}
Let \(3^{704} = 125r + 81 = 8s + 1\) for some integers \(r\) and \(s\). Therefore, \(3^{704} = 1000r' + 81\) for \(r' \in \mathbb {N}\) and \(2009^{2008^{2007}} \equiv 81 \pmod {1000}\).
With these techniques in mind, let’s conclude our review on number theory with a theorem and modular multiplicative inverse.
Definition 0.1.8
For two integers \(a\) and \(n\) such that \(a x \equiv 1 \pmod {n}\) and \((a, n) = 1\), \(x\) often denoted as \(a^{-1}\) is the modular multiplicative inverse of \(a\).
With this definition, we can see an interesting property. If we consider the equation \(ax + nm = 1\), we can know that there always exists integer \(x, m\) that satisfies the equation by Bézout’s Identity. In other words, integer \(x\) such that \(ax \equiv 1 \pmod {n}\) always exist if \((a, n) = 1\). Here, we could also see that if \(x_1 \neq x_2\) are both modular multiplicative inverse of \(a\), then \(ax_1 \equiv ax_2 \pmod {n}\) and \(x_1 \equiv x_2 \pmod {n}\), implying the uniqueness of the modular multiplicative inverse of \(a\) in the standard representatives.
For an integer \(a\) and modulo \(n\), if \((a, n) = 1\), then there always exists the modular multiplicative inverse of \(a\) and the inverse is unique in the residue system of \(n\).
With this, we can consider Wilson’s Theorem.
Theorem 0.1.9: Wilson’s Theorem
For an integer \(p > 1\), \((n - 1)! \equiv -1 \pmod {p}\) if and only if \(p\) is a prime.
Proof.
To prove this theorem, first consider the case when an integer is a modular multiplicative inverse of itself. \[ x \equiv x^{-1} \pmod {p} \] Note that by definition, \(x^2 \equiv 1 \pmod {p}\) holds if \(x \equiv 1 \pmod {p}\) or \(x \equiv p-1 \pmod {p}\). Moreover, there exists even number of integers \(1, \ldots , p-1\) for prime \(p > 2\). Because those numbers are prime to \(p\), there exists a unique modular multiplicative inverse, and this implies that the terms can be grouped in pairs, leaving only \((p - 1)! \equiv p - 1 \equiv -1 \pmod {p}\). Moreover, it is evident that the theorem holds for \(p = 2\). Furthermore, because the pairing does not apply when \(p\) is not a prime, the theorem holds.
This was it for the review on number theory! In our next section, we will review some of the basic topics in combinatorics.