Number theory

Just as in the case of set theory, our discussion of number theory will be strictly naive, e.g., we shall not develop $\mathbb{N}$ from axioms, we shall just assume that if $S\subset \mathbb{N}$ and $S\not= \emptyset$, then $S$ has a smallest element, etc. We first establish the division algorithm:

Theorem 1.2.1 (Division Algorithm)   : Let $a,b \in\mathbb{Z}$ with $b\not= 0$. Then there exist unique integers $q$ and $r$ such that

$$a = bq + r\ \ \ \ {\rm and}\ \ \ \ 0 \leq r < \vert b\vert .$$

Proof: Let

$$S = \{m\vert b\vert\ \vert\ m \in Z \ {\rm and}\ m\vert b\vert\leq a\}.$$

Note that $S\not= \emptyset$ because $-\vert a\vert \vert b\vert\in S$. The set $S$ must therefore contain a largest element, say $t\vert b\vert$ . Then, by the definition of $S$, $t\vert b\vert\leq a$. Putting $r = a - t \vert b\vert$ , we have

$$a = t \vert b\vert + r \ \ \ \ \ {\rm where} \ \ \ \ \ r \geq 0.$$ (1.1)

But $(t + 1)\vert b\vert = t\vert b\vert + \vert b\vert > t \vert b\vert$. Thus by the maximality of $t\vert b\vert$, $(t + 1)\vert b\vert\notin S$, so $(t + 1)\vert b\vert > a$. Hence

$$t \vert b\vert + \vert b\vert > t \vert b\vert + r$$

or $r < \vert b\vert$ . Finally let

$$q= \left\{ \begin{array}{cc} t, & {\rm if}\ \ b>0,\\ -t, & {\rm if}\ \ b<0, \end{array}\right.$$

So that $qb = t\vert b\vert$ if $b > 0$ and $qb = -tb = t(- b) = t\vert b\vert$ if $b < 0$. Thus by (1.1)

$$a = qb + r \ \ \ \ \ {\rm where} \ \ \ \ \ 0 \leq r < \vert b\vert,$$

and the existence part of the theorem has been established.

Suppose now that

$$a = bq + r = bq + r$$

where $0 \leq r < \vert b\vert$ and $0 \leq r < \vert b\vert$. Then

$$r-r'=b(q'-q),$$ (1.2)

but $-\vert b\vert < r - r' < \vert b\vert$, which in conjunction with (1.2) implies $r - r' = 0$; thus $bq = bq'$, thus $q = q'$ (since $b\not= 0$). So we have uniqueness and our proof is complete. $\Box$

Let $a,b \in\mathbb{Z}$. We say that $b$ divides $a$, written $b\vert a$, if there exists a $c \in \mathbb{Z}$ such that $a = bc$. If $b$ does not divide $a$, we write $b \not\vert a$.

Definition 1.2.2   The greatest common divisor (g.c.d.) of two integers $a$ and $b$ is a positive integer $d$, denoted by $gcd (a,b)$, such that $d\vert a$ and $d\vert b$, and if $c$ is any integer such that $c\vert a$ and $c\vert b$, then $c\vert d$. (Here we assume that $a$ and $b$ are not both $0$; in that case, we define $gcd (0,0) = 0$.)

We observe first that if the $gcd (a,b) exists$, then it is unique. To see this, suppose we have two g.c.d.'s $d$ and $d'$. Since $d\vert a$ and $d\vert b$, and since $d = gcd (a,b)$, then we must have $d\vert d'$. Similarly, $d'\vert d$; hence $d = d$ (since the g.c.d. $> 0$, by definition).

Now let us show the g.c.d exists. Suppose $a,b \in\mathbb{Z}$ and also suppose $a \not= 0$ or $b\not= 0$. We let $S$ denote the set of all positive integers of the form $xa + yb$ where $x, y \in \mathbb{Z}$. $S\not= \emptyset$, and therefore, $S$ must contain a smallest integer, $d$. We claim that $d = gcd (a,b)$. Since $d \in S$, there exist $x_1, y_1 \in \mathbb{Z}$ such that

$$d=x_1a+y_1b.$$ (1.3)

If $c\vert a$ and $c\vert b$, then clearly from (1.3) $c\vert d$. Therefore, we must simply show that $d\vert a$ and $d\vert b$. By the Division Algorithm,

$$a = dq + r, \ \ \ \ \ {\rm where} \ \ \ \ 0 \leq r < d.$$

Hence $r = a - dq = a - q (x_1 a + y_1 b)= x_2 a + y_2 b$, where $x_2 = 1 - qx_1$ and $y_2 = qy_1$. Thus if $r > 0$, then $r \in S$, which would contradict the minimality of $d$. Thus $r = 0$ and $d\vert a$. Similarly, $d\vert b$.

Summarizing, we have the following result.

Theorem 1.2.3   The greatest common divisor $d = gcd (a,b)$ of any two integers exists, is unique, and can be expressed in the form $d = xa + yb$ where $x, y \in \mathbb{Z}$.

Note that while $d$ is unique, $x$ and $y$ are not, e.g., if $a = 6$ and $b = 4$, then $d = 2$ and $(x, y)$ can be $(1, 1)$, $( 1,2)$, $(3, 4)$. etc. We note that the proof we have given for the existence of the g.c.d. is not constructive. We wish now to given an alternate proof for the existence of the g.c.d. which at the same time yields a systematic finite constructive way (or an algorithm) for obtaining it. (This is called the Euclidean Algorithm.) We assume without loss of generality that $b > 0$ (go through this for $b < 0$ to convince yourself that it can be done!). We then write

$$a = bq_1 + r_1, \ \ \ \ 0 \leq r_1 < b.$$

Now if $r_1 = 0$, the process stops. If not, we write

$$b = r_1q_2 + r_2, \ \ \ \ 0 \leq r_2 < r_1.$$

If $r_2 = 0$, the process stops. If not, write

$$r_1 = r_2q_3 + r_3, \ \ \ \ 0 \leq r_3 < r_2$$

and continue until a $0$ remainder is obtained, which must be the case eventually since $b > r_1 > r_2 > r_3 > ...$ is a sequence of decreasing positive integers. Thus we have

$$\begin{array}{c} a = bq_1 + r_1\\ b = r_1q_2 + r_2\\ r_1 =... ...{n-2} = r_{n-1}q_n + r_n\\ r_{n-1} = r_{n}q_{n+1}, \end{array}$$ (1.4)

i.e., $r_n$ is the last nonzero remainder.

Now we claim that the above Euclidean Algorithm yields the gcd.

Proof: Note that $r_n\vert r_{n- 1}$, so from the next to the last equation in (1.4), we see that $r_n\vert r_{n- 2}$, and continuing up the ``scale'' in (1.4), we eventually see that $r_n\vert b$ and $r_n \vert a$. Now if $c\vert a$ and $c\vert b$, then the first equation in (1.4) implies that $c\vert r_1$, which implies, by the second equation that $c\vert r_2$, and continuing down in this fashion, we finally have that $c\vert r_n$. Thus $r_n = gcd (a,b)$. $\Box$

The reader should have no difficulty in applying this algorithm to particular cases. It also should be noted that the Euclidean Algorithm, in particular equations (1.4), may also easily be used to write the g.c.d. of $a$ and $b$ as a linear combination of $a$ and $b$, i.e., in the form $xa + yb$ with $x, y \in \mathbb{Z}$.

For $a,b \in\mathbb{Z}$, if $gcd (a,b) = 1$, then we say that the integers $a$ and $b$ are relatively prime (or coprime).

Definition 1.2.4   The least common multiple (l.c.m.) of two nonzero integers $a$ and $b$ is a positive integer $t$, written $lcm (a,b)$, such that $a\vert t$ and $b\vert t$, and if $a\vert c$ and $b\vert c$, then $t\vert c$. We define $lcm (0,a) = 0$ for any integer $a$.

As in the case of the g.c.d., it is easy to see that if the l.c.m. exists it is unique. Therefore we consider the existence. Since by Definition 1.2.4 $lcm (0,a) = 0$ for any $a\in\mathbb{Z}$, we now assume that both $a$ and $b$ are nonzero integers. Note that there is at least one positive common multiple, namely $\pm ab$. Thus there must exist a smallest positive common multiple. Call it $t$. Let $c$ be any common multiple of $a$ and $b$. Clearly, $gcd (t,c) \leq t$. However, $a\vert t$ and $a\vert c$; therefore, $a\vert gcd (t,c)$. Similarly, $b\vert gcd (t,c)$. Hence, $gcd (t,c)$ is a common multiple of $a$ and $b$. Since $t$ was chosen as the smallest positive common multiple, we must have $t = gcd (t,c)$. This implies $t\vert c$, and completes the existence proof.

We will now establish a few useful properties regarding the g.c.d. and l.c.m. which will be used quite frequently.

Theorem 1.2.5   If $m$ is a positive integer, then $gcd (ma,mb) = m gcd (a,b)$.

Proof: Let $d = gcd (a,b)$ and $\delta = gcd (ma,mb)$. Since $d\vert a$ and $d\vert b$, we have that $md\vert ma$ and $md\vert mb$; consequently $md\vert\delta$. On the basis of Theorem 1.2.3, we can write $d = xa + yb$, where $x, y \in \mathbb{Z}$. Then $md = x(ma) + y (mb)$ from which it is clear that $\delta\vert md$. Thus $\delta = md$, i.e., $gcd (ma,mb) = m gcd (a,b)$. $\Box$

The next theorem is actually a simple consequence of Theorem 1.2.5.

Theorem 1.2.6   If $m$ is a positive integer, and if $m\vert a$ and $m\vert b$, then $gcd(\frac{a}{m},\frac{b}{m})= \frac{gcd(a,b)}{m}$.

Proof: $gcd(a,b)=gcd(m\frac{a}{m},m\frac{b}{m}) =m\cdot gcd(\frac{a}{m},\frac{b}{m})$, by Theorem 1.2.5. A division by $m$ completes the proof. $\Box$

Corollary 1.2.7   Let $d = gcd (a,b)$. Then $gcd(\frac{a}{d},\frac{b}{d})=1$.

Proof: $gcd(\frac{a}{d},\frac{b}{d})=\frac{gcd(a,b)}{d}=1$. $\Box$

In other words, the corollary states that when two numbers are divided by their g.c.d., the resulting quotients will be relatively prime.

Theorem 1.2.8   If $c\vert ab$, and $gcd (c,b) = 1$, then $c\vert a$.

Proof: Since $gcd (c,b) = 1$, there exist integers $x$ and $y$ such that $1 = bx + cy$. Thus $a = abx + acy$, and since $c\vert ab$ and $c\vert ac$, it is clear that $c\vert a$. $\Box$

Definition 1.2.9   A positive integer $p > 1$ is called a prime if its only divisors are $\pm 1$ and $\pm p$.

Using this notion, we can immediately state the following corollary to Theorem 1.2.8.

Corollary 1.2.10   If $p$ is a prime such that $p\vert ab$, then $p\vert a$ or $p\vert b$.

Proof: If $p\vert a$, are done. If $p\vert a$, then we claim that the $gcd (a,p) = 1$. For if $d = gcd (a,p)$, then $d\vert a$ and $d\vert p$. From the definition of prime, $d\vert p$ implies $d = 1$ or $=p$ (recall that the g.c.d. $> 0$). Since $p\not\vert a$, $d$ must be 1. Now from Theorem 1.2.8, $p\vert ab$ and $gcd (a,p) = 1$ imply $p\vert b$. $\Box$

As our final theorem pertaining directly to divisibility in $\mathbb{Z}$, we establish the following connection between the g.c.d. and l.c.m.

Theorem 1.2.11   If $a$ and $b$ are positive integers, then $gcd (a,b)\cdot lcm (a,b) = ab$.

Proof: Consider $\frac{ab}{gcd (a,b)}$. We can write this as

$$\frac{ab}{gcd (a,b)}= \frac{a}{gcd (a,b)}b,$$

which is certainly a multiple of $b$. Similarly,

$$\frac{ab}{gcd (a,b)}= \frac{b}{gcd (a,b)}a,$$

is a multiple of $a$. Hence $\frac{ab}{gcd (a,b)}$ is a common multiple of $a$ and $b$. Thus $lcm(a,b)\vert\frac{ab}{gcd (a,b)}$ or

$$lcm(a,b)gcd (a,b)\vert ab.$$ (1.5)

Next, consider $\frac{ab}{lcm (a,b)}$. This is integral since $lcm (a,b)\vert ab$. Also, since $a\vert lcm (a,b)$, we have $lcm(a,b) =ac$, for some $c \in \mathbb{Z}$. This imples

$$\frac{ab}{lcm (a,b)}=\frac{ab}{ac}=\frac{b}{c},$$

and so $b/c$ is integral. However, $\frac{b}{c}\vert b$. Thus $\frac{ab}{lcm (a,b)}\vert b$, Similarly, $\frac{ab}{lcm (a,b)}\vert a$, and therefore $\frac{ab}{lcm (a,b)}\vert gcd(a,b)$, or

$$ab\vert lcm (a,b)\cdot gcd(a,b).$$ (1.6)

Comparing (1.6) and (1.5) yields the theorem. $\Box$

As our final consideration in this section, we turn to the equivalence relation introduced in Example 1.1.3. We recall that $a \equiv b$ (mod $m$) means $m\vert (a - b)$.

We next note that any integer a is congruent modulo $m$ to one of the integers $0, 1, 2, ..., m - 1$. For by the Division Algorithm, we can write $a = qm + r$, where $0 \leq r < m$, so $a - r = qm$, i.e., $a \equiv r$ mod $m$, where $0 \leq r < m$.

We therefore have $m$ distinct equivalence classes $[0]$, $[1]$, $[2]$, ..., $[m - 1]$ such that any integer is in one of these classes, and the classes are disjoint. The equivalence classes for this special equivalence relation are usually called residue classes modulo $m$, and a set of elements, exactly one from each class, is referred to as a complete residue system modulo $m$.

We shall now establish a few properties of the congruence relation.

Theorem 1.2.12   If $a \equiv b$ (mod $m$) and $c \equiv d$ (mod $m$) then

(1)

$a + c \equiv b + d$ (mod $m$),

(2)

$ac \equiv bd$ (mod $m$).

Proof: For (1), $m\vert (a - b)$ and $m\vert (c - d)$ imply $m\vert (a - b + c - d)$, i.e., $m\vert( a + c - (b + d))$ which is equivalent to (1). For (2), $m\vert (c - d)$ and $m\vert (a - b)$ imply $m\vert a(c - d)$ and $m\vert d(a - b)$. Thus $m\vert a(c - d) + d(a - b)$ or $m\vert (ac - bd)$, which is equivalent to (2). $\Box$

Thus with regard to addition and multiplication, the congruence relationship behaves like equality. This ceases to be the case with divisibility; e.g., it does not follow from $ac \equiv bc$ (mod $m$) that $a \equiv b$ (mod $m$). For example $9 \equiv 6$ (mod $3$) but $3\not\equiv 2$ (mod $3$). We do, however, have the following theorem pertaining to division.

Theorem 1.2.13   If $ac \equiv bc$ (mod $m$) and if $d = gcd (c,m)$, then $a \equiv b$ (mod $\frac{m}{d}$).

Proof: By the hypothesis, $m\vert c(a - b)$.

Let $c = dc'$ and $m = dm'$ where $c' , m'\in \mathbb{Z}$, and $gcd (c' ,m' ) = 1$ by the Corollary 1.2.7. Then $dm'\vert dc (a- b)$, or $m'\vert c' (a - b)$. Since $(c' ,m' ) = 1$, Theorem 1.2.8 implies that $m' \vert (a - b)$. This means that $a \equiv b$ (mod $m'$) and since $m' = \frac{m}{d}$ this completes the proof. $\Box$

We can see from this theorem that should $gcd (c,m) = 1$ (i.e., if $c$ and $m$ are relatively prime), then we can divide by $c$ in a relationship of the form $ac \equiv bc$ (mod $m$).

Definition 1.2.14   If $n$ is a positive integer, the Euler $\phi$-function, $\phi(n)$ is defined to be the number of positive integers less than or equal to n and relatively prime to n.

One can show, that if $gcd (m,n) = 1$, then $\phi(mn) = \phi(m)\phi(n)$. Such functions are called multiplicative. (See Theorem 9.2.5.)

Finally, suppose that $a$ is an integer prime to the positive integer $m$, i.e., $gcd (a,m) = 1$. We claim that every element of the residue class $[a]$ is also prime to $m$. Thus suppose that $b\in [a]$, so $b \equiv a$ (mod $m$). If $d = gcd (b,m)$, then since $m\vert (b - a)$, $d \vert(b - a)$, but $d\vert b$, so $d\vert a$. Consequently, $d\vert a$ and $d\vert m$ which implies $d = 1$ since $gcd (a,m) = 1$. On the basis of this it makes sense to say that a residue class is prime to $m$. We know that there are $\phi(m)$ residue classes prime to $m$, and a set of elements, exactly one from each of these classes, is called a reduced residue system modulo $m$.

We shall denote the set of residue classes prime to $m$ by ${\cal R} (m)$.