maths.free › Abstract Algebra › 2. The Integers › The Division Algorithm

The Division Algorithm

An application of the Principle of Well-Ordering that we will use often is the division algorithm. Theorem: Division Algorithm Let a and b be integers, with b \gt 0.

The Division Algorithm

An application of the Principle of Well-Ordering that we will use often is the division algorithm.

Theorem: Division Algorithm

Let \(a\) and \(b\) be integers, with \(b \gt 0\). Then there exist unique integers \(q\) and \(r\) such that \[\begin{aligned}\end{aligned}\] where \(0 \leq r \lt b\).

Proof

This is a perfect example of the existence-and-uniqueness type of proof. We must first prove that the numbers \(q\) and \(r\) actually exist. Then we must show that if \(q'\) and \(r'\) are two other such numbers, then \(q = q'\) and \(r = r'\).

Let \[\begin{aligned}\end{aligned}\]. If \(0 \in S\), then \(b\) divides \(a\), and we can let \(q = a/b\) and \(r = 0\). If \(0 \notin S\), we can use the Well-Ordering Principle. We must first show that \(S\) is nonempty. If \(a \gt 0\), then \(a - b \cdot 0 \in S\). If \(a \lt 0\), then \(a - b(2a) = a(1 - 2b) \in S\). In either case \(S \neq \emptyset\). By the Well-Ordering Principle, \(S\) must have a smallest member, say \(r = a - bq\). Therefore, \(a = bq + r\), \(r \geq 0\). We now show that \(r \lt b\). Suppose that \(r \gt b\). Then \[\begin{aligned}\end{aligned}\]. In this case we would have \(a - b(q + 1)\) in the set \(S\). But then \(a - b(q + 1) \lt a - bq\), which would contradict the fact that \(r = a - bq\) is the smallest member of \(S\). So \(r \leq b\). Since \(0 \notin S\), \(r \neq b\) and so \(r \lt b\).

Uniqueness of \(q\) and \(r\). Suppose there exist integers \(r\), \(r'\), \(q\), and \(q'\) such that \[\begin{aligned}\end{aligned}\]. Then \(bq + r = bq' + r'\). Assume that \(r' \geq r\). From the last equation we have \(b(q - q') = r' - r\); therefore, \(b\) must divide \(r' - r\) and \(0 \leq r'- r \leq r' \lt b\). This is possible only if \(r' - r = 0\). Hence, \(r = r'\) and \(q = q'\).

Let \(a\) and \(b\) be integers. If \(b = ak\) for some integer \(k\), we write \(a \mid b\). An integer \(d\) is called a common divisor of \(a\) and \(b\) if \(d \mid a\) and \(d \mid b\). The greatest common divisor of integers \(a\) and \(b\) is a positive integer \(d\) such that \(d\) is a common divisor of \(a\) and \(b\) and if \(d'\) is any other common divisor of \(a\) and \(b\), then \(d' \mid d\). \(a \mid b\) \(a\) divides \(b\) \(\gcd(a, b)\) greatest common divisor of \(a\) and \(b\) We write \(d = \gcd(a, b)\); for example, \(\gcd( 24, 36) = 12\) and \(\gcd(120, 102) = 6\). We say that two integers \(a\) and \(b\) are relatively prime if \(\gcd( a, b ) = 1\).

Theorem

Let \(a\) and \(b\) be nonzero integers. Then there exist integers \(r\) and \(s\) such that \[\begin{aligned}\end{aligned}\]. Furthermore, the greatest common divisor of \(a\) and \(b\) is unique.

Proof

Let \[\begin{aligned}\end{aligned}\]. Clearly, the set \(S\) is nonempty; hence, by the Well-Ordering Principle \(S\) must have a smallest member, say \(d = ar + bs\). We claim that \(d = \gcd( a, b)\). Write \(a = dq + r'\) where \(0 \leq r' \lt d\). If \(r' \gt 0\), then \[\begin{aligned}r'& = a - dq \\ & = a - (ar + bs)q \\ & = a - arq - bsq \\ & = a( 1 - rq ) + b( -sq )\end{aligned}\], which is in \(S\). But this would contradict the fact that \(d\) is the smallest member of \(S\). Hence, \(r' = 0\) and \(d\) divides \(a\). A similar argument shows that \(d\) divides \(b\). Therefore, \(d\) is a common divisor of \(a\) and \(b\).

Suppose that \(d'\) is another common divisor of \(a\) and \(b\), and we want to show that \(d' \mid d\). If we let \(a = d'h\) and \(b = d'k\), then \[\begin{aligned}\end{aligned}\]. So \(d'\) must divide \(d\). Hence, \(d\) must be the unique greatest common divisor of \(a\) and \(b\).

The Euclidean Algorithm

Among other things, allows us to compute the greatest common divisor of two integers.

Example

Let us compute the greatest common divisor of \(945\) and \(2415\). First observe that \[\begin{aligned}2415 & = 945 \cdot 2 + 525 \\ 945 & = 525 \cdot 1 + 420 \\ 525 & = 420 \cdot 1 + 105 \\ 420 & = 105 \cdot 4 + 0\end{aligned}\]. Reversing our steps, \(105\) divides \(420\), \(105\) divides \(525\), \(105\) divides \(945\), and \(105\) divides \(2415\). Hence, \(105\) divides both \(945\) and \(2415\). If \(d\) were another common divisor of \(945\) and \(2415\), then \(d\) would also have to divide \(105\). Therefore, \(\gcd( 945, 2415 ) = 105\).

If we work backward through the above sequence of equations, we can also obtain numbers \(r\) and \(s\) such that \(945 r + 2415 s = 105\). Observe that \[\begin{aligned}105 & = 525 + (-1) \cdot 420 \\ & = 525 + (-1) \cdot [945 + (-1) \cdot 525] \\ & = 2 \cdot 525 + (-1) \cdot 945 \\ & = 2 \cdot [2415 + (-2) \cdot 945] + (-1) \cdot 945 \\ & = 2 \cdot 2415 + (-5) \cdot 945\end{aligned}\]. So \(r = -5\) and \(s= 2\). Notice that \(r\) and \(s\) are not unique, since \(r = 41\) and \(s = -16\) would also work.

To compute \(\gcd(a,b) = d\), we are using repeated divisions to obtain a decreasing sequence of positive integers \(r_1 \gt r_2 \gt \cdots \gt r_n = d\); that is, \[\begin{aligned}b & = a q_1 + r_1 \\ a & = r_1 q_2 + r_2 \\ r_1 & = r_2 q_3 + r_3 \\ & \aatavdots{=} \\ r_{n - 2} & = r_{n - 1} q_{n} + r_{n} \\ r_{n - 1} & = r_n q_{n + 1}\end{aligned}\]. To find \(r\) and \(s\) such that \(ar + bs = d\), we begin with this last equation and substitute results obtained from the previous equations: \[\begin{aligned}d & = r_n \\ & = r_{n - 2} - r_{n - 1} q_n \\ & = r_{n - 2} - q_n( r_{n - 3} - q_{n - 1} r_{n - 2} ) \\ & = -q_n r_{n - 3} + ( 1+ q_n q_{n-1} ) r_{n - 2} \\ & \aatavdots{=} \\ & = ra + sb\end{aligned}\]. The algorithm that we have just used to find the greatest common divisor \(d\) of two integers \(a\) and \(b\) and to write \(d\) as the linear combination of \(a\) and \(b\) is known as the Euclidean algorithm.

Prime Numbers

Let \(p\) be an integer such that \(p \gt 1\). We say that \(p\) is a prime number, or simply \(p\) is prime, if the only positive numbers that divide \(p\) are \(1\) and \(p\) itself. An integer \(n \gt 1\) that is not prime is said to be composite.

Condensed — the full section is in Judson, Abstract Algebra: Theory and Applications.

Historical Note

Prime numbers were first studied by the ancient Greeks. Two important results from antiquity are Euclid's proof that an infinite number of primes exist and the Sieve of Eratosthenes, a method of computing all of the prime numbers less than a fixed positive integer \(n\). One problem in number theory is to find a function \(f\) such that \(f(n)\) is prime for each integer \(n\). Pierre Fermat (1601?1665) conjectured that \(2^{2^n} + 1\) was prime for all \(n\), but later it was shown by Leonhard Euler (17071783) that \[\begin{aligned}\end{aligned}\] is a composite number. One of the many unproven conjectures about prime numbers is Goldbach's Conjecture. In a letter to Euler in 1742, Christian Goldbach stated the conjecture that every even integer with the exception of \(2\) seemed to be the sum of two primes: \(4 = 2 + 2\), \(6 = 3 + 3\), \(8 =3 + 5\), \(\ldots\). Although the conjecture has been verified for the numbers up through \(4 \times 10^{18}\), it has yet to be proven in general. Since prime numbers play an important role in public key cryptography, there is currently a great deal of interest in determining whether or not a large number is prime.

Sage's original purpose was to support research in number theory, so it is perfect for the types of computations with the integers that we have in this chapter.

Symbols used here

a \mid b,\ \gcd(a,b)

divides, greatest common divisor
b is a multiple of a; the largest number dividing both.

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

imaginary unit
i² = −1.

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

\neq

not equal
The two sides are different.

\mathbb{N},\ \mathbb{Z},\ \mathbb{Q},\ \mathbb{R},\ \mathbb{C}

number sets
Naturals, integers, rationals, reals, complex numbers.

\blacksquare\ \text{or}\ \square

end of proof (halmos)
Marks the point where the statement has been established.

a \equiv b \pmod n

congruent modulo n
n divides a − b; a and b have the same remainder.

(G, \cdot),\ e,\ g^{-1}

group, identity, inverse
A set with an operation; the do-nothing element; the element that undoes g.

G \cong H,\ G / N

isomorphic, quotient group
Same structure; the group of cosets of a normal subgroup N.

\mathbb{Z}/n\mathbb{Z},\ \mathbb{Z}_n

integers modulo n
The remainders 0…n−1 with clock arithmetic.

\operatorname{Hom}(A, B),\ f \circ g

arrows from A to B, composition
The set of morphisms; do g then f.

Questions people ask

What is a group, in plain words?

A set with one operation that is associative, has an identity, and lets every element be undone. Symmetries of any object form a group — that is where the idea came from.

What is the difference between a ring and a field?

A ring has addition and multiplication that behave like the integers (you cannot always divide); a field is a ring where every non-zero element has a reciprocal, like the rationals or the reals.

Provo timen.

Parts of this page are adapted from Judson, Abstract Algebra: Theory and Applications (GFDL 1.3). Condensed and re-explained here; errors are ours.

Më shumë në Abstract Algebra

Groups Subgroups, cosets and Lagrange's theorem Cyclic groups and permutation groups Homomorphisms, normal subgroups and quotient groups Rings and fields Galois theory: why the quintic has no formula