Divisibility

Subsection 5.1.1 Divisibility

Definition 5.1.1.1.

Let \(a\) and \(b\) be integers, with \(a \neq 0\text{.}\) We say \(a\) divides \(b\text{,}\) denoted \(a \mid b\) , if there exists an integer \(k\) such that \(b = ak\text{.}\) In this case, we call \(a\) a factor of divisor of \(b\text{,}\) and \(b\) is a multiple of \(a\text{.}\) We write \(a \nmid b\) when \(a\) does not divide \(b\text{.}\)

🔗

Example 5.1.1.2. Divisibility.

\(3\) divides \(12\) 🔗: \(3 \mid 12\) since \(12 = 3 \cdot 4\text{.}\)
🔗
\(3\) does not divide \(7\) 🔗: \(3 \nmid 7\) since there is no integer \(k\) such that \(7 = 3k\text{.}\)
🔗

🔗

Theorem 5.1.1.3.

Let \(a\text{,}\) \(b\text{,}\) and \(c\) be integers with \(a \neq 0\text{.}\)

If \(a \mid b\) and \(a \mid c\text{,}\) then \(a \mid (b + c)\text{.}\)
🔗

🔗
If \(a \mid b\text{,}\) then \(a \mid bc\text{.}\)
🔗

🔗
Suppose in addition \(b \neq 0\text{.}\) If \(a \mid b\) and \(b \mid c\text{,}\) then \(a \mid c\text{.}\)
🔗

🔗

🔗

Proof.

Suppose \(a \mid b\) and \(a \mid c\text{.}\) Then there exists integers \(m\) and \(n\) such that \(b = am\) and \(c = a n\text{.}\) We want to show \(a \mid (b + c)\text{.}\) We compute

\begin{equation*} b + c = am + an = a(m + n). \end{equation*}

Since \(m\) and \(n\) are integers, \(m + n\) is an integer. Thus \(a \mid (b + c)\text{.}\)

🔗

🔗
Suppose \(a \mid b\text{.}\) Then there exists an integer \(n\) such that \(b = an\text{.}\) We want to show \(a \mid bc\text{.}\) We compute

\begin{equation*} bc = (an)c = a(nc). \end{equation*}

Since \(n\) and \(c\) are integers, \(nc\) is an integer. Thus \(a \mid bc\text{.}\)

🔗

🔗
Suppose \(a \mid b\) and \(b \mid c\text{.}\) Then there exist integers \(m\) and \(n\) such that \(b = am\) and \(c = bn\text{.}\) We want to show \(a \mid c\text{.}\) We compute

\begin{equation*} c = bn = (am)n = a (mn). \end{equation*}

Since \(m\) and \(n\) are integers, \(mn\) is an integer. Thus \(a \mid c\text{.}\)

🔗

🔗

🔗

Corollary 5.1.1.4.

Let \(a, b, c \in \ZZ\) with \(a \neq 0\text{.}\) If \(a \mid b\) and \(a \mid c\text{,}\) then \(a \mid (sb + tc)\) for all \(s, t \in \ZZ\text{.}\)

🔗

Theorem 5.1.1.5. Division algorithm for positive integers.

Let \(a\) and \(b\) be integers with \(b \gt 0\text{.}\) There exists unique integers \(q\) and \(r\) with \(0\leq r \lt b\) such that \(a = b\cdot q + r\text{.}\)

🔗

Proof.

The existence of \(q\) and \(r\) follows from Listing 5.1.1.6.

🔗

We now prove the uniqueness of \(q\) and \(r\text{.}\) Suppose that there are \(q_1\in\ZZ\) and \(q_2\in\ZZ\) and \(r_1\in\ZZ\) and \(r_2\in\ZZ\) such that

\(a=b\cdot q_1+r_1\) and \(0\le r_1\lt b\) and
🔗

🔗
\(a=b\cdot q_2+r_2\) and \(0\le r_2\lt b\text{.}\)
🔗

🔗

Then \(b\cdot q_1+r_1=b\cdot q_2+r_2\text{.}\) We need to show that \(q_1=q_2\) and \(r_1=r_2\text{.}\)

Case 1: \(r_1=r_2\) 🔗: If \(r_1=r_2\) then

\begin{align*} b\cdot q_1+r_1\amp =b\cdot q_2+r1 \amp \text{ subtract }r_1\\ b\cdot q_1\amp =b\cdot q_2 \amp \text{ divide by }b\\ q_1\amp =q_2 \end{align*}

🔗
Case 2: \(q_1=q_2\) 🔗: If \(q_1=q_2\) then \(bq_1=bq_2\text{.}\) Thus \(b\cdot q_1+r_1=b\cdot q_2+r2\) becomes \(b\cdot q_1+r_1=b\cdot q_1+r2\text{.}\) Subtracting \(b\cdot q_1\) from both sides yields \(r_1=r_2\text{.}\)
🔗
Case 3: \(r_1\ne r_2\) 🔗: We prove that this case cannot happen by contradiction.
🔗

Collecting the \(q_i\) on the left and the \(r_i\) on the right

\begin{equation*} b\cdot q_1+r_1=b\cdot q_2+r_2 \end{equation*}

becomes

\begin{equation*} b\cdot(q_1-q_2) = r_2-r_1. \end{equation*}

\begin{equation*} |b\cdot(q_1-q_2)| = |r_2-r_1|>0. \end{equation*}

Because \(r_1\ne r_2\) and \(r_2\lt b\) and \(r_1\lt b\) we have

\begin{equation*} 0\lt |r_2-r_1| \lt b. \end{equation*}

Because \(0\ne q_1-q_2\) and \(q_1\in\ZZ\) and \(q_2\in\ZZ\) we have

\begin{equation*} |b\cdot(q_1-q_2)|=b\cdot|q_1-q_2|\ge b \end{equation*}

which contradicts

\begin{equation*} |b\cdot(q_1-q_2)| = |r_2-r_1|\lt b. \end{equation*}

🔗

So we must have \(r_1=r_2\) and \(q_1=q_2\) which proves the uniqueness.

🔗

Listing 5.1.1.6. Naive division algorithm for \(a\in\NN_0\) and \(b\in\NN\)

🔗

def divmod_naive(a,b):	
  q=0	
  while a>b:
    a=a-b
    q=q+1
  return q,a

Theorem 5.1.1.7. Division algorithm for negative integers.

Let \(a\) be neagtive integer and \(d\) be integers with \(d \gt 0\text{.}\) There exists unique integers \(q\) and \(r\) with \(0\leq r \lt d\) such that \(a = dq + r\text{.}\)

🔗

Proof.

The existence of \(q\) and \(r\) follows from Listing 5.1.1.8.

🔗

The uniqueness follows as in the proof of Theorem 5.1.1.5.

🔗

Listing 5.1.1.8. Naive division algorithm for \(a\in\ZZ\) with \(a\lt 0\) and \(\in\NN\)

🔗

def divmod_negative(a,b):	
  q=0	
  while a <0:
    a=a+b
    q=q-1
  return q,a

Together Theorem 5.1.1.5 and Theorem 5.1.1.7 yield:

🔗

Theorem 5.1.1.9. Division algorithm.

Let \(a\) and \(d\) be integers with \(d \gt 0\text{.}\) There exists unique integers \(q\) and \(r\) with \(0\leq r \lt d\) such that \(a = dq + r\text{.}\)

🔗

Remark 5.1.1.10.

For \(d\in\NN\) and \(a\in\ZZ\) we have that \(d\mid a\) is equivalent to \(a\bmod d=0\text{.}\)

🔗

Remark 5.1.1.11.

Given \(a\) and \(d\text{,}\) we can compute \(q\) as the floor and get

\begin{equation*} q=a\div d=\floor{\frac{a}{d}}. \end{equation*}

After we have \(q\text{,}\) we can solve for \(r\) in the equation \(a = dq + r\) and get

\begin{equation*} r=a\bmod d=a-\floor{\frac{a}{d}}\cdot d.\text{.} \end{equation*}

🔗

Example 5.1.1.12. Division algorithm and floor.

Let’s see what the division algorithm says in a few examples.

🔗

First consider \(a = 253\) and \(d = 17\text{.}\) With a calculator we obtain \(253 / 17 \approx 14.88\text{.}\) Thus \(q = \floor{\frac{253}{17}} = 14\text{.}\) Then \(253 = 17 \cdot 14 + r\text{.}\) Solving for \(r\) gives \(r = 15\text{.}\)

🔗

Next consider \(a = -253\) and \(d = 17\text{.}\) By long division, we see \(-253/17 \approx -14.88\text{.}\) Thus \(q = \floor{\frac{-253}{17}} = -15\text{.}\) Then \(-253 = 17(-15) + r\text{.}\) Solving for \(r\) gives \(r = 2\text{.}\)

🔗

Definition 5.1.1.13.

Let \(a\) and \(d\) be integers, with \(d \gt 0\text{.}\) Let \(q\) and \(r\) be integers such that \(a = dq + r\text{,}\) with \(0 \leq r \lt d\text{.}\) We call \(d\) the divisor and we call \(a\) the dividend.

🔗

We call \(q\) the quotient, and denote it by \(q=a \div d\text{.}\)

🔗

We call \(r\) the remainder, and denote it \(t=a \bmod d\text{.}\)

🔗

Example 5.1.1.14. Quotients and remainders.

\(\phantom{-}17 \div 3 = 5\) and \(17 \bmod 3 = 2\) since \(17 = 5 \cdot 3 + 2\text{.}\)

🔗

\(-17 \div 3 = -6\) and \(-17 \bmod 3 = 1\) since \(17 = -6 \cdot 3 + 1\text{.}\)

🔗

Theorem 5.1.1.15.

Every integer is even or odd. No integer is both.

🔗

Proof.

Let \(n\) be an integer.

🔗

It follows from and that \(n\) is even if and only if \(n\bmod 2=0\) and from and that \(n\) is odd if and only if \(n\bmod 2=1\text{.}\)

🔗

Because the remainder from the division by \(2\) is either \(0\) or \(1\) but not both by we we have that integer is even or odd but not both.

🔗

While Listing 5.1.1.6 and Listing 5.1.1.8 are useful for proving Theorem 5.1.1.9 using repeated subtraction or addition to compute quotients and remainders when numbers are a bit larger takes a lot of subtractions or additions. Long division is much more efficient.

🔗

Example 5.1.1.16. Long division interactive.

🔗

In Python, the quotient and remainder can be computed as follows. There is also a function that returns both the quotient and remainder at once.

🔗

Listing 5.1.1.18.

🔗

# quotient	
q = a // d
# remainder
r = a % d
# or compute them both at the same time
q, r = divmod(a,d)

🔗

Prev Top Next