Residual class ring

This article is about residue class rings of integers modulo a fixed positive integer. For more general residue class rings, see factor ring .

The residual class ring is shown graphically. More detailed explanation by clicking on the picture in its description. ${\displaystyle \mathbb {Z} /60\mathbb {Z} }$

In mathematics , a remainder class ring modulo a positive integer is an abstraction of the classification of integers in terms of their remainder when divided by . ${\displaystyle n}$ ${\displaystyle n}$

This article deals with the algebraic definition and more abstract properties of residue class rings. For a simpler and more understandable introduction to the calculation rules, see the article Congruence (Number Theory) .

definition

Is a natural number, then integers with the same balance on be division by so-called residue classes modulo summarized. So two whole numbers are in the same remainder class if their difference is divisible by . The residue classes, together with the addition and multiplication explained below the residue class ring modulo n, of with , , or is referred to (read "Z modulo n"). Also can form the residue class ring: Each integer then forms its own residue class because the only integer is, for which there is an integer with are: why is through divisible. ${\displaystyle n\geq 1}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle \mathbb {Z} /(n)}$ ${\displaystyle \mathbb {Z} /n}$ ${\displaystyle \mathbb {Z} _{n}}$ ${\displaystyle n=0}$ ${\displaystyle a}$ ${\displaystyle 0}$ ${\displaystyle z}$ ${\displaystyle t}$ ${\displaystyle z=t\cdot 0}$ ${\displaystyle a-a=0}$ ${\displaystyle 0}$

The addition and multiplication of residue classes is carried out by addition and multiplication of any elements of these classes (in general, these elements are as representative or agent hereinafter) and subsequent radical formation of the result. If one denotes the remainder class of with , then one defines: ${\displaystyle a}$ ${\displaystyle [a]}$

${\displaystyle [a]+[b]:=[a+b]}$

${\displaystyle [a]\cdot [b]:=[a\cdot b]}$

The fact that these links of the remainder class ring are well defined is due to the following property of the remainder classes.

Are whole numbers with ${\displaystyle a_{1},\ b_{1},\ a_{2},\ b_{2}}$

${\displaystyle [a_{1}]=[b_{1}]}$

${\displaystyle [a_{2}]=[b_{2}]}$, then:

${\displaystyle [a_{1}+a_{2}]=[b_{1}+b_{2}]}$

${\displaystyle [a_{1}\cdot a_{2}]=[b_{1}\cdot b_{2}]}$

The links are thus defined independently of the representative of the remainder class.

Spellings and conventions

The notation can be confused with the designation for the ring of whole p -adic numbers to a prime number . If the notation for the remainder class ring is preferred, the -adic numbers are denoted by. The notation for the residual class rings, from which the construction of the ring in question can be read precisely as a general factor ring , is more complicated, but clearer. The spelling is rarer and also unfavorable because of the risk of confusion with . ${\displaystyle \mathbb {Z} _{n}}$ ${\displaystyle \mathbb {Z} _{p}}$ ${\displaystyle p}$ ${\displaystyle \mathbb {Z} _{n}}$ ${\displaystyle p}$ ${\displaystyle \mathbb {Z} _{p}^{\land }}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle \mathbb {Z} /n}$ ${\displaystyle \textstyle {{\frac {1}{n}}\mathbb {Z} =\left\{{\frac {k}{n}}\colon k\in \mathbb {Z} \right\}}}$

To avoid the annoying notation for the equivalence classes, simply leave out the square brackets. Each equivalence class thus has an infinite number of names; for example, with the agreed spelling and in . If you value a unique name for the finite number of elements of the remainder class ring, you select a canonical representative from each remainder class and identify the remainder class with this: ${\displaystyle n=0}$ ${\displaystyle n-1=-1}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$

According to this convention, the remainder class ring consists of the numbers . Through the congruences ${\displaystyle (\mathbb {Z} _{n},+,\cdot )}$ ${\displaystyle 0,1,\dotsc ,n-1}$

${\displaystyle (a+b)\mod n}$

${\displaystyle (a\ \cdot \ b)\mod n}$

in the ring of integers we get results which, according to our convention, we can immediately interpret as results in . Every chain of arithmetic operations in this remainder class ring (e.g. the evaluation of a polynomial at the point with ) can take place as an evaluation in the whole numbers with a final modulo reduction; however, the intermediate results can already be subjected to a modular reduction at any (or all) points. ${\displaystyle \mathbb {Z} }$ ${\displaystyle \mathbb {Z} _{n}}$ ${\displaystyle p\in \mathbb {Z} _{n}[X]}$ ${\displaystyle X=k}$ ${\displaystyle k\in \mathbb {Z} _{n}}$

If the number is a power of two, the system of representatives symmetrized around zero is often chosen. This corresponds to a binary representation of the numbers in which the most significant bit is interpreted as a sign . ${\displaystyle n=2^{k}}$ ${\displaystyle \textstyle {\left\{-{\tfrac {n}{2}},\dotsc ,-1,0,1,\dotsc ,{\tfrac {n}{2}}-1\right\}}}$

properties

For every natural number there is a commutative ring with one . The zero element is the remainder class and the one element is the remainder class . ${\displaystyle n\geq 0}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle n\mathbb {Z} }$ ${\displaystyle 1+n\mathbb {Z} }$

If a prime number , then the remainder class ring is a finite field , the remainder class field modulo , and is denoted by (from the English "field" for field). Inverse with respect to the multiplication can then be calculated unambiguously using the extended Euclidean algorithm . ${\displaystyle p}$ ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ ${\displaystyle p}$ ${\displaystyle \mathbb {F} _{p}}$

If, on the other hand, is not a prime number, then the remainder class ring is modulo no field , since the remainder class of every real divisor of is a zero divisor that has no inverse with respect to the multiplication . ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

A remainder class with is called prime remainder class modulo . The group of prime remainder classes modulo is called prime remainder class group modulo and is symbolized with . It is the unit group of the ring and has elements, where is Euler's φ function . ${\displaystyle a+n\mathbb {Z} }$ ${\displaystyle \operatorname {ggT} (a,n)=1}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle \varphi (n)}$ ${\displaystyle \varphi }$

Examples

Illustration on the face of the watch

The calculation with residual classes can be illustrated using the dial of an analog clock. The hours are numbered from 1 to 12, with hour 12 being considered hour 0.

If you start at hour 0 and add one hour each, you get each of the twelve hours on the dial in sequence. You add any two hours to each other by starting at the first given hour and counting down the second hour clockwise: To determine, you start at hour 4 and count five hours further, you end up at hour 9. If you now calculate , so count Five hours further from hour 9, you end up at hour 2, so it is in this system. How does this result come about? If you simply add the hourly values, you get 14; and “2 o'clock” corresponds to “2 o'clock” on the twelve-hour dial, so here it is . The result of an addition is therefore the normal sum, possibly minus a twelve. This corresponds to the remainder when dividing by 12. This type of addition is called “addition modulo 12”. You can see here that adding the twelve does not change a number for every hour . This explains why the 12th hour is referred to here as hour 0. ${\displaystyle 4+5}$ ${\displaystyle 9+5}$ ${\displaystyle 9+5=2}$ ${\displaystyle 14=2}$ ${\displaystyle 12+x=x}$ ${\displaystyle x}$

The multiplication is traced back to the addition: To determine, for example, one forms the sum and lands at the 12th hour. The product delivers "4:00 PM", and that is identical to "4:00 PM"; modulo 12 is . ${\displaystyle 4\cdot 3}$ ${\displaystyle 3+3+3+3}$ ${\displaystyle 4\cdot 4}$ ${\displaystyle 4\cdot 4=4}$

The twelve hourly values, together with the rules for addition and multiplication, are written as . ${\displaystyle (\mathbb {Z} /12\mathbb {Z} ,+,\cdot )}$

The calculation of the minutes on the dial of an analog clock works accordingly. The minutes are numbered from 0 to 59 and accordingly you get in, for example , etc. Calculating with remaining classes can also be found in the calculation of days that are limited to 24 hours and in weeks that consist of 7 days and then accordingly not on one Set of numbers but of day names is defined, for example "5 days after Friday is Wednesday, 5 days before Wednesday is Friday". ${\displaystyle \mathbb {Z} /60\mathbb {Z} =\{0,1,\dotsc ,58,59\}}$ ${\displaystyle 15+30=45,\ 30+30=0,\ 45+30=15}$

The remainder class ring modulo 2

The residual class ring is shown graphically ${\displaystyle \mathbb {Z} /2\mathbb {Z} }$

If whole numbers are divided by 2 with a remainder, the remainder is either 0 or 1. This is the second smallest of all remainder class rings after the single-element zero ring. Since 2 is a prime number, there is even a finite field here , the smallest of all fields. ${\displaystyle \mathbb {Z} /2\mathbb {Z} =\mathbb {Z} _{2}=\{0,1\}}$ ${\displaystyle \mathbb {Z} /1\mathbb {Z} =\mathbb {Z} _{1}=\{\mathbb {Z} \}}$ ${\displaystyle \mathbb {F} _{2}}$

The remainder class ring modulo 3

The residual class ring is shown graphically. ${\displaystyle \mathbb {Z} /3\mathbb {Z} }$

Division by 3 results in the three remainder classes

${\displaystyle \mathbf {0} :=[0]=\{\dotsc ,-6,-3,0,3,6,9,12,\dotsc \}}$, d. H. the numbers divisible by 3.

${\displaystyle \mathbf {1} :=[1]=\{\dotsc ,-5,-2,1,4,7,10,13,\dotsc \}}$, d. i.e. the remainder of the division is 1.

${\displaystyle \mathbf {2} :=[2]=\{\dotsc ,-4,-1,2,5,8,11,14,\dotsc \}}$, d. i.e. the remainder of the division is 2.

Let’s calculate : Select roughly the 4 and the 8 . Do the math . 12 is in . So . ${\displaystyle \mathbf {1} +\mathbf {2} }$
${\displaystyle \mathbf {1} }$ ${\displaystyle \mathbf {2} }$ ${\displaystyle 4+8=12}$ ${\displaystyle \mathbf {0} }$ ${\displaystyle \mathbf {1} +\mathbf {2} =\mathbf {0} }$

The set gets the link tables like this: ${\displaystyle \mathbb {Z} /3\mathbb {Z} =\{\mathbf {0} ,\mathbf {1} ,\mathbf {2} \}}$

Addition: ${\displaystyle +}$ 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1

Multiplication: ${\displaystyle \cdot }$ 0 1 2 0 0 0 0 1 0 1 2 2 0 2 1

${\displaystyle (\mathbb {Z} /3\mathbb {Z} ,+,\cdot )}$is a ring and, since 3 is a prime number , even a field , which is referred to as (from English field ). ${\displaystyle \mathbb {F} _{3}}$

The remainder class ring modulo 4

The residual class ring is shown graphically ${\displaystyle \mathbb {Z} /4\mathbb {Z} }$

Let's look at the remainder of dividing by 4.

It applies with: ${\displaystyle \mathbb {Z} /4\mathbb {Z} =\{\mathbf {0} ,\mathbf {1} ,\mathbf {2} ,\mathbf {3} \}}$

${\displaystyle \mathbf {0} =\{\dotsc ,-4,0,4,8,12,16,\dotsc \}}$

${\displaystyle \mathbf {1} =\{\dotsc ,-3,1,5,9,13,17,\dotsc \}}$

${\displaystyle \mathbf {2} =\{\dotsc ,-2,2,6,10,14,18,\dotsc \}}$

${\displaystyle \mathbf {3} =\{\dotsc ,-1,3,7,11,15,19,\dotsc \}}$

In this remainder class ring , i. H. is a zero divisor . So the multiplication is not completed in. The resulting structure is therefore not a body, but only a commutative ring (the remainder class ring modulo 4), because zero divisors have no multiplicative inverse . This has to do with the fact that 4 is not a prime number and is therefore not an integrity ring . (However, since 4 = 2 ^{2 is} a power of a prime number, there is another field that has four elements.) ${\displaystyle \mathbf {2} \cdot \mathbf {2} =\mathbf {0} }$ ${\displaystyle \mathbf {2} }$ ${\displaystyle \mathbb {Z} /4\mathbb {Z} \,\setminus \,\{\mathbf {0} \}}$ ${\displaystyle (\mathbb {Z} /4\mathbb {Z} ,+,\cdot )}$ ${\displaystyle \mathbb {Z} /4\mathbb {Z} }$

Integer arithmetic in microprocessors

Common microprocessors (often referred to as the 16-bit integer numbers: how they are used for example in computers, expected in the integer arithmetic in reality in residue class rings short integer called) make up the remainder class ring with . For example, the result of the addition 65535 + 1 is 0, and 32768 · 2 is also 0. ${\displaystyle \mathbb {Z} /65536\mathbb {Z} }$ ${\displaystyle 65536=2^{16}}$

generalization

The idea of ​​residual classes can also be implemented in rings other than whole numbers. To this end, the concept of the ideal is defined and residual classes are formed modulo an ideal, which in turn form a ring called the factor ring .

literature

• Andreas Bartholomé, Josef Rung, Hans Kern: Number theory for beginners. Vieweg + Teubner, 7th edition, 2010, ISBN 978-3-8348-1213-1 .