Modular Arithmetic

Congruence

Congruence Modulo:

In the previous section, we discussed the calculation of the remainder.

In this remainder world, two numbers are similar (not the same) when they give the same Remainder. For example, if we take A (mod c), we will get D as the remainder; similarly, when we take B (mod c), we will get D as the remainder. As in both cases, i.e., A and B, we get the identical remainder, we call them congruent.

Formally, we will represent or express it as:

This says that A is congruent to B modulo C.

We will discuss the meaning of congruence modulo by performing a thought experiment with the regular modulo operator.

Let's imagine we were calculating mod 5 for all of the integers:

Suppose we labelled 5 slices 0, 1, 2, 3, 4. Then, for each of the integers, we put it into a slice that matched the value of the integer mod 5.

Think of these slices as buckets, which hold a set of numbers. For example, 26 would go in the slice labelled 1, because

Above is a figure that shows some integers that we would find in each of the slices.

It would be useful to have a way of expressing that numbers belonged in the same slice. (Notice 26 is in the same slice as 1, 6, 11, 16, 21 in above example).

A common way of expressing that two values are in the same slice, is to say they are in the same equivalence class.

Kindly watch the video from 4:10 to 13:10.

Activity: Kindly change A and B's values and see which integers are congruent.

NEXT: Next we will learn addition in this remainder world.

Reference: Learn more at Khan Academy

Page updated

Google Sites

Report abuse