# 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. (read "a equals b mod m" or a is congruent to b mod m) if any of the following equivalent conditions hold:

(a) .

(b) .

(c) (or ) for some .

(d) (or ) for some .

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. Another way of saying this is: Mod m any multiple of m is 0.

Remark. Many people prefer to write " ". Since equality mod m is an equivalence relation, since " " is a little less writing than " ", and since there isn't much risk of confusion, I'll write " ".

Example.

(a) Reduce to a number in the range .

(b) Reduce to a number in the range .

(a) , because .

(b) , because .

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 .

Theorem. Suppose and . Then:

(a) .

(b) .

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

Proof. Suppose and .

(a) and , so by properties of divisibility,

This implies that .

(b) and imply that there are integers j and k such that

Multiplying these two equations, I obtain

Hence, , so .

Corollary. Suppose . Then:

(a) .

(b) .

Proof. Apply the theorem to the equations and .

Assume that the modulus m is a positive integer. By the Division Algorithm, every integer n can be written as

Reducing this equation mod m, I have , so

Since , I have . In other words, mod m every integer can be reduced to a number in . This set is called the standard residue system mod m, and answers to modular arithmetic problems will usually be simplified to a number in this range.

Example.

(a) What are the equivalence classes under the relation of congruence mod 3?

(a) 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 .)

(b) 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, but I would have gotten an equivalent table. The simplest thing is to use the numbers from the standard residue system mod 3.

Example. ( Reducing an expression mod n) Reduce to an element in the standard residue system .

, so

Example. Simplify to a number in the range .

Rather than deal with large "positive" numbers, I'll convert them to small "negative" numbers:

So

Example. ( A modular binomial theorem) Prove 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,

Example. Prove that if , then is not divisible by 5.

The phrase "not divisible by 5" leads one to think of doing things mod 5.

Every integer is equal to one of 0, 1, 2, 3, or 4 mod 5. Make a table:

Example. Give a counterexample to show that does not imply that , for .

For instance, , but (since ).

Example. Solve the congruence

The modular arithmetic properties allow me to solve this equation the way I would solve a linear equation, up to a point. I multiply out the left side, then get the x's on one side:

If this were an equation over the real numbers, you could divide both sides by 4 --- equivalently, multiply both sides by .

What would " " mean mod 7? This is the multiplicative inverse of 4, which we write as (in modular arithmetic you don't use fraction notation). This means: What number multiplied by 4 gives 1 mod 7?

Since there are only 7 numbers mod 7, I can do this by trial and error, multiplying 4 by 0, 1, ... until I get 1. I find that

So for this modular equation, I multiply both sides by 2:

You can see that finding multiplicative inverses mod n can be useful in solving congruences. Sometimes they can be found by more refined trial and error than simply trying all the numbers mod n.

Since multiples of n equal 0 mod n,

I can sometimes use this to find inverses mod n.

Example.

(a) Use trial and error to find .

(b) Use trial and error to find .

(c) Prove that 25 does not have a multiplicative inverse mod 30.

(a) I take multiples of 7 and add 1, stopping when I get a number which is divisible by 5:

Since , I have .

(b) I take multiples of 89 and add 1, stopping when I get a number which is divisible by 45:

Since , I have .

(c) Suppose that (so ). Then

This contradiction shows that there is no such x, so 25 does not have a multiplicative inverse mod 30.

The previous method still has its limitations, as you can see by trying to use it to find . And as you saw, some elements don't have multiplicative inverses mod n. The following theorem says which elements have multiplicative inverses, and how to find them if they exist.

Theorem. m has a multiplicative inverse mod n if and only if .

Proof. Suppose m has a multiplicative inverse mod n. This means that for some a. Then

Hence, .

Conversely, if , then

Reducing mod n, I get , which means that m has a multiplicative inverse mod n.

As the proof shows, you can find by applying the Extended Euclidean algorithm to a and n.

Example. ( Finding elements which have multiplicative inverses) Which elements of have multiplicative inverses mod 12?

The numbers in which are relatively prime to 12 and 1, 5, 7, and 11. Hence, 1, 5, 7, and 11 have multiplicative inverses mod 12.

Example. Find .

Apply the Extended Euclidean Algorithm to 61 and 47:

Write the linear combination, then reduce mod 61:

Hence, .

Proposition. If , then

Proof. Write

Then

(Notice that and are integers, since and .) Now divides the right side, but it's relatively prime to . Therefore, it must divide k:

Hence,

Therefore, .

Notice that you "divide the equality" by c, but you divide the modulus by .

Example. ( Solving a congruence with cancellation) Solve

By the previous result, if I "cancel" the factors of 6, I must divide the modulus by . This makes the modulus 19:

Now , so I can solve this congruence by multiplying by . Noting that , I see that I need to multiply by 10:

(If you didn't see that by trial, you'd use the Extended Euclidean algorithm as before.)

The original congruence was mod 38, so I want all solutions in the range . I have one: . To get others, I add multiples of 19 until I exceed 37. Thus, is the other solution.

All together, the solutions are and .

Example. ( A congruence with no solutions) Show that the following congruence has no solutions:

Suppose that x is a solution. Multiply the equation by 7:

This contradiction shows that the equation has no solutions.

These examples show that linear congruences may have solutions or may be unsolvable. We can understand better what is happening by relating them to linear Diophantine equations.

Contact information