* Modular arithmetic* is a way of systematically
ignoring differences involving a multiple of an integer. If n is an
integer, two integers are equal mod n if they differ by a multiple of
n; it is as if multiples of n are "set equal to 0".

* Definition.* Let n, x, and y be integers. x is
* congruent to* y * mod* n if
. Notation:

* Remarks.* is equivalent
to the following statements:

(a) .

(b) for some .

(c) for some .

I'll often use any of these four statements as the definition of .

A lot of people like to write " " instead of " ". I don't think there's any harm in using an ordinary equal sign, since the " " makes the meaning clear. It's also a bit shorter to write.

* Example.* (* Examples of
congruences with numbers*) (a) Demonstrate that and .

(b) Express "x is even" and "x is odd" in terms of congruences.

(c) What does means in terms of divisibility?

(a)

(b) x is even if and only if and x is odd if and only if .

(c) if and only if . Thus, congruences provide a convenient notation for dealing with divisibility relations.

The following proposition says that you can work with modular equations in many of the ways that you work with ordinary equations.

* Proposition.* Let .

(a) If and , then

(b) If and , then

(c) If , then

* Proof.* Two ideas for these kinds of proofs:

1. You can often prove statements about congruences by reducing them to statements about divisibility.

2. You can often prove statements about divisibility by reducing them to (ordinary) equations.

(a) Suppose and .

means and means . By properties of divisibility,

Therefore, .

(b) Suppose and .

means , which means for some . means , which means for some . Thus, , , and hence

This gives , so , and hence .

(c) Suppose . This means that . By properties of divisibility,

Therefore, .

* Example.* (* Solving a
congruence*) Solve .

In this case, I'll solve the modular equation by adding or subtracting the same thing from both sides.

The solution is .

* Example.* Reduce to a number in the
range , *doing the
computation by hand*.

Note that

So

The next result says that congruence mod n is an *
equivalence relation*.

* Proposition.*

(a) (Reflexivity) for all .

(b) (Symmetry) Let . If , then .

(c) (Transitivity) Let . If and , then .

* Proof.* (a) If , then , so .

(b) If , then , so . Therefore, .

(c) Suppose and . means ; means . Therefore,

Hence, .

An equivalence relation on a set gives rise to a *
partition* of the set into equivalence classes. In the case of
congruence mod n, an equivalence class consists of integers congruent
to each other mod n.

* Definition.* (read "Z mod n") is the set of equivalence
classes under congruence mod n.

* Example.* (* Congruence classes
mod 3*) Find the equivalence classes of the relation congruence
mod 3 on the set of integers.

Relative to the equivalence relation of congruence mod 3 on , the integers break up into three *disjoint*
sets:

All the elements of a given set are congruent mod 3, and no element in one set is congruent mod 3 to an element of another. The sets divide up the integers like three puzzle pieces.

It's cumbersome to write and use equivalence classes as is, since
each equivalence class is a set (infinite, in this case). It's
customary to choose a * representative* from each
equivalence class and use the representatives to do arithmetic. I'll
choose

I'll abuse notation and write

is called the * cyclic
group of order 3*. The "cyclic" nature of can be visualized by arranging the integers in a
spiral, with each congruence class on a ray.

When you do arithmetic in , it is as if you count in a circle: 0, 1, 2, then back to 0 again.

You can form other cyclic groups in an analogous way. For example,

You can do arithmetic in by adding and
multiplying as usual, but * reducing the results mod
n*.

* Example.* (* Operation tables
for* ) Construct addition and
multiplication tables for .

For example, as integers . I divide 4 by the modulus 3 and get a remainder of 1. Hence, .

Likewise, in .

* Example.* (* Equations in*
) Find in , in , and -8 in .

-8 means the additive inverse of 8. The last statement is just another way of saying .

* Example.* (* Using modular
arithmetic in a divisibility proof*) Prove that if n is an
integer, then is not divisible by 5.

Every integer n is congruent to one of 0, 1, 2, 3, or 4 mod 5. Therefore, I have 5 cases. In each case, I want to show that is not divisible by 5 --- or to say it in terms of congruences, I want to show that .

I set and "substitute" the value into . This substitution is justified by the properties of congruences I discussed above.

For example, if , then

Likewise, . So

Essentially, I can plug into , then reduce the result mod 5 to one of 0, 1, 2, 3, or 4.

Continuing in this way, I get the following table:

In all five cases, . Therefore, is never divisible by 5.

I showed earlier how to use algebraic operations to solve simple modular equations. How would you solve something like this:

I'd like to divide both sides by 6, but I only know how to add and
multiply. I *can* subtract, but that's because I can add
additive inverses. Well, division is multiplication by the
multiplicative inverse; what is a multiplicative inverse mod 25?

* Definition.* Let . a and b are *
multiplicative inverses* if (or in ).

If a is the multiplicative inverse of b, you can write .

(You don't write " " unless you're in a number system like the rational numbers where fractions are in use.)

* Example.* (* Modular
multiplicative inverses*) (a) Prove that 6 and 2 are
multiplicative inverses mod 11.

(b) Show that 8 does not have a multiplicative inverse mod 12.

(a) .

(b) One tedious way is to take cases:

No number multiplied by 8 gives 1 mod 12.

I could try all the possibilities because the numbers were small. How would you do this kind of problem if the numbers were larger?

One approach is to simply appeal to the result following this example. However, I can also give a proof by contradiction.

Suppose that 8 has a multiplicative inverse mod 12. Let x be the multiplicative inverse. Then . Multiplying both sides by 3, I get

This is a contradiction, since 0 and 3 do not differ by a multiple of 12. Therefore, 8 does not have a multiplicative inverse mod 12.

* Proposition.* has a multiplicative inverse if and only if
.

* Proof.* Suppose has a multiplicative inverse, so

I can regard this as a statement in :

This means that and 1 *differ by* a
multiple of n:

Thus,

This is a linear combination of m and n which gives 1. Therefore, .

Conversely, suppose . I may find integers a and b such that

That is,

Now regarded as an equation in , this says

That is, m has multiplicative inverse a.

* Example.* (* Using the Extended
Euclidean algorithm to find modular inverses*) Find the
multiplicative inverse of 31 in .

Note that . Apply the Extended Euclidean Algorithm:

Thus,

In , and . The equation says . Thus, 47 is the multiplicative inverse of 31 in .

* Theorem.* If , then the following equation has a unique solution:

* Proof.* If , then a has a
multiplicative inverse in . Thus, in .

First, this means that is a solution, since

Second, if is another solution, then . Multiplying both sides by , I get

That is, . This means the solution is unique.

* Example.* (* Solving modular
equations using modular inverses*) Solve

There is a solution, since . I need to find a multiplicative inverse for 13 mod 15.

The Extended Euclidean Algorithm says that

Hence, , i.e. 7 is the multiplicative inverse of 13 mod 15.

Multiply the original equation by 7:

* Proposition.* Suppose

Then

* Proof.* I have

(Note that and , so and are actually integers.) Now divides , but

By Euclid's lemma, . Hence,

I can use the preceding result to solve some congruences when I can't immediately use modular inversion.

* Example.* Solve

Since , 12 doesn't have a multiplicative inverse mod 34. I'll use the preceding result. I "cancel" a factor of 6 from and 30, and divide the modulus 34 by :

Since the original congruence was mod 34, I must find all numbers in which satisfy . One is obviously 11. Adding 17, I find that also works. (Adding 17 again takes me out of the set .)

The solutions are and .

Copyright 2018 by Bruce Ikenaga