296 ALGEBRAIC STRUCTURES
This particular element α is the primitive element of the group G. All elements γ ∈ G
of a finite group G of order ord(G) fulfil the condition
γ
ord
(G)
= e.
A.1.2 Rings
If we define two operations – multiplication ‘·’ and addition ‘+’ – over the set S, then S
is called a ring if the following properties are fulfilled for all elements a, b,c ∈ S:
(R1) a + b ∈ S,
(R2) a + (b + c) = (a + b) + c,
(R3) ∃0 ∈ S : ∀a ∈ S : a + 0 = 0 +a = a,
(R4) ∀a ∈ S : ∃−a ∈ S : a + (−a) = 0,
(R5) a + b = b + a,
(R6) a · b ∈ S,
(R7) a · (b · c) = (a · b) · c,
(R8) a · (b + c) = a · b + a · c.
The element 0 is the zero element. The inverse element of a with respect to addition is
given by −a. If, additionally, the following two properties
(R9) ∃1 ∈ S : ∀a ∈ S : a · 1 = 1 ·a = a,
(R10) a · b = b · a
are met, then the ring is called a commutative ring with identity. The element 1 denotes the
identity element. In the following, we will use the common notation ab for the multipli-
cation a · b. The set of integers Z with ordinary addition ‘+’ and multiplication ‘·’ forms
a commutative ring with identity. Another example of a commutative ring with identity is
the residue class ring defined in Figure A.1.
An important operation for rings is the division with remainder. As a well-known
example, we will consider the set of integers Z. For two integers a, b ∈ Z there exist
numbers q,r ∈ Z such that
a = qb+ r
with quotient q, remainder r and 0 ≤ r<b. Written with congruences, this reads
a ≡ r mod b.
If the remainder r is zero according to a ≡ 0 modulo b, the number b divides a which we
will write as b|a. b is called a divisor of a. A prime number p>1 is defined as a number
that is only divisible by 1 and itself.
The greatest common divisor gcd(a, b) of two numbers a and b can be calculated with
the help of Euclid’s algorithm. This algorithm is based on the observation that gcd(a, b) =
gcd(a, b − ca) for each integer c ∈ Z. Therefore, the greatest common divisor gcd(a, b)