Remainder Classes in Discrete Mathematics

---

---

Remainder classes are ways of grouping numbers based on their remainders when divided by a certain number. Remainder classes have a wide range of applications, especially in domains that require working with integers or finite sets.

In this chapter, we will see the basics of remainder classes, explain how they work, and and explore a few examples to understand the concept better.

What are Remainder Classes?

The concept behind remainder classes is simple. When we divide the numbers by another number, each result may keep a remainder. The numbers that give the same remainder will be classified into the same class. In other words, all the numbers that leave a remainder will be in same class.

When we talk about remainder classes in mathematics, we use the phrase "modulo." Modulo refers to the divisor we are working on. For example, in modulo 5, we are only interested with remainders when numbers are divided by 5. So, we would have remainder classes like 0, 1, 2, 3, and 4.

Example

In modulo 3, the remainder classes would be 0, 1, and 2. This is because any number divided by 3 will give one of these remainders.

These remainder classes are useful in creating a kind of "short-hand" for working with numbers. It is simplifying operations by letting us group numbers based on remainders.

Understanding the Modulo Operation and Remainder Classes

The modulo operation is written as "mod," this is important to remainder classes. When we say a ≡ b (mod n), we are saying that a and b are in the same remainder class modulo n. This means they have the same remainder when divided by n.

Example

Consider we take modulo 4. 8 and 12 both leave a remainder of 0 when divided by 4, so they are in the same remainder class 0.

Similarly, 5 and 9 both leave a remainder of 1. When it is divided by 4, they are in the remainder class 1 (mod 4).

By categorizing the numbers into these classes, we can see patterns and simplify calculations.

Defining Remainder Classes Modulo n

In discrete mathematics, we define remainder classes using a divisor n. For any integer n, there are n possible remainder classes. These are labeled from 0 up to n 1. Here each class contains numbers that share the same remainder when divided by n.

Example

If we are working with modulo 5, there are five possible remainder classes −

• Class 0 − All numbers divisible by 5, like 0, 5, 10, 15, and so on.
• Class 1 − Numbers that leave a remainder of 1, like 1, 6, 11, 16, etc.
• Class 2 − Numbers that leave a remainder of 2, such as 2, 7, 12, 17, and so forth.
• Class 3 − Numbers with a remainder of 3, like 3, 8, 13, 18, etc.
• Class 4 − Numbers with a remainder of 4, such as 4, 9, 14, 19, and so on.

Each remainder class forms a set of numbers that follow a predictable pattern.

Another example, where we are organizing a set of numbers into remainder classes under modulo 4:

• Class 0 (mod 4) − 0, 4, 8, 12, ...
• Class 1 (mod 4) − 1, 5, 9, 13, ...
• Class 2 (mod 4) − 2, 6, 10, 14, ...
• Class 3 (mod 4) − 3, 7, 11, 15, ...

By grouping numbers like this can help in various mathematical problems. Basically, where simplifying calculations or finding patterns is needed.

How Remainder Classes Form a Partition

One of the important things about remainder classes is that they split the set of all integers into distinct groups or "partitions." Each number falls into exactly one remainder class for a given modulo. It ensures that all possible integers are covered without overlap between classes.

This partitioning is useful when we do not need to check each integer individually in certain problems. We can just check one representative from each remainder class.

Example

Using modulo 3, we have three remainder classes: 0, 1, and 2. Any integer we choose will fall into one of these classes. For example −

• Class 0 (mod 3) − ..., -9, -6, -3, 0, 3, 6, 9, ...
• Class 1 (mod 3) − ..., -8, -5, -2, 1, 4, 7, 10, ...
• Class 2 (mod 3) − ..., -7, -4, -1, 2, 5, 8, 11, ...

So by picking one representative from each class, we have covered all possible numbers under modulo 3.

Practical Applications of Remainder Classes

As we have understood this is an interesting and important concept. It has several applications in various fields. For instance, the remainder classes are used in cryptography, coding theory, and data storage. We need efficient use of numbers and patterns.

Let us see some applications to see how remainder classes work.

• Application in Coding Theory − In coding, the remainder classes can help detect and correct errors. If we know that a code number should fall into a particular remainder class. If any deviation from this class can indicate an error.
• Application in Cryptography − Remainder classes are also used in a major role in cryptography. Mainly when we are working on modular arithmetic-based encryption algorithms. By assigning each letter or data point to a remainder class, encryption systems can create unique codes which challenging to decode without the correct key.
• Application in Calendar Cycles − It is used in calendars. For instance, if today is Monday and we want to know what day it will be in 10 days, we can use modulo 7 (since there are 7 days in a week). So dividing 10 by 7 gives a remainder of 3, so in 10 days. It will be Thursday, three days after Monday.

Finding Remainder Classes

Let us see a few examples to get how remainder classes work and how we can determine which class a number belongs to.

Example 1: Modulo 5

Question − Find the remainder class of 28 in modulo 5.

When we divide 28 by 5, the remainder is 3. So, 28 belongs to the remainder class 3 (mod 5).

Example 2: Modulo 6

Question − Find the remainder class of -14 in modulo 6.

Dividing -14 by 6 gives a remainder of 4. So, -14 falls into remainder class 4 (mod 6).

Example 3: Modulo 4

Question − Classify numbers from -5 to 5 in remainder classes under modulo 4.

By grouping the numbers into remainder classes, we can make calculations easier and get the patterns.

• Class 0 − -4, 0, 4
• Class 1 − -3, 1, 5
• Class 2 − -2, 2
• Class 3 − -1, 3

Conclusion

Remainder classes is a key concept in discrete mathematics that helps in grouping numbers based on their remainders. In this chapter, we explained the basics of remainder classes and looked into how they are defined for any integer n. We also covered how they create partitions of integers.

Using practical examples, we understood how remainder classes work in modular arithmetic and how they are applied in areas like coding and cryptography.