Congruence (number theory)

This article deals with congruence in terms of division with remainder. For congruence in terms of area, see congruent number .

In number theory, congruence is a relationship between whole numbers . They call two integers and congruent modulo (= another number), when used in the division by both the same rest have. This is precisely the case when they differ by an integral multiple of . However, if the remainders do not match, the numbers are called incongruent modulo . Every congruence modulo an integer is a congruence relation on the ring of integers. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m}$

Examples

example 1

For example, 5 is congruent 11 modulo 3, da and , the two remainders (2) are therefore the same, or da , the difference is therefore an integer multiple (2) of 3. ${\displaystyle 5:3=1{\text{ Rest }}2}$ ${\displaystyle 11:3=3{\text{ Rest }}2}$ ${\displaystyle 11-5=6=2\cdot 3}$

Example 2

In contrast, 5 is incongruent 11 modulo 4, da and ; the two remains are not the same here. ${\displaystyle 5:4=1{\text{ Rest }}1}$ ${\displaystyle 11:4=2{\text{ Rest }}3}$

Example 3

And −8 is congruent to 10 modulo 6, because when dividing by 6, both 10 and −8 produce the remainder 4. Note that the mathematical definition of the integer division is based, according to which the remainder has the same sign as the divisor (here 6) receives, so . ${\displaystyle -8:6=-2{\text{ Rest }}4}$

Notation

The following notations are used for the statement " and are congruent modulo ": ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle m}$

• ${\displaystyle a\equiv b\mod m}$
• ${\displaystyle a\equiv b\mod m\mathbb {Z} }$
• ${\displaystyle a\equiv b{\pmod {m}}}$
• ${\displaystyle a\equiv b\quad (m)}$
• ${\displaystyle a\equiv _{m}b}$

These spellings can be used as a short form of the statement (equivalent to the above statement) "remainder of division of through is equal to remainder of division of through ", ie of ${\displaystyle a}$ ${\displaystyle m}$ ${\displaystyle b}$ ${\displaystyle m}$

${\displaystyle (a{\bmod {m}})=(b{\bmod {m}})}$,

(where in the last-mentioned equation is the mathematical modulo function that determines the remainder of an integer division, in this case the remainder of or ; with the mathematical modulo function, the result, i.e. the remainder, always has the same sign as ). ${\displaystyle \operatorname {mod} }$ ${\displaystyle {\tfrac {a}{m}}}$ ${\displaystyle {\tfrac {b}{m}}}$ ${\displaystyle m}$

history

The theory of congruences was developed by Carl Friedrich Gauß in his work " Disquisitiones Arithmeticae " published in 1801 . The term congruence was used by Christian Goldbach as early as 1730 in letters to Leonhard Euler , but without the theoretical depth of Gauss. In contrast to Gauss, Goldbach used the symbol and not . The Chinese mathematician Qin Jiushao (秦九韶) was also familiar with congruences and the accompanying theory, as can be seen in his book “ Shushu Jiuzhang ” ( Chinese 數 書 九章  /  数 书 九章 , Pinyin Shùshū Jiǔzhāng  - “Mathematical treatise in nine chapters” published in 1247 ) “). ${\displaystyle \mp }$ ${\displaystyle \equiv }$ 

Formal definition

In number theory, congruence is reduced to a divisibility statement . In addition , and integers, i.e. H. Elements from . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle m\neq 0}$ ${\displaystyle \mathbb {Z} }$

• Two numbers and are called congruent modulo if the difference divides. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle a-b}$
• Two numbers and are called incongruent modulo if the difference does not divide. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle a-b}$

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

• ${\displaystyle a\equiv b{\pmod {m}}}$

${\displaystyle \Leftrightarrow m\mid (a-b)}$

${\displaystyle \Leftrightarrow \exists k\in \mathbb {Z} :a=km+b}$

• ${\displaystyle a\not \equiv b{\pmod {m}}}$

${\displaystyle \Leftrightarrow m\nmid (a-b)}$

${\displaystyle \Leftrightarrow \forall k\in \mathbb {Z} :a\neq km+b}$

Residual classes

A congruence relation is a special equivalence relation . So it has the following properties:

Reflexivity

${\displaystyle a\equiv a{\pmod {m}}}$ for all ${\displaystyle a\in \mathbb {Z} }$

symmetry

${\displaystyle a\equiv b{\pmod {m}}\Rightarrow b\equiv a{\pmod {m}}}$ for all ${\displaystyle a,b\in \mathbb {Z} }$

Transitivity

${\displaystyle a\equiv b{\pmod {m}}}$and for everyone ${\displaystyle b\equiv c{\pmod {m}}\Rightarrow a\equiv c{\pmod {m}}}$ ${\displaystyle a,b,c\in \mathbb {Z} }$

The equivalence classes of the congruence relation are called residual classes . If one also wants to specify, one speaks of residual classes . A remainder class that contains the element is often referred to as. ${\displaystyle m}$ ${\displaystyle ({\text{mod }}m)}$ ${\displaystyle a}$ ${\displaystyle [a]}$

Like every equivalence relation, a congruence relation defines a partition of its support set: The remainder classes of two elements are either equal or disjoint , the former if and only if the elements are congruent:

${\displaystyle [a]=[b]\quad \iff \quad a\equiv b{\pmod {m}}\quad \iff \quad a\in [b]\quad \iff \quad b\in [a]}$.

Equipped with the links induced by the residue classes form a ring , the so-called residue class ring . He is designated for with . ${\displaystyle \mathbb {Z} (+,\cdot )}$ ${\displaystyle m}$ ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$

comment

• Since a division by has not yet occurred, one can allow for the formal definition (in the previous section) as well as for the equivalence relation (in this section) . ${\displaystyle m}$ ${\displaystyle m=0}$
• Since there are no real zero divisors in the ring , the relation degenerates to the trivial case, to equality: ${\displaystyle \mathbb {Z} }$ ${\displaystyle \equiv ({\text{mod }}0)}$

${\displaystyle a\equiv b{\pmod {0}}\quad \Rightarrow \quad a=b}$       for everyone . ${\displaystyle a,b\in \mathbb {Z} }$

• The unitary ring of the characteristic is isomorphic to . This property is also needed in the event . Then is . This ring is not viewed as a residual class ring in the narrower sense. ${\displaystyle m}$ ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$ ${\displaystyle m=0}$ ${\displaystyle \mathbb {Z} /m\mathbb {Z} =\mathbb {Z} /0\mathbb {Z} =\mathbb {Z} }$
• The interesting cases are the cases that can be taken as the standard . ${\displaystyle m\neq 0}$
• The remainder class ring is the null ring , which consists of only one element. ${\displaystyle \mathbb {Z} /1\mathbb {Z} }$

Is not trivial, so then are in a residue class all the numbers that have the same remainder when dividing by exhibit. Then the absolute value of , that is , corresponds to the number of remainder classes. For example, there are two remainder classes of even and odd numbers for 2 . ${\displaystyle m}$ ${\displaystyle m\neq 0}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle |m|}$

Calculation rules

Below are , , , , and whole numbers. Be there , and . Then the following calculation rules apply: ${\displaystyle a}$ ${\displaystyle a'}$ ${\displaystyle b}$ ${\displaystyle b'}$ ${\displaystyle c}$ ${\displaystyle m}$ ${\displaystyle m\neq 0}$ ${\displaystyle a\equiv a'{\pmod {m}}}$ ${\displaystyle b\equiv b'{\pmod {m}}}$

${\displaystyle ca\equiv ca'{\pmod {m}}}$

${\displaystyle a+b\equiv a'+b'{\pmod {m}}}$

${\displaystyle a-b\equiv a'-b'{\pmod {m}}}$

${\displaystyle ab\equiv a'b'{\pmod {m}}}$

If there is a polynomial over the whole numbers, then: ${\displaystyle f\in \mathbb {Z} [X]}$

${\displaystyle f(a)\equiv f(a'){\pmod {m}}}$

Shortening is also possible if there are congruences . However, other abbreviation rules apply to those used for rational or real numbers ( ... greatest common factor ): ${\displaystyle \operatorname {ggT} }$

${\displaystyle ca\equiv cb{\pmod {m}}\Leftrightarrow a\equiv b{\pmod {\frac {m}{\operatorname {ggT} (c,m)}}}}$

It follows immediately that - if a prime number and this is not a divisor of - the following applies: ${\displaystyle m}$ ${\displaystyle p}$ ${\displaystyle c}$

${\displaystyle ca\equiv cb{\pmod {p}}\Leftrightarrow a\equiv b{\pmod {p}}}$

If is a composite number or a factor of , only: ${\displaystyle m}$ ${\displaystyle c}$

${\displaystyle ca\equiv cb{\pmod {m}}\Leftarrow a\equiv b{\pmod {m}}}$

For every divisor of it follows that . ${\displaystyle d}$ ${\displaystyle m}$ ${\displaystyle a\equiv b{\pmod {m}}}$ ${\displaystyle a\equiv b{\pmod {d}}}$

If integers are not equal to zero and their lowest common multiple , then: ${\displaystyle m_{1},m_{2},\dotsc ,m_{k}}$ ${\displaystyle m}$

${\displaystyle a\equiv a'{\pmod {m_{\kappa }}}}$ for all ${\displaystyle \kappa =1,2,\dotsc ,k\quad \Leftrightarrow \quad a\equiv a'{\pmod {m}}}$

Potencies

If it is a natural number , then: ${\displaystyle n\in \mathbb {N} _{0}}$

${\displaystyle a^{n}\equiv (a')^{n}{\pmod {m}}}$

Are and coprime , then according to Euler's theorem ${\displaystyle a}$ ${\displaystyle m}$

${\displaystyle a^{\varphi (m)}\equiv 1{\pmod {m}}}$,

wherein the Euler's φ function referred to. It also follows from this ${\displaystyle \varphi (m)}$

${\displaystyle a^{n}\equiv a^{n'}{\pmod {m}}}$if . ${\displaystyle n\equiv n'{\pmod {\varphi (m)}}}$

A special case of this is the little Fermat's theorem , hence congruence for all prime numbers ${\displaystyle p}$

${\displaystyle a^{p}\equiv a{\pmod {p}}}$

is satisfied.

Derived calculation rules

1. The following applies to: ${\displaystyle t\neq 0}$ ${\displaystyle t\cdot a\equiv t\cdot b{\pmod {|t|\cdot m}}}$
2. If is a factor of , then: ${\displaystyle k}$ ${\displaystyle m}$ ${\displaystyle a\equiv b{\pmod {k}}}$
3. For every odd number : ${\displaystyle a}$ ${\displaystyle a^{2}\equiv 1{\pmod {8}}}$
4. Either or or applies to every integer . ${\displaystyle a^{3}\equiv 0{\pmod {9}}}$ ${\displaystyle a^{3}\equiv 1{\pmod {9}}}$ ${\displaystyle a^{3}\equiv 8{\pmod {9}}}$
5. For every whole number : ${\displaystyle a}$ ${\displaystyle a^{3}\equiv a{\pmod {6}}}$
6. Either or or applies to every integer . ${\displaystyle a^{3}\equiv 0{\pmod {7}}}$ ${\displaystyle a^{3}\equiv 1{\pmod {7}}}$ ${\displaystyle a^{3}\equiv 6{\pmod {7}}}$
7. Either or applies to every integer . ${\displaystyle a^{4}\equiv 0{\pmod {5}}}$ ${\displaystyle a^{4}\equiv 1{\pmod {5}}}$
8. If both a square number and a cube number (e.g. ) then either or or or applies . ${\displaystyle a}$ ${\displaystyle a=64}$ ${\displaystyle a\equiv 0{\pmod {36}}}$ ${\displaystyle a\equiv 1{\pmod {36}}}$ ${\displaystyle a\equiv 9{\pmod {36}}}$ ${\displaystyle a\equiv 28{\pmod {36}}}$
9. Let be a prime number with . Then: ${\displaystyle p}$ ${\displaystyle n<p<2n}$
   ${\displaystyle {2n \choose n}\equiv 0{\pmod {p}}}$
10. Let be an odd integer. Further be . Then: ${\displaystyle a}$ ${\displaystyle n>0}$ ${\displaystyle a^{2^{n}}\equiv 1{\pmod {2^{n+2}}}}$
11. Be . Furthermore, let and be prime twins . Then: ${\displaystyle p>3}$ ${\displaystyle p}$ ${\displaystyle q=p+2}$ ${\displaystyle p\cdot q\equiv -1{\pmod {9}}}$

Solvability of linear congruences

Linear congruence

A linear congruence of shape

${\displaystyle ax\equiv c{\pmod {m}}}$

is solvable in if and only if the number divides. In this case the congruence has exactly solutions in , and the solutions are congruent to each other modulo . ${\displaystyle x}$ ${\displaystyle g=\operatorname {ggT} (a,m)}$ ${\displaystyle c}$ ${\displaystyle g}$ ${\displaystyle \{0,1,\dotsc ,m-1\}}$ ${\displaystyle {\tfrac {m}{g}}}$

The solutions can also be efficiently determined for large ones by applying the extended Euclidean algorithm to and , which also calculates two numbers and , which express as a linear combination of and : ${\displaystyle m}$ ${\displaystyle a}$ ${\displaystyle m}$ ${\displaystyle g}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle g}$ ${\displaystyle a}$ ${\displaystyle m}$

${\displaystyle g=\operatorname {ggT} (a,m)=s\cdot a+t\cdot m}$

One then receives a solution with , and the other solutions differ from by a multiple of . ${\displaystyle \textstyle x_{1}={\frac {s\cdot c}{g}}}$ ${\displaystyle x_{1}}$ ${\displaystyle {\tfrac {m}{g}}}$

Example: is solvable, because divides the number , and there are solutions in the area . The extended Euclidean algorithm gives what the solution is. The solutions are congruent modulo . The solution set for is thus . ${\displaystyle 4x\equiv 10{\pmod {18}}}$ ${\displaystyle \operatorname {ggT} (4,18)=2}$ ${\displaystyle 10}$ ${\displaystyle 2}$ ${\displaystyle 0\leq x<18}$ ${\displaystyle 2=-4\cdot 4+1\cdot 18}$ ${\displaystyle \textstyle x_{1}={\frac {-4\cdot 10}{2}}=-20}$ ${\displaystyle \textstyle {\frac {18}{2}}=9}$ ${\displaystyle x}$ ${\displaystyle \{\cdots ,-20,-11,-2,7,16,25,\cdots \}}$

Simultaneous congruence

A simultaneous congruence like

${\displaystyle \qquad a_{1}x\equiv c_{1}{\pmod {m_{1}}}}$

${\displaystyle \qquad a_{2}x\equiv c_{2}{\pmod {m_{2}}}}$

${\displaystyle \qquad a_{3}x\equiv c_{3}{\pmod {m_{3}}}}$

can certainly be solved if:

• for all is through divisible d. H. every congruence is solvable for itself, and ${\displaystyle i}$ ${\displaystyle c_{i}}$ ${\displaystyle g_{i}=\operatorname {ggT} (a_{i},m_{i})}$
• which are pairwise mutually prime . ${\displaystyle {\tfrac {m_{i}}{g_{i}}}}$

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

Relationship to the modulo function

General

With , generally applies: ${\displaystyle a,b,m\in \mathbb {Z} }$ ${\displaystyle m\neq 0}$

${\displaystyle a\equiv b{\pmod {m}}\quad \Leftrightarrow \quad (a{\bmod {m}})=(b{\bmod {m}})\quad \Leftrightarrow \quad (a-b){\bmod {m}}=0}$

programming

Are two numbers and congruent modulo a number , resulting from the division by the same rest . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle m}$ ${\displaystyle m}$

With the help of the "symmetrical variant" of the modulo function , which is particularly widespread in computer science and is often referred to in programming languages with the modulo operators mod or %, this can be written as follows:

(a mod m) = (b mod m) or. (a % m) = (b % m)

Note that with the symmetrical modulo function common in computer science, this is only true for positive and positive . So that the equation is actually for all and equivalent to congruence, one has to through ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$

${\displaystyle (a{\bmod {m}}):=a-\left\lfloor {\frac {a}{m}}\right\rfloor \cdot m}$

Use a defined mathematical modulo function , the result of which always has the same sign as ( is the Gaussian bracket ). With this definition, for example . ${\displaystyle \operatorname {mod} }$ ${\displaystyle m}$ ${\displaystyle \lfloor \cdot \rfloor }$ ${\displaystyle (-1){\bmod {7}}=6}$

Applications

Congruences or remainder classes are often helpful when you have to perform calculations with very large numbers.

An important statement about congruence of prime numbers is Fermat's little theorem or Fermat's prime number test .

See also

• Chinese remainder
• Linear congruence
• Polynomial congruence
• Simultaneous congruence
• Module (mathematics)

Web links

• Christian Spannagel : Congruences and residual classes . Lecture series, 2012.

swell

1. ↑ Peter Bundschuh : Introduction to Number Theory. 5th edition. Springer, Berlin 2002, ISBN 3-540-43579-4
2. ^ Song Y. Yan: Number theory for computing. 2nd Edition. Springer, 2002, ISBN 3-540-43072-5 , pp. 111-117