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
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,
If a is a real number, then |a| denotes its absolute value: |a|=a if a ≥ 0, and |a|=−a if
a < 0.