Elementary Number Theory - 1.1 Definitions and Propositions

Definition:

Suppose that \(a,b \in \mathbb{Z}\) and \(a\neq 0\). Then we say that \(a\) divides \(b\), denoted by \(a|b\), if there exists \(c \in \mathbb{Z}\) such that \(b=ac\). In this case, we also say that \(a\) is a divisor of \(b\) (or) \(b\) is a multiple of \(a\).

Theorem:

Suppose that \(a \in \mathbb{N}\) and \(b \in \mathbb{Z}\). Then there exists unique \(q,r \in \mathbb{Z}\) such that \(b=aq+r\) and \(0 \leq r \lt a\)

Proof:

First we need to show the existence of \(q,r \in \mathbb{Z}\). Consider the set \[S = \{b-as \geq 0 : s \in \mathbb{Z}\}.\] \(S \subset \mathbb{N}\) and hence by well-ordering principle there exists a least element in \(S\). Call the least element \(r\). Claim now is that \(0 \leq r \lt a\). Clearly, since \(r \in S\), we have \(r \geq 0\). Now assume that \(r \geq a\). Now \(r = b-as_1 \geq a\) for some \(s_1 \in \mathbb{Z}\). Consider \(r_1 = r-a = b- as_1 - a \geq a-a = 0\) i.e. \(r_1 = b- a (s_1 + 1) \geq 0 \implies r_1 \in S\). However, \(r_1 < r\). This contradicts the minimality of \(r\). Hence, \(0 \leq r \lt a\) and thereby the existence follows.

To prove the uniqueness, as always, assume that there are two distinct sets of numbers \(q_1,r_1 \in \mathbb{Z}\) and \(q_2,r_2 \in \mathbb{Z}\) such that \(aq_1 + r_1 = b = aq_2 + r_2\) and \(0 \leq r_1,r_2 \lt a\). Assume without loss of generality that \(q_1 \lt q_2\). This obviously implies \(r_1 \gt r_2\). Hence, we get \(0 \lt a(q_2-q_1) = r_1 - r_2\). This means that \(a|(r_1 - r_2)\). But, since \(r_1 \gt r_2\), \(0 \lt r_1 - r_2 \lt a\). CONTRADICTION. Hence, the uniqueness follows. \(\Box\)

Theorem:

Suppose that \(a,b \in \mathbb{N}\). Then there exists a unique \(d \in \mathbb{N}\) such that

1. there exists \(x,y \in \mathbb{Z}\) such that \(d = ax+by\);
2. \(d|a\) and \(d|b\);
3. for every \(k\in \mathbb{N}\) such that \(k|a\) and \(k|b\), we have \(k|d\).

Proof:

Consider the set \(I = \{au + bv : u,v \in \mathbb{Z}\}\). Clearly, \(I \subseteq \mathbb{Z}\). By well-ordering principle, there exists a least positive element in \(I\). Call it \(d\). We have \(d = ax+by\) for some \(x,y \in \mathbb{Z}\). 

We now want to show that \(d|a\) and \(d|b\). In fact, we shall show that \(d|(au+bv)\), \(\forall u,v, \in \mathbb{Z}\). By the previous theorem, we get that \(au+bv = dq + r\) where \(0 \leq r \lt d\). Since \(d = ax+by\), we get \(au+bv - (ax+by)q = r\) i.e. \(r = a(u-qx) + b(v-qy)\). Hence, \(r \in I\) and \(0 \leq r \lt d\). But \(d\) is the least positive element in \(I\). This gives us that \(r=0\). Hence, \(d\) divides all elements in the set \(I\). Setting \(u=1\) and \(v=0\) gives us that \(d|a\) and setting \(u=0\) and \(v=1\) gives us that \(d|b\).

We now need to prove that for every  \(k\in \mathbb{N}\) such that \(k|a\) and \(k|b\), we have \(k|d\). We have that \(d = ax+by\). Further since \(k|a\) and \(k|b\), we get \(a=ka_1\) and \(b=kb_1\), where \(a_1,b_1 \in \mathbb{Z}\). Hence, we get \(d = k (a_1x + b_1y)\). Since \(a_1x + b_1y \in \mathbb{Z}\), we get \(k|d\).  \(\Box\)

Definition:

The number \(d\) satisfying the criteria in the above theorem is called the greatest common divisor of \(a\) and \(b\). It is typically denoted as \(d=(a,b)\)

Theorem: (Euclid Algorithm)

Suppose that \(a,b \in \mathbb{N}\). Suppose further that \(q_1,q_2,\ldots,q_{n+1} \in \mathbb{Z}\) and \(r_1,r_2,\ldots,r_n \in \mathbb{N}\) satisfy \(0 \lt r_n \lt r_{n-1} \lt \cdots \lt r_1 \lt a\) and \[b = aq_1 + r_1\] \[a = r_1q_2 + r_2\] \[r_1 = r_2q_3 + r_3\] \[\vdots\] \[r_{n-2} = r_{n-1}q_n + r_n\] \[r_{n-1} = r_{n}q_{n+1}\] Then \((a,b) = r_n\)

Proof:

We shall first prove that \((b,a) = (a,r_1)\). This is not hard to prove. This follows immediately once we note that if \(k\) divides \(a\) and \(b\) then \(k\) has to divide \(r_1\). Similarly, if \(m\) divides \(a\) and \(r_1\) then \(m\) has to divide \(b\). Hence, \((b,a) = (a,r_1)\). Now it follows by repeatedly recognizing this fact that \((b,a) = (a,r_1) = (r_1,r_2) = (r_2,r_3) = \cdots = (r_{n-2},r_{n-1}) = (r_{n-1},r_{n}) = (q_{n+1}r_{n},r_{n}) = r_n\). \(\Box\)

Theorem:

Suppose that \(a,b \in \mathbb{N}\) and \((a,b) = 1\). Suppose further that \(w \in \mathbb{N}\) satisfies \(w|ab\), then there exists a unique \(u,v \in \mathbb{N}\) such that \(u|a\), \(v|b\) and \(w = uv\)

Proof:

Let \(u = (w,a)\) and \(v = (w,b)\). We shall show that \(u|a\), \(v |b\) and \(w = uv\). From the definition of \(u\) and \(v\) it is clear that \(u|a\) and \(v|b\). All we need to show is that \(uv = w\). From the theorem proved earlier, we have that \(u = wx_1 + ay_1\) for some \(x_1,y_1 \in \mathbb{Z}\) and \(v = wx_2 + by_2\) for some \(x_2,y_2 \in \mathbb{Z}\). Hence, we get \(uv = (wx_1 + ay_1)(wx_2 + by_2)\). We also have \(ab = wk\) for some \(k \in \mathbb{Z}\). Hence expanding we get, \(uv = w(wx_1x_2 + x_1by_2 + ay_1x_2 + ky_1y_2)\). Hence, \(w|(uv)\).

Now we will show that \((uv)|w\). Since \((a,b) = 1\), \(\exists x,y \in \mathbb{Z}\) such that \(ax+by = 1\). Multiply by \(w\) to get \(w = wax + wby\). Since \(u = (w,a)\), we get \(w = uw_u\) and \(a = ua_u\). Also since \(v = (w,b)\), we get \(w = v w_v\) and \(b = v b_v\). Hence, \(w = v w_v u a_u x + u w_u v b_v y \implies w = u v (w_v a_u x + w_u b_v y) \implies (uv)|w\).

Now, we still need to show uniqueness. If we have another set, say \(u_1,v_1\), such that \(u_1 | a\), \(v_1 | b\) and \(w = u_1 v_1\). We have that \(u = wx_1 + ay_1 = u_1 v_1 x_1 + u_1 k_1 y_1 = u_1 (v_1 x_1 + k_1 y_1)\) . Hence, we get \(u_1|u\) i.e. \(u = u_1 m_1\). Similarly, we have that \(v = wx_2 + by_2 = u_1 v_1 x_2 + v_1 k_2 y_2 = v_1 (u_1 x_2 + k_2 y_2)\) . Hence, we get \(v_1|v\) i.e. \(v = v_1 l_1\). But we have that \(uv = w = u_1v_1\) and hence we get \(l_1m_1 = 1\) and since \(u,v,u_1,v_1 \in \mathbb{N}\), we get \(l_1 = m_1 = 1\) and hence \(u_1 = u\) and \(v_1 = v\). \(\Box\)