# Congruences and Modular Arithmetic

• a is congruent to b mod n means that . Notation: .
• Congruence mod n is an equivalence relation. Hence, congruences have many of the same properties as ordinary equations.
• Congruences provide a convenient shorthand for divisibility relations.

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

Write to mean 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.

Example. and .

Proposition. Congruence mod m is an equivalence relation:

(a) ( Reflexivity) for all a.

(b) ( Symmetry) If , then .

(c) ( Transitivity) If and , then .

Proof. I'll prove transitivity by way of example. Suppose and . Then there are integers j and k such that

This implies that .

Example. Consider congruence mod 3. There are 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 .)

When you're doing things mod 3, it is if there were only 3 numbers. I'll grab one number from each of the classes to represent the classes; for simplicity, I'll use 0, 2, and 1.

Here is an addition table for the classes in terms of these representatives:

Here's an example: , because as integers, and 3's congruence class is represented by 0. This is the table for addition mod 3.

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 least nonnegative system of residues mod n, and it is the set of representatives I'll usually use.

(Sometimes I'll get sloppy and call it the least positive system of residues, even though it includes 0.)

Proposition. Suppose . Then

Proof.I'll prove (part of) the first congruence as an example. Suppose . Then for some k, so

But this implies that .

Example. Solve the congruence

First, reduce all the coefficients mod 3:

Next, add 1 to both sides, using the fact that :

Finally, multiply both sides by 2, using the fact that :

That is, any number in the set will solve the original congruence.

Remark. Notice that I accomplished division by 2 (in solving by multiplying by 2. The reason this works is that, mod 3, 2 is its own multiplicative inverse.

Recall that two numbers x and y are multiplicative inverses if and . For example, in the rational numbers, and are multiplicative inverses. {\it Division by a number is defined to be multiplication by its multiplicative inverse.} Thus, division by 3 means multiplication by .

In the integers, only 1 and -1 have multiplicative inverses. When you perform a "division" in --- such as dividing by 2 to get --- you are actually factoring and using the Zero Divisor Property:

(I used the Zero Divisor Property in making the third step: Since , must be 0.)

In doing modular arithmetic, however, many numbers may have multiplicative inverses. In these cases, you can perform division by multiplying by the multiplicative inverse.

Here is a multiplication table mod 3, using the standard residue system :

You can construct similar tables for other moduli. For example, 2 and 3 are multiplicative inverses mod 5, because . So if you want to "divide" by 3 mod 5, you multiply by 2 instead.

This doesn't always work. For example, consider

2 does not have a multiplicative inverse mod 6; that is, there is no k such that . You can check by trial that the solutions to the equation above are and --- just look at for .

Proposition. Suppose and . Then

Note that you can use the second property and induction to show that if , then

Proof. Suppose and . Then and , so by properties of divisibility,

This implies that .

To prove the second equation, note that and imply that there are integers j and k such that

Therefore,

Multiplying these two equations, I obtain

Hence, , so .

Example. What is the least positive residue of ?

, so

Example. 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,