Integers and Divisibility

This section includes some basic topics in number theory such as integers, divisibility, greatest common divisor, and integers.

The Division Algorithm

Let \(a\) and \(b\) (\(≥ 1\)) be integers. Then there exist unique integers \(q\) and \(r\) such that

\[a = bq + r\]

Where \(0 ≤ r < b\).

The integer \(q\) is called the quotient of \(a\) and \(b\) on dividing \(a\) by \(b\); the integer \(r\) is called the remainder of \(a\) and \(b\) on dividing \(a\) by \(b\).

Greatest Common Divisor

A nonzero integer \(d\) is said to be a common divisor of integers \(a\) and \(b\) if \(d | a\) and \(d | b\).

The largest nonzero integer \(d\) is said to be the greatest common divisor of integers \(a\) and \(b\) denoted by \(\text{gcd} (a, b)\), if \(d|a\) and \(d|b\).

Example

\(1\), \(3\), \(5\), and \(15\) divides both \(30\) and \(45\). The greatest common divisor of \(30\) and \(45\) is \(\text{gcd} (30, 45) = 15\).

Example

\(1\), \(2\), \(3\), \(6\), \(9\), and \(18\) divides both \(54\) and \(90\). The greatest common divisor of \(54\) and \(90\) is \(\text{gcd} (54, 90) = 18\).

Example

\(15\) and \(22\) has no common divisor other than \(1\), so that \(\text{gcd} (15, 22) = 1\).

Eucledian Algorithm for Finding the GCD

Consider two positive integers \(a\) and \(b\). By the division algorithm, there exist integers \(q_1\) and \(r_1\) such that

\[a = q_1b + r_1, 0 ≤ r_1 < b.\]

Now consider \(b\) and \(r_1\). Suppose \(r_1 \neq 0\). Then by the division algorithm, there exist integers \(q_2\) and \(r_2\) such that

\[b = q_2 r_1 + r_2, 0 \le r_2 < r_1.\]

Next consider \(r_1\) and \(r_2\). Suppose \(r_2 \neq 0\). Then by the division algorithm, there exist integers \(q_3\) and \(r_3\) such that

\[r_1 = q_3 r_2 + r_3, 0 \le r_3 < r_2.\]

We continue this process. Then we have

\[\begin{split}\begin{aligned} &\phantom{\text{If } r_1 \neq 0,} & a &= q_1b + r_1, & 0 &\le r_1 < b \\ &\text{If } r_1 \neq 0, & b &= q_2r_1 + r_2, & 0 &\le r_2 < r_1 \\ &\text{If } r_2 \neq 0, & r_1 &= q_3r_2 + r_3, & 0 &\le r_3 < r_2 \\ &\text{If } r_3 \neq 0, & r_2 &= q_4r_3 + r_4, & 0 &\le r_4 < r_3 \\ & & &\vdots & & \end{aligned}\end{split}\]

The remainder \(r_1, r_2, r_3, ...\) form the following decreasing sequence of nonnegative integers:

\[b > r_1 > r_2 > r_3 > ... \ge 0\]

Because \(b\) is a fixed positive integer, we must encounter the remainder \(0\) after a finite number of steps. Therefore, the process terminates after some steps.

Example

Consider the integers \(448\) and \(196\).

By repeated application of the division algorithm, we get

\(448 = 2 \times 196 + 56\)

\(196 = 3 \times 56 + 28\)

\(56 = 2 \times 28 + 0\)

The gcd is the last nonzero remainder. Thus, the \(\text{gcd} (196, 448) = 28\).

Least Common Multiple

The least common multiple of \(a\) and \(b\), denoted by \(\text{lcm} (a, b)\), is the smallest positive integer that is both divisible by \(a\) and \(b\).

Example

The least common multiple of \(18\) and \(20\) is \(\text{lcm} (18, 20) = 180\).

Solution.

\(18 = 2 \times 3^2\) and \(20 = 2^2 \times 5\)

The least common multiple of \(18\) and \(20\) is \(2^2 \times 3^2 \times 5 = 180\).