Modular arithmetic

In mathematics, modular arithmetic is a special way of working with numbers that makes them "wrap around" after reaching a certain value. This value is called the modulus.

Imagine a 12-hour clock: if it is 7 o'clock now, after 8 hours it will show 3 o'clock. Normally, 7 + 8 equals 15, but on the clock, 15 "wraps around" to 3. We say that 15 is the same as 3 when we are using modulo 12, and we write this as 15 ≡ 3 (mod 12).

This idea was formalized by the famous mathematician Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, which was published in 1801. Modular arithmetic is very useful in number theory, which is the study of the properties of numbers.

Another example is waiting 8 hours twice, which is the same as waiting 16 hours. On a 12-hour clock, 16 hours later is the same as waiting 4 hours, so we can write 2 × 8 ≡ 4 (mod 12). After exactly 12 hours, the clock returns to the starting point, which means 12 acts like 0 in modular arithmetic, written as 12 ≡ 0 (mod 12).

Congruence

When we talk about modular arithmetic, we use the idea of congruence. This means two numbers are the same in a special way when we look at them under a certain "modulus."

For example, with a modulus of 12 (like on a clock), the numbers 3 and 15 are congruent because they show the same hour.

In math terms, we say two numbers a and b are congruent modulo m if their difference (a − b) is a multiple of m. We write this as a ≡ b (mod m). This idea works well with addition, subtraction, and multiplication. If a ≡ b (mod m), then adding the same number to both, multiplying both by the same number, or even adding or multiplying parts together will still keep them congruent modulo m.

This concept helps us solve problems where numbers "wrap around" after reaching a certain value, making modular arithmetic useful in many areas of math.

Congruence classes

The congruence relation is an equivalence relation. The equivalence class modulo m of an integer a is the group of all integers that look the same when divided by m. This is called the congruence class or residue class of a modulo m.

Each residue class modulo m has one integer between 0 and |m| − 1. These integers are called representatives of their residue classes. It is usually easier to work with these representatives.

Main article: Covering system

Given the Euler's totient function φ(m), a reduced residue system modulo m is a group of φ(m) integers that are relatively prime to m and do not share the same remainder when divided by m.

Covering systems are another type of residue system that may use residues with different moduli.

Integers modulo m

The set of all numbers modulo m is a special way to work with numbers. This idea helps us understand number theory better. For example, on a 12-hour clock, the numbers start again after 12. This is a simple example of modular arithmetic.

In this system, we use numbers from 0 up to m − 1. We can add, subtract, and multiply these numbers. The results also start again after reaching m. This wrapping around makes modular arithmetic useful in many areas, such as cryptography and computer science.

Main article: Applications

Applications

Modular arithmetic is important in many areas of math and science. It helps in number theory, group theory, ring theory, and abstract algebra. It is also used in computer science, cryptography, and even in music and chemistry.

One common use is in checking codes, like ISBNs for books and IBANs for bank accounts, to catch mistakes. In music, modular arithmetic helps organize the notes in a scale. It is also important for secure communication and for solving complex math problems on computers.

Computational complexity

Modular arithmetic is used in many places, so it’s important to know how hard it is to solve problems with it. For example, a set of simple modular equations can be solved quickly using methods like those in regular math. There are also special ways to make basic calculations, like multiplying big numbers, faster and easier.

Some problems in modular arithmetic, such as finding certain answers, are very hard to solve. These hard problems help create safe codes and protections for information. Solving more complex modular equations is one of the toughest jobs in computer science.

Main article: Linear congruence theorem

Montgomery reduction

Discrete logarithm

Quadratic congruence

Integer factorization

Cryptographic algorithms

Encryption

NP-intermediate

NP-complete