Page 262 - Discrete Mathematics and Its Applications

4.1 Divisibility and Modular Arithmetic 241

THEOREM 3 Let a and b be integers, and let m be a positive integer. Then a ≡ b (mod m) if and only
if a mod m = b mod m.

The proof of Theorem 3 is left as Exercises 15 and 16. Recall that a mod m and b mod m are
the remainders when a and b are divided by m, respectively. Consequently, Theorem 3 also says
that a ≡ b (mod m) if and only if a and b have the same remainder when divided by m.

EXAMPLE 5 Determine whether 17 is congruent to 5 modulo 6 and whether 24 and 14 are congruent modulo 6.

Solution: Because 6 divides 17 − 5 = 12, we see that 17 ≡ 5 (mod 6). However, because
24 − 14 = 10 is not divisible by 6, we see that 24 ≡ 14 (mod 6). ▲

The great German mathematician Karl Friedrich Gauss developed the concept of congru-
ences at the end of the eighteenth century. The notion of congruences has played an important
role in the development of number theory.
Theorem 4 provides a useful way to work with congruences.

THEOREM 4 Let m be a positive integer. The integers a and b are congruent modulo m if and only if there
is an integer k such that a = b + km.

Proof: If a ≡ b(mod m), by the definition of congruence (Definition 3), we know that
m | (a − b). This means that there is an integer k such that a − b = km, so that a = b + km.
Conversely, if there is an integer k such that a = b + km, then km = a − b. Hence, m divides
a − b, so that a ≡ b(mod m).

The set of all integers congruent to an integer a modulo m is called the congruence class
of a modulo m. In Chapter 9 we will show that there are m pairwise disjoint equivalence classes
modulo m and that the union of these equivalence classes is the set of integers.
Theorem 5 shows that additions and multiplications preserve congruences.

KARL FRIEDRICH GAUSS (1777–1855) Karl Friedrich Gauss, the son of a bricklayer, was a child prodigy.
He demonstrated his potential at the age of 10, when he quickly solved a problem assigned by a teacher to keep
the class busy. The teacher asked the students to find the sum of the first 100 positive integers. Gauss realized
that this sum could be found by forming 50 pairs, each with the sum 101: 1 + 100, 2 + 99,..., 50 + 51.
This brilliance attracted the sponsorship of patrons, including Duke Ferdinand of Brunswick, who made it
possible for Gauss to attend Caroline College and the University of Göttingen. While a student, he invented
the method of least squares, which is used to estimate the most likely value of a variable from experimental
results. In 1796 Gauss made a fundamental discovery in geometry, advancing a subject that had not advanced
since ancient times. He showed that a 17-sided regular polygon could be drawn using just a ruler and compass.
In 1799 Gauss presented the first rigorous proof of the fundamental theorem of algebra, which states that a polynomial of
degree n has exactly n roots (counting multiplicities). Gauss achieved worldwide fame when he successfully calculated the orbit of
the first asteroid discovered, Ceres, using scanty data.
Gauss was called the Prince of Mathematics by his contemporary mathematicians. Although Gauss is noted for his many
discoveries in geometry, algebra, analysis, astronomy, and physics, he had a special interest in number theory, which can be seen
from his statement “Mathematics is the queen of the sciences, and the theory of numbers is the queen of mathematics.” Gauss laid
the foundations for modern number theory with the publication of his book Disquisitiones Arithmeticae in 1801.