Cyclic ring

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Definition

The rings are simple mathematical structures that generalize the properties of addition and multiplication (associativity, commutativity, distributivity, neutral element, opposite...) of the set of relative integers Z in particular.

The cyclic rings are characterized by being generated by a single element (they are said to be monogeneous) and by being finite. More precisely, for every natural number n ≥ 2 there exists a unique cyclic ring (through isomorphisms) of order (size) n, it is noted Z/nZ (as a quotient of the ring Z by the ideal nZ), Z/(n) (nZ, ideal generated by n is also written (n)) or Z_n, and can be represent as in the figure.
They were the first rings discovered after Z and the name "ring" obviously comes from the previous figure.

Elementary calculus

In the ring Z_n, the sum and the product are the usual Z with an additional rule: it is decided that the numbers n and 0 are equal: it is written n ≡ 0 or n ≡ 0 (mod n) to be more precise, when one is placed in Zand ${displaystyle {overline {n}}={overline {o}}}$ when working in Z_n (ā is an arbitrary way of designating the kind of equivalence of a Z_n - this notation will not be used here.
Applying several times the above is shown to be lawful to add or subtract how many times you want "n" to a term without changing its value Z_n:

a ≡ a + k·n (mod n), with k 한 Z.

a and a + k n are said to be equal modulo n or congruent modulo n and This class of equalities is called modular calculus or congruences.

For example in Z₁₀: 1968 ≡ 8, because 1968 = 196×10 + 8.

In this example, 8 is the remainder of the Euclidean division of 1968 by 10, and in fact each division gives rise to a congruence:

the rest and the dividend are equal module the divider
if a = b·q + r, then r ≡ a (mod q)

The relation ≡ can be seen as a congruence in Z or as an equality in Z_n. Since we have decided not to distinguish the integer a from its class ā, the same relation a ≡ b (mod n) has two interpretations. Seeing it as an equality has the advantage of being much more intuitive; for example the following properties will not surprise you:

Let a₁,a₂, b₁, b₂ be integers (or elements of Z_n), and m a natural, then:

{displaystyle {mbox{si }} a_{1}equiv a_{2} y b_{1}equiv b_{2} {mbox{entonces }}left{{begin{matrix}a_{1}+b_{1}equiv a_{2}+b_{2},\a_{1}b_{1}equiv a_{2}b_{2},\a_{1}^{m}equiv a_{2}^{m}end{matrix}}right.}

Direct applications to arithmetic

Divisibility criteria by 3, 9 and 11 are a direct result of previous relationships.

Let us consider the best known, the criterion for 9. Let us be a number n whose digits are a_o (units), a₁ (tens), a₂ (hundreds)...

It's customary to write. ${displaystyle n={overline {a_{p}a_{p-1}...a_{2}a_{1}a_{o}}}}$ to distinguish it from the product ${displaystyle n=a_{p}a_{p-1}...a_{2}a_{1}a_{o}quad }$ And then, in classic writing: ${displaystyle n=a_{p}10^{p}+a_{p-1}10^{p-1}+...+a_{2}10^{2}+a_{1}10+a_{o}quad }$

Like ${displaystyle 10equiv 1;(mod;9)}$ then for all positive integer k ${displaystyle 10^{p}equiv 1^{p}equiv 1;(mod;9)quad }$ and adding the terms in n is obtained: ${displaystyle n=a_{p}10^{p}+...+a_{1}10+a_{o}equiv a_{p}+a_{p-1}+...+a_{1}+a_{0};(mod;9)}$

That is, the remainder modulo 9 is obtained by adding the digits of the number. To verify a calculation, for example a product: a = b×c, look at the remainders modulo 9, a', b' and c', and if a'≠b'×c' (mod 9) then the calculation is wrong. Otherwise it cannot be concluded.

Congruences also allow to solve essentially playful problems in the style find the number of units in 2003²⁰⁰⁵.

An ordinary computer is incapable of calculating number size. A good opportunity to underline the superiority of human intelligence over artificial intelligence, and show off at the first opportunity...
Finding the unit number is achieved by working modulo 10, since the remainder of division by 10 is precisely this number.
As 2003 ≡ 3 (mod 10), 2003²⁰⁰⁵ ≡ 3²⁰⁰⁵, then we have to look at the 3^k (mod 10):
3⁰ ≡ 1, 3¹ ≡ 3, 3² = 9 ≡ 9, 3³ = 27 ≡ 7, 3⁴ = 81 ≡ 1.
This last result allows us to generalize: 3^4k ≡ 1, for all natural k.
Then we divide 2005 by 4: 2005 = 4×501 + 1.
Finally 3²⁰⁰⁵ = 3^{4×501 + 1} = 3^4×501× 3¹ ≡ 1 × 3 = 3 (mod 10).
The desired number is 3.

Inversible elements

Addition, subtraction, and multiplication behave as expected in cyclic rings. But what about division?
Dividing by a number is by definition multiplying by its inverse. The question is then to find out which are the inversible elements of the ring. The number a is invertible in Z/(n) if and only if there exists b such that:

a·b ≡ 1 (mod n) what is written: a·b = 1 + k·n, k 한 Z I mean: a·b - k·n = 1.

This is a Bézout identity and has solutions if and only if a and n are coprime numbers (ie prime to each other: their greatest common divisor is 1).
Examples:

2 and 5, being number different cousins, are coprimos, then 2 is inversible in Z₅. A Bézout relationship is 2×3 - 1×5 = 1 that gives 2×3 ≡ 1 (mod 5), therefore the reverse of 2 is 3 in Z₅. In effect 2×3 = 6 ≡ 1 (mod 5).
7 and 12 are coprimos because the prime number 7 does not appear in the breakdown in prime factors of 12 = 22×3.

Euclid's algorithm allows us to obtain the Bezout relation:

3×12 - 5×7 = 1 that gives congruence: -5×7 ≡ 1 (mod 12).

-5 is therefore the inverse of 7 in Z₁₂. But -5 ≡ 7 (mod 12), therefore 7 is its own inverse in Z₁₂, which is quickly verified: 7² = 49 = 4×12 + 1 ≡ 1 (mod 12).

The number of invertible elements of Z_n is denoted φ(n), where φ is the Euler function fi.
If and only if n is prime, all nonzero natural integers less than n are coprime with n; this implies that they will all be Z_n invertible, making this ring a field sometimes denoted F_n.

Universality of cyclic rings

Let A be a finite ring, whose neutral (for multiplication) we denote e. The set of multiples of e, C = {0, e, 2 e, 3 e, 4 e...} to be included in A is also finite. Then from a certain value of m, m·e has already been listed in C, that is to say that there exists k < m such that k e = m e. By subtraction n e = 0 with n = m - k.
Let n be the smallest nonzero natural integer such that n e = 0. Then C = {0, e, 2 e, 3 e, 4 e...(n-1) ·e} that is to say that C is isomorphic to the cyclic ring of order n. Furthermore, C belongs to the center of A, since its elements commute with all those of A.
The number n also verifies the property of overriding all the elements of A: for all a ∈ A, n a = n e a = 0·a = 0. It is the nonzero natural minor that has this property, and it is called the characteristic of the ring.

In short:

Every finite ring has in its center a cyclic ring.
Your order is the characteristic of the ring
The structure of the ring is largely defined by its cyclic ring

Indeed, the product:

${displaystyle Ctimes Arightarrow A}$
${displaystyle (c,a)rightarrow ccdot a}$

Converts ring A into a module over C = Z_n. in particular, if the feature n is a prime, then A is a vector space over the field C = Z_n, and as such is necessarily ismorphic to Cⁿ. The inner product also gives it an algebra structure.

Cyclic Ring Products

Theorem:

For all pairs (a, b) of integers coprimos, Z_a·b isomorph to the product of Z rings_a×Z_b.

This allows decomposing a cyclic ring Z_n into smaller ones, according to the prime factorization of n.

Test:

Let us consider the linear map f:

Z → Z_a× Z_b

n → (n mod a, n mod b) ("n mod a" is the class n in Z_a)

The core of this application is the set of n numbers divisible by both a and b; are therefore the multiples of least common multiple of a and b which is ab because a and b are coprime: The kernel is Ker f = a ·bZ.
Since a and b are coprime, the theorem of Chinese remainders, a consequence of Bézout's identity, states that f is surjective: Im f = Z_a×Z_b. According to the decomposition of a linear map, there is an isomorphism (hence a bijection) between Z/Ker f and Im f, that is, between Z_{a b} and Z_a× Z_b.

The bijection is obtained graphically on a board of a × b boxes, listing the boxes of the diagonal (which corresponds to the application n → (n, n)) and when a border is reached it is followed by the opposite edge, as if touched. The red arrows of the second figure indicate these sudden changes of edges.
Let's look at the box containing the number 17. Corresponds to the element ${displaystyle {overline {17}}}$ of Z₂₈. It is located in the column ${displaystyle {overline {3}}}$ and the row ${displaystyle {overline {1}}}$ .
Then ${displaystyle {overline {17}}}$ of Z₂₈ corresponds to ${displaystyle ({overline {3}},{overline {1}})}$ of Z₇×Z₄.

With small values of a and b there is another way to obtain the bijection: Instead of cutting the diagonal into pieces, it is preferable to reproduce the board a × b as many times as necessary (actually b sometimes) to get the a b elements of Z_{a b}. Then they are brought together in the same painting.
Z₆ ≡ Z₂×Z₃, like this:
0 → (0,0)
1 → (1,1)
2 → (0,2)
3 → (1,0)
4 → (0,1)
5 → (1,2)

Gluing opposite edges of a rectangle gives in topology a torus, a tire without the central opening. The torus is in geometry the product of two circles, each one representing a cyclical ring.

The content of this article incorporates material from a Entry of the Universal Free Encyclopedia, published in Spanish under the Creative Commons Share-Igual 3.0 license.

Data: Q5695908

Contenido relacionado

Más resultados...