Page 261 - Discrete Mathematics and Its Applications

240 4 / Number Theory and Cryptography

EXAMPLE 4 What are the quotient and remainder when −11 is divided by 3?

Solution: We have

−11 = 3(−4) + 1.

Hence, the quotient when −11 is divided by 3 is −4 =−11 div 3, and the remainder is
1 =−11 mod 3.
Note that the remainder cannot be negative. Consequently, the remainder is not −2, even
though

−11 = 3(−3) − 2,

because r =−2 does not satisfy 0 ≤ r< 3. ▲

Note that the integer a is divisible by the integer d if and only if the remainder is zero
when a is divided by d.

Remark: A programming language may have one, or possibly two, operators for modular arith-
metic, denoted by mod (in BASIC, Maple, Mathematica, EXCEL, and SQL), % (in C, C++, Java,
and Python), rem (in Ada and Lisp), or something else. Be careful when using them, because
for a< 0, some of these operators return a − m a/m instead of a mod m = a − m a/m (as
shown in Exercise 18). Also, unlike a mod m, some of these operators are defined when m< 0,
and even when m = 0.

Modular Arithmetic

In some situations we care only about the remainder of an integer when it is divided by some
specified positive integer. For instance, when we ask what time it will be (on a 24-hour clock) 50
hours from now, we care only about the remainder when 50 plus the current hour is divided by 24.
Because we are often interested only in remainders, we have special notations for them. We have
already introduced the notation a mod m to represent the remainder when an integer a is divided
by the positive integer m. We now introduce a different, but related, notation that indicates that
two integers have the same remainder when they are divided by the positive integer m.

DEFINITION 3 If a and b are integers and m is a positive integer, then a is congruent to b modulo m if
m divides a − b. We use the notation a ≡ b (mod m) to indicate that a is congruent to
b modulo m. We say that a ≡ b (mod m)isa congruence and that m is its modulus (plural
moduli). If a and b are not congruent modulo m, we write a ≡ b (mod m).

Although both notations a ≡ b (mod m) and a mod m = b include “mod,” they represent
fundamentally different concepts. The first represents a relation on the set of integers, whereas
the second represents a function. However, the relation a ≡ b (mod m) and the mod m function
are closely related, as described in Theorem 3.