Modular arithmetic

The congruence in number theory a relation between integers. We call two numbers congruent with respect to a module ( another number ) when through the module have the same remainder when divided. This is exactly the case if they differ by an integer multiple of the module. If the residues do not match, so you call the numbers incongruent with respect to the module.

For example, 5 is congruent modulo 11 3, as and, respectively. And -8 is congruent modulo 6 to 10, for providing division by 10 and 6, both the remaining 4 -8 It should be noted that the mathematical definition of the integer division is based on, after which the rest of the same sign as the divisor (in this case 6) gets so.

For the statement " and are congruent modulo " one uses the following notations:

• .

The importance of congruences based on the fact that it can be calculated approximately as with equations with them.

The theory of congruences was developed by Carl Friedrich Gauss in his published work in 1801 " Disquisitiones Arithmeticae ". The concept of congruence has been used by Christian Goldbach 1730 in letters to Leonhard Euler, but without the theoretical depth of Gauss. In contrast to Gaussian Goldbach used the icon and not. The Chinese mathematician Ch'in Chiu- Shao had known congruences and the associated theory, such as " Mathematical Treatise in Nine Chapters " is evident from his 1247 published book.

Formal definition

In number theory the congruence is attributed to a Teilbarkeitsaussage. Be it, and integers, that is, Elements.

Using mathematical notation, these two statements be written as follows:

Residue classes

The congruence is an equivalence relation. Thus, it has the following properties:

If we specify a module, as thereby the set of all numbers on so-called residue classes are distributed. In a residue class contains all numbers that are congruent to each other below the specified module, which therefore always have the same radical. The absolute value of the modulus is always equal to the number of cosets. For example, there are the two cosets of the even and odd numbers for the module 2. The residue classes of a module form a ring, called the residue class ring.

Calculation rules

Is a polynomial over the integers, the following applies

Even with congruences a shortening is possible. However, there are other reduction rules as usual rational or real numbers. If the module is not zero, is valid

It follows immediately that if the modulus is a prime number and this is not a divisor of, applies

For each divisor of follows that.

Are integers equal to zero and is their least common multiple, then applies

Potencies

Is a natural number, then:

If and are relatively prime, then apply according to the Euler

Where φ is the Euler function called. It follows also

A special case of this is the small Fermat's theorem, therefore, for all primes the congruence

Is satisfied.

Derived calculation rules

Solvability of linear congruences

A linear congruence of the form

Exactly then is solvable if the number of shares. In this case, the congruence has exactly solutions, and the solutions are mutually congruent modulo.

Also great for one can determine the solutions efficiently by the extended Euclidean algorithm to apply to and which calculates next two numbers and that express as a linear combination of and:

A solution is obtained by then, and the remaining solutions differ by a multiple of.

For example, if removable, is divided for the number, and there are solutions. The extended Euclidean algorithm delivers what the solution results. The solutions are congruent modulo. Thus, the solution set

A simultaneous congruence as

Is safe then solvable if and only if:

• For all is divisible by, that is, each congruence is solvable for yourself
• Which are pairwise relatively prime

The proof of the Chinese remainder theorem provides the solution method for such simultaneous congruences.

Relationship with the modulo function

If two numbers are congruent modulo a number that results from dividing by the same rest

Use the widespread especially in computer science modulo function, one can write this as:

Note that this is the usual in computer science modulo function only for positive and correct. Thus, the equation is actually equivalent to the congruence and for all, you have to by the

Use defined modulo function. ( Is the floor function. ) With this definition, for example.

Applications

Congruences and residue classes are often helpful when you need to perform calculations with very large numbers.

An important statement about congruences of prime numbers is the small Fermat's theorem or the Fermat primality test.