If two integers, a and b, are in the same congruence class,

then they have the same remainder when written using our defining relationship.

By subtracting it, we get the very useful result that two integers are congruent

mod-N if their difference is an integer multiple of the modulus.

We indicate the congruents of two numbers with the congruent sign

which looks like a three-barred equal sign.

And with the modulus written to the right in parenthesis, essentially is a note,

indicating what module or world these two integers happen to be congruent in.

This is like saying that the two numbers are equal, but congruent and

equal are not the same thing.

Again, 11 and 12 are not equal, but they are congruent modulo 13.

Like the divisibility expression, this is a predicate claim and not an operation.

There's no mathematical operator here, so no operation gets performed.

If we want to actually reduce a number to its class representative,

we use the mod operator.

Here mod is a binary operator, and

it has two operands, the dividend on the left and the divisor on the right.

Sometimes we use the percent sign because this is the remainder operator supported

in most high level programming languages.

Here, we do use the equal sign because the expression on the left

evaluates to the exact same value as the expression on the right.

Also, note that this is just an integer expression,

there's no mod N world involved.

When working in a mod N world, one approach is to simply ignore the modulus

until the end, and then reduce the final result by the modulus.

However, when working with problems of cryptographic interest,

our modulus alone may have hundreds or even thousands of digits.

And this approach could easily result in our needing to work with numbers having

millions of digits.

While possible in principle, using what are called big number libraries, the speed

associated with such computations is prohibitively slow in practice.

So we need to find a way to speed things up,

while still getting the same final answer.

One of the simplest and most powerful techniques is simply to

reduce the computation by the modulus after every step of the computation.

For addition and subtraction, our defining relationship requires that the residue of

the sum of two integers is simply the sum of the residues.

Similarly, for multiplication, our defining relationship requires that

the residue of the product of two integers is simply the product of the residues.

One thing to keep in mind is that even if we perform reductions along the way, we

still need to perform a final reduction at the end because any operation, other than

mod itself, has the potential to yield a value other than the class representative.