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 often 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 both 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 a useful tool 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 set of all integers of the form a + k m, where k is any integer. This is called the congruence class or residue class of a modulo m.

Each residue class modulo m has one integer in the range from 0 to |m| − 1. These integers are called representatives of their residue classes. It is usually easier to work with these representatives rather than the whole sets of integers.

Main article: Covering system

Given the Euler's totient function φ(m), a reduced residue system modulo m is a set of φ(m) integers that are relatively prime to m and do not share the same remainder when divided by m. For example, the set {5, 15} is a reduced residue system modulo 4.

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 forms a special mathematical structure called the ring of integers modulo m. This idea helps us understand number theory better. For example, on a 12-hour clock, the numbers wrap around after 12, which is a simple example of modular arithmetic.

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

Main article: Applications

Applications

Modular arithmetic is a key part of 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 12 notes in a scale. It is also important for secure communication methods and for solving complex math problems on computers.

Computational complexity

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

Some problems in modular arithmetic, such as finding certain types of solutions, are very hard to solve and are used to create secure codes and protections for information. These problems are so challenging that they help keep data safe online. Solving more complex modular equations, however, can be one of the toughest problems in computer science.

Main article: Linear congruence theorem

Montgomery reduction

Discrete logarithm

Quadratic congruence

Integer factorization

Cryptographic algorithms

Encryption

NP-intermediate

NP-complete