Modular Arithmetic

Definiton. Let a, b, and m be integers. a is congruent to b mod m if ; that is, if

Notation: means that a is congruent to b mod m. m is called the modulus of the congruence; I will almost always work with positive moduli.

Note that if and only if . Thus, modular arithmetic gives you another way of dealing with divisibility relations.

For example:

because .

because .

Proposition. Congruence mod m is an equivalence relation:

(a) ( Reflexivity) for all a.

(b) ( Symmetry) If , then .

(c) ( Transitivity) If and , then .

Proof. Since , it follows that .

Suppose . Then , so . Hence, .

Suppose and . Then there are integers j and k such that

This implies that .

Example. (a) List the elements of the equivalence classes relative to congruence mod 3.

(b) Using 0, 1, and 2 to represent these equivalence classes, construct addition and multiplication tables mod 3.

(a) The equivalence classes are the 3 congruence classes:

Each integer belongs to exactly one of these classes. Two integers in a given class are congruent mod 3.

(If you know some group theory, you probably recognize this as constructing from .)

(b)

For example, , because as integers, and the congruence class of 3 is represented by 0. Likewise, as integers, and the congruence class of 4 is represented by 1.

I could have chosen different representatives for the classes --- say 3, -4, and 4. A choice of representatives, one from each class, is called a complete system of residues mod 3. But working mod 3 it's natural to use the numbers 0, 1, and 2 as representatives --- and in general, if I'm working mod n, the obvious choice of representatives is the set . This set is called the standard residue system mod n, and it is the set of representatives I'll usually use. Thus, the standard residue system mod 6 is .

Theorem. Suppose and . Then:

(a) and .

(b) .

Proof. I'll prove the first congruence as an example. Suppose and . Then and for some , so

This implies that .

Example. Solve the congruence

There are no "fractions" mod 11. I want to divide by 3, and to do this I need to multiply by the multiplicative inverse of 3. So I need a number k such that . A systematic way of finding such a number is to use the Extended Euclidean algorithm. In this case, I just use trial and error. Obviously, and won't work, so I'll start at :

Thus, I need to multiply the equation by 4:

Definition. x and y are multiplicative inverses mod n if .

Notation: or . Do not use fractions.

Example. (a) Find .

(b) Prove that 6 does not have a multiplicative inverse mod 8.

(a) , so .

(b) Suppose . Then

This contradiction shows that 6 does not have a multiplicative inverse mod 8.

Example. Reduce to a number in .

Example. Reduce to a number in .

, so

Example. Show that if p is prime, then

By the Binomial Theorem,

A typical coefficient is divisible by p for . So going mod p, the only terms that remain are and .

For example

The result is not true if the modulus is not prime. For example,

Contact information