Congruence Classes and Modular Arithmetic

The congruence class modulo of the integers is the set of integers

(See set builder notation)

For , the four congruence classes are given by:

A congruence class has more than one representation. From the example above,

We define to be the set of congruence classes:

and define two operations on :

There operations are well-defined. For example, in ,

For all integers and , with non-zero, the equation:

has a solution if and only if , where .

Moreover, when , there are solutions, given by

where is a particular solution

(See divisibility, GCD)

By comparing the proofs of the linear congurence theorem and Modular Arithmetic Theorem, we can see that to find solutions to the equation in , we should consider the linear Diophantine equation

Let be an integer with . The element has a multiplicative inverse if and only if .

Moreover, when , the multiplicative inverse is unique.

For all prime numbers and non-zero elements , the multiplicative inverse exists and is unique.

If possible, find the multiplicative inverse of in

Since , by corollary Inverses in , has no multiplicative inverse in

If possible, find the multiplicative inverse of in

Since , by corollary Inverses in , has a unique multiplicative inverse in .

To find the inverse, we consider the corresponding linear Diophantine equation .
Using the EEA, we obtain:

So . We can conclude that in

solve the following system of equations in

First, subtract times (2) from times (1) to obtain .
Since , we have the equation .
Since 11 is prime, and , by corollary Inverses in , the element has a multiplicative inverse in .
Multiplying both sides of the equation by , we obtain:

Subbing into equation 1 gives:

But has a multiplicative inverse in , and multiplying both sides of by , we obtain , and

To make sure this equation isn't extraneous, substitute the values back into equations (1) and (2) to make sure they work out.