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.”

Here is another numerical example to help you understand the

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.

Start Free Trial

No credit card required