## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required MODULAR ARITHMETIC 33
Congruences
The symbol “%” is used by computer scientists, but mathematicians
ﬁnd it more convenient to study these concepts with a binary rela-
tion
2
called congruence, which is similar to equality. We deﬁne two
numbers as congruent modulo n if they have the same remainder
upon division by n. For example, we will call 23 and 45 congruent
modulo 11, because each leaves the remainder of 1 when divided by
11. Computer scientists would write this as 23%11 = 45%11. The
notation invented by Gauss to express this is
23 45 (mod 11). (4.1)
DEFINITION: We write a b (mod n) (read as a is
congruent to b modulo n”) if a%n = b%n. Equivalently, we
write a b (mod n)ifa b is a multiple of n. The number n
here is the modulus of the congruence.
EXERCISE: Show that the two deﬁnitions really are
equivalent. In other words, show that if a%n = b%n,then
a b is a multiple of n, and also show that if a b is a
multiple of n,thena%n = b%n.
The symbol can be used in most of the ways that the = symbol
is used. If a b (mod n)andb c (mod n), then a c (mod n);
this is the analogue for congruences of Euclid’s famous axiom,
“Things equal to the same thing are equal to each other.”
notation: 100 23 (mod 11) because both leave a remainder of 1
when divided by 11. From this and the congruence (4.1), we can
conclude that 100 45 (mod 11) without having to check again
that both leave the same remainder when divided by 11.
But we can also deal with unknowns: For instance, if x y
(mod 11) then we can see that x + 2 y + 13 (mod 11),
3
and this
2
A binary relation is a relation between two things of the same kind, in this case whole
numbers.
3
It is because 2 13 (mod 11); this is like adding equals to equals. 34 CHAPTER 4
congruence remains true whatever x and y are. However, we cannot
actually divide either side of the congruence by 11 to see what the
remainders are, because we do not know what x and y actually are.
Negative numbers can be included in the game. We will always
use a positive remainder (or 0), even if we are dividing into a
negative number. So, for example, (23)%11 = 10 because 11 goes
into 23 just 3 times, leaving a remainder of 10. In other words,
23 =−3 · 11 + 10.
What are all the positive numbers satisfying x 5(mod7)?
They are 5, 12, 19, 26, 33, 40, ... (just keep adding 7). They make
up what is called an “arithmetic progression.”
We need to pause here and deﬁne integer, prime number,and
composite number. We will be using these concepts all the time,
starting in the next paragraph.
DEFINITION: An integer is a whole number—positive,
negative, or zero. A prime number is a positive integer greater
than 1 that has no positive divisors except itself and 1.
A composite number is a positive integer greater than 1 that
is not prime. We will also refer to a negative number as prime
(respectively, composite) if its absolute value
4
is prime
(respectively, composite).
The ﬁrst few primes are 2, 3, 5, 7, 11, 13, 17, 19, and 23. There
are inﬁnitely many prime numbers. Some composite numbers are
4, 52 and 1000.
A famous theorem of the nineteenth-century mathematician
Lejeune Dirichlet says that an arithmetic progression, such as 5,
12, 19, 26, 33, 40, ...contains an inﬁnite number of prime numbers,
as long as there is no common divisor greater than 1 of all the
numbers in it. (For example, the arithmetic progression 2, 6, 10,
14, ...cannot contain inﬁnitely many prime numbers because all of
the numbers in the progression have a common divisor of 2.)
It may have occurred to you that we left negative numbers out
of the arithmetic progression. If so, you are right. Besides 5, 12,
4
If a is a real number, then |a| denotes its absolute value: |a|=a if a 0, and |a|=−a if
a < 0.

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required