C: Elementary Number Theory
- Page ID
- 74653
Here we review some basic number theoretic definitions and results. For the most part, we will just state the results. For a more detailed treatment, the student is referred references ,, or given in the bibliography. Unless otherwise stated in this appendix, all lower case letters, \(a\), \(b\), \(c\), etc. will be integers. Recall that we use \(\mathbb{N}\) to denote the set of natural numbers (also known as the positive integers) and we use \(\mathbb{Z}\) to denote the set of all integers, i.e., \[\nonumber \mathbb{N}= \{ 1,2,3, \dots \}\] and \[\nonumber \mathbb{Z}= \{ \dots, -3,-2,-1,0,1,2,3,\dots \}.\]
Let \(a,b \in \mathbb{Z}\). We say \(b\) divides \(a\) and we write \(b\ \vert\ a\) if there is an element \(c \in \mathbb{Z}\) such that \(a=bc\). We write \(b \ \not \vert \ a\) if \(b\) does not divide \(a\).
If \(b \ \vert \ a\) we also sometimes say that \(b\) is a factor of \(a\) or that \(a\) is a multiple of \(b\). To tell if \(b\) divides \(a\) where \(b \neq 0\), we simply divide \(a\) by \(b\) and see if the remainder is 0 or not. More generally, we have the following fundamental result.
For any integers \(a\) and \(b\) with \(b \neq 0\) there exists unique integers \(q\) and \(r\) such that \[ \nonumber a = bq+r, \qquad 0 \le r < |b|.\]
The number \(r\) in the above Lemma is denoted by \(a \bmod b\).
For example we have
\[ \nonumber 17 \bmod 5 = 2 \qquad \mbox{ since \quad $17 = 3 \cdot 5 + 2$ \ and \ $0 \le 2 < 5$}\] and \[ \nonumber (-17) \bmod 5 = 3 \qquad \mbox{ since \quad $-17 = (-4) \cdot 5 + 3$ \ and \ $0 \le 3 < 5$}.\]
An integer \(p\) is said to be prime if \(p \ge 2\) and the only positive factors of \(p\) are \(p\) and 1.
Let \(a\) and \(b\) be integers, at least one of which is non-zero. The greatest common divisor of \(a\) and \(b\) is the greatest positive integer, \(\gcd(a,b)\), that divides both \(a\) and \(b\). We define \(\gcd(0,0)=0\).
If \(a\) and \(b\) are non-zero integers, the least common multiple of \(a\) and \(b\) is the smallest positive integer, \(\text{lcm}(a,b)\), that is a multiple of both \(a\) and \(b\). If \(a=0\) or \(b=0\), we define \(\text{lcm}(a,b) = 0\).
An important property of primes is given by the following lemma.
If \(p\) is prime and \(p | ab\) then \(p | a\) or \(p | b\).
Perhaps the most fundamental result concerning integers is the following theorem, which is sometimes called The Fundamental Theorem of Arithmetic.
If \(n \ge 2\) is an integer, then there exists a unique list of primes \(p_1, p_2, \dots, p_k\) such that the following two conditions hold:
- \(p_1 \le p_2 \le \cdots \le p_k\),
- \(n = p_1 p_2 \cdots p_k\)
For example, if \(n=72\) the unique list of primes is 2, 2, 2, 3, 3.
Now fix a positive integer \(n\). Recall that \(\mathbb{Z}_n = \{ 0, 1, \dots , n-1 \}\) and that multiplication and addition in \(\mathbb{Z}_n\) are defined by
\(a + b =\) remainder when the ordinary sum of \(a\) and \(b\) is divided by \(n\), and
\(a \cdot b =\) remainder when the ordinary product of \(a\) and \(b\) is divided by \(n\).
To facilitate the proof that these two binary operations are associative, we temporarily denote addition in \(\mathbb{Z}_n\) by \(\oplus\) and multiplication in \(\mathbb{Z}_n\) by \(\odot\). This way we can use \(+\) and \(\cdot\) for ordinary addition and multiplication in \(\mathbb{Z}\). Thus we have \[\begin{aligned} a \oplus b &=&(a + b) \bmod n \\ a \odot b &=& (ab) \bmod n\end{aligned}\]
Proof Let \(r_1 = f(a)\) and \(r_2 = f(b)\). This implies that \[a = nq_1 + r_1, \quad 0 \le r_1 < n\] and \[b = nq_2 + r_2, \quad 0 \le r_2 < n\] Hence \[a+b= nq_1 + r_1 + nq_2 + r_2 = n(q_1+q_2) + r_1+r_2\] Now \[f(a) \oplus f(b) = r_1 \oplus r_2 = r\] where \[r_1 + r_2 = qn + r, \quad 0 \le r < n\] Hence \[a+b=n(q_1+q_2+q) + r, \quad 0 \le r < n\] and it follows that \[f(a+b)=(a+b) \bmod n = r,\] and we conclude that \[f(a+b) = r = f(a) \oplus f(b).\] This proves (C.1). The proof of (C.2) is similar and left to the interested reader.
The binary operations \(\oplus\) and \(\odot\) on \(\mathbb{Z}_n\) are associative.
Proof Using the notation in the theorem, we have for \(a,b,c \in \mathbb{Z}_n\): \(f(a) = a\), \(f(b) = b\) and \(f(c) = c\). Hence \[\begin{aligned} (a \oplus b) \oplus b &=& (f(a) \oplus f(b)) \oplus f(c)\\ &=& f(a+b) \oplus f(b) \\ &=& f( (a+b)+c)\\ &=& f(a + (b+c)) \\ &=& f(a) \oplus f(b+c) \\ &=& f(a) \oplus( f(b) \oplus f(c)) \\ &=& a \oplus (b \oplus c)\end{aligned}\] This proves that \(\oplus\) is associative on \(\mathbb{Z}_n\). The proof for \(\odot\) is similar and left to the interested reader.