In particular, we will have (p a) = p a - p a-1, (p) = p-1.
Examples. (60) = 60
(81) = 81-27 = 54
Multiplicative function
Function (a) is called multiplicative if it satisfies the following two conditions:
This function is defined for all positive integers a and is not equal to zero for at least one such a.
For any positive coprime a 1 and a 2 we have:
(a 1 a 2) = (a 1) (a 2).
Basic concepts of the theory of comparisons
Comparison properties
We will consider integers in connection with the remainder of their division by a given positive integer m, which we will call the modulus.
Each integer corresponds to a certain remainder after dividing it by m. If two integers a and b correspond to the same remainder r, then they are said to be equal modulo m.
Comparability of numbers a and b modulo m is written:
Comparability of numbers a and b modulo m is equivalent to:
Possibilities to represent a as a = b + mt, where t is an integer.
Divisibility of a b by m.
Indeed, from a b (mod m) it follows
a = mq + r, b = mq 1 + r, 0<= r whence a - b = m (q - q 1), a = b + mt, t = q - q 1. Conversely, from a = b + mt, representing b as b = mq 1 + r, 0<=r we deduce a = mq + r, q = q 1 + t, i.e. a b (mod m). Both statements are proven. Two numbers comparable to the third are comparable to each other. Comparisons can be added term by term. Indeed, let A 1 b 1 (mod m), a 2 b 2 (mod m),…, a k b k (mod m) (1). Then a 1 = b 1 + mt 1, a 2 = b 2 + mt 2,…, a k = b k + mt k (2), Whence a 1 + a 2 +… + a k = b 1 + b 2 +… + b k + m (t 1 + t 2 +… + t k), or a 1 + a 2 +… + a k b 1 + b 2 +… + b k (mod m). Comparisons can be multiplied term by term. Consider (1) and (2). Multiplying equalities (2) term by term, we get: a 1 a 2… a k b 1 b 2… b k + mN, where N is an integer. Hence: a 1 a 2… a k b 1 b 2… b k (mod m). Both parts of the comparison can be raised to the same degree. Both parts of the comparison can be multiplied by the same integer. Indeed, multiplying the congruence a b (mod m) with the obvious congruence k k (mod m), we obtain ak bk (mod m). Both parts of the comparison can be divided by their common divisor if the latter is relatively prime to the modulus. Indeed, from ab (mod m), a = a 1 d, b = b 1 d, (d, m) = 1 it follows that the difference a - b equal to (a 1 - b 1) d is divisible by m, i.e. a 1 b 1 (mod m). Numbers that are equally sufficient, or, which is the same, comparable modulo m, form a class of numbers modulo m. It follows from this definition that all numbers of the class correspond to the same remainder r, and we will get all numbers of the class if, in the form mq + r, we force q to run through all integers. According to m different values of r, we have m classes of numbers modulo m. Any number of a class is called a residue modulo m with respect to all numbers of the same class. The residue obtained when q = 0, which is equal to the remainder r itself, is called the smallest non-negative residue. Taking one residue from each class, we obtain a complete system of residues modulo m. Most often, the smallest non-negative residues 0, 1, ..., m-1, or also the absolutely smallest residues, are used as a complete system of residues. The latter, as follows from the above, in the case of odd m are represented by the series 1, 0, 1, ..., and in the case of even m, either of the two series 1, 0, 1, ..., 1, 0, 1, ..., . Any m numbers that are pairwise incomparable modulo m form a complete system of residues modulo m. Indeed, being incomparable, these numbers thus belong to different classes, and since there are m, i.e. as many as there are classes, then each class will probably get one number. If (a, m) = 1 and x runs through the complete system of residues modulo m, then ax + b, where b is any integer, also runs through the complete system of residues modulo m. Indeed, there will be as many numbers ax + b as there are numbers x, i.e. m. According to the previous statement, it remains, therefore, only to show that any two numbers ax 1 + b and ax 2 + b corresponding to incomparable x 1 and x 2 will themselves be incomparable modulo m. But assuming that ax 1 + b ax 2 + b (mod m), we arrive at the comparison ax 1 = ax 2 (mod m), whence, due to (a, m) = 1, we obtain x 1 x 2 (mod m), which contradicts the assumption that the numbers x 1 and x 2 are incomparable. Numbers of the same class modulo m have the same common greatest divisor with the modulus. Especially important are the classes for which this divisor is equal to one, i.e. classes containing numbers that are relatively prime to the module. Taking one residue from each such class, we obtain the reduced system of residues modulo m. The reduced system of residues, therefore, can be composed of the numbers of the complete system, which are coprime to the modulus. The usually reduced system of residues is separated from the system of least non-negative residues: 0, 1, ..., m-1. Since among these numbers the number of coprime to m is (m), the number of numbers in the reduced system, as well as the number of classes containing numbers coprime to the modulus, is (m). Example. The reduced system of residues modulo 42 will be 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41. Any (m) numbers pairwise incomparable modulo m and coprime to the modulus form a reduced system of residues modulo m. Indeed, being incomparable and coprime with the modulus, these numbers thus belong to different classes containing numbers coprime to the modulus, and since their (m), i.e. as there are classes of the specified type, then each class will probably contain one number. If (a, m) = 1 and x runs over the reduced system of residues modulo m, then ax also runs over the reduced system of residues modulo m. Indeed, there will be as many numbers ax as there are numbers x, i.e. (m). According to the previous property, it remains, therefore, only to show that the numbers ax modulo m are incomparable and coprime with the modulus. The first follows from the property of comparisons (if a comparison takes place modulo m, then it also takes place modulo d, equal to any divisor of the number m) for numbers of a more general form ax + b, while the second follows from (a, m) = 1, (x, m) = 1. Euler's theorem (2. 5. 3. 1). For m> 1 and (a, m) = 1, we have a (m) 1 (mod m). Evidence. Indeed, if x runs through the reduced system of residues x = r 1, r 2, ..., r c; c = (m), composed of the smallest non-negative residues, then the smallest non-negative residues 1, 2, ..., from the numbers ax will run through the same system, but, generally speaking, located in a different order (1). Multiplying term by term comparisons ar 1 1 (mod m), ar 2 2 (mod m), ..., ar c c (mod m), we get a c 1 (mod m). Fermat's theorem (2. 5. 3. 2). For p prime and a not divisible by p, we have a p-1 1 (mod p). (2) Evidence. This theorem is a consequence of Euler's theorem for m = p. Fermat's theorem can be given a more convenient form by multiplying both sides of the congruence (2) by a, we obtain the congruence a p a (mod p), which is already valid for all integers a, since it is also true for a multiple of p. The theorem is proved. Theorem (2.5.3.3). If n = pq, (p and q are distinct primes), then (n) = (p-1) (q-1). Theorem (2.5.3.4). If n = pq, (p and q are distinct primes) and x is prime with respect to p and q, then x (n) = 1 (mod n). As shown in §5, the relation of comparability modulo m possesses the properties of reflexivity, symmetry, and transitivity; therefore it is an equivalence relation. Take an arbitrary integer a. We denote by o the set of numbers comparable to a modulo m: Let. Let now. Etc. The process will continue until the constructed sets cover the entire set of integers. This gives rise to a partition2> of the set Z into sets a. B, c, .. which are called classes of residues modulo m; each number included in any of the classes is called the deduction of this class. The number of residue classes modulo m is equal to m. Indeed, the remainder of the division of an integer into m takes one of the values m - 2 or m - 1, and therefore each of the numbers falls into one of the classes 01, the number of which is m. Taking one number from for each class of residues we obtain a system of representatives of the classes of residues, or a complete system of residues modulo m. Systems of residues Example 1. Various complete systems of residues modulo 7: Lemma 3. Numbers, xm form a complete system of residues modulo m if and only if they are pairwise incomparable modulo m. The necessity is obvious. Let us prove the sufficiency. If two numbers are not comparable in modulus then they fall into different classes of residues. Since there are all classes of residues m and the numbers rn under consideration, they constitute a complete system of residues. Lemma 4. Let xm be a complete system of residues modulo m, an integer a mutually simple with m, b an arbitrary integer. Then the numbers axi + 6, ax2 + b, ..axt -f b also form a complete system of residues. According to Lemma 3, it is enough to make sure that Suppose (to reduce to a contradiction) that OG the general definition of a relation and its properties will be discussed below - in Chapter LXVIII; note that number theory is the source of many important examples for general algebra. Partitioning a set is a representation of it as a union of pairwise disjoint subsets. Then a (xi-xj) \ my and, since (o, m) = 1, we have (Xi-Xj) m, which contradicts Lemma 3. Lemma 5. Let x = a (modm). Then (Systems of residues m Indeed, let r be the remainder of dividing o by m. Then, by Lemma 2 But since x = a (mod m), when dividing by m "" elo r "there has a remainder r, and, therefore, (i, m) = (r, m), whence the required result follows. Thus, numbers from one class of residues modulo m have the same greatest common divisor with m. Therefore, the following definition of e becomes correct. A residue modulo m is called given if it is mutually simple with the so-called The set of reduced deductions from different classes of deductions is called the reduced system of deductions. Example 2. For m = 7, the reduced system of residues may look like this: Systems of residues The Euler function (p (m) is the number of natural numbers that do not exceed m and are mutually simple with m. For example,. It is easy to see that if p is a prime number, Obviously, the reduced system of residues modulo m contains numbers.Lemma 6. Let a be a mutually simple reduced system of residues modulo m. Then the numbers ax \, ax k also form a reduced system of residues modulo m. 4 Since the numbers o and X ( are coprime with m, and their product ax * possesses the same property. By Lemma 4, the numbers ax \, ax2, ... belong to different classes of residues, and, therefore, by virtue of the preceding, form a reduced system of residues. Complete deduction system. Reduced system of deductions. The most commonly used residue systems: least positive, least non-negative, absolutely least, etc. Theorem 1... Properties of the complete and reduced system of residues. 1 °. Criterion for the complete system of deductions. Any set of m integers that are pairwise incomparable modulo m, forms a complete system of residues modulo m. 2 °. If the numbers x 1 , x 2 , ..., x m- complete system of residues modulo m, (a, m) = 1, b- an arbitrary integer, then numbers ax 1 +b, ax 2 +b, ..., ax m+b also constitute a complete system of residues modulo m. 3 °. Criterion of the Reduced System of Deductions. Any collection consisting of j ( m) integers that are pairwise incomparable modulo m and coprime with the modulus, forms a reduced system of residues modulo m. 4 °. If the numbers x 1 , x 2 , ..., x j ( m) Is the reduced system of residues modulo m, (a, m) = 1, then the numbers ax 1 , ax 2 , ..., a x j ( m) also constitute a reduced system of residues modulo m. Theorem 2. Euler's theorem. If the numbers a and m mutually simple, then a j ( m) º 1 (mod m). Consequence. 1 °. Fermat's theorem. If a p Is a prime number and a not divisible by p then a p–1 º 1 (mod p). 2 °. Generalized Fermat's theorem. If a p Is a prime number, then a p º a(mod p) for any aÎ Z
. § four. Solving comparisons with a variable Comparison solution. Equivalence. Comparison degree. Theorem... Properties of solutions of comparisons. 1 °. Whole residue classes are solutions to comparisons. 2 °. (" k)(a k º b k(mod m))Ù k= Þ comparisons º 0 (mod m) and º 0 (mod m) are equivalent. 3 °. If both parts of the comparison are multiplied by a number that is relatively prime to the modulus, then a comparison is obtained that is equivalent to the original one. 4 °. Any comparison based on a simple modulus p is equivalent to a comparison whose degree does not exceed p–1. 5 °. Comparison º 0 (mod p), where p- prime number, has no more n different solutions. 6 °. Wilson's theorem. ( n-one)! º –1 (mod n) Û n Prime number. § five. Solving First Degree Comparisons ax º b(mod m). Theorem... 1 °. If a ( a, m) = 1, then the congruence has a unique solution. 2 °. If a ( a, m) = d and b not divisible by d, then the comparison has no solutions. 3 °. If a ( a, m) = d and b divided by d, then the comparison has d different solutions that make up one class of residues modulo. Ways to solve comparisons ax º b(mod m) in the case when ( a, m) = 1: 1) selection (enumeration of elements of the complete system of deductions); 2) using Euler's theorem; 3) using the Euclidean algorithm; 4) variation of the coefficients (using property 2 ° of the complete system of residues from Theorem 2.2); Section 6. Indefinite equations of the first degree ax+by = c. Theorem... The equation ax+by = c solvable if and only if c (a, b). When ( a, b) = 1 all solutions of the equation are given by the formulas tÎ Z
where x 0 is any comparison solution ax º c(mod b), y 0 = . Diophantine equations. CHAPTER 10. Complex numbers Definition of a system of complex numbers. Existence of a system of complex numbers Definition of a system of complex numbers. Theorem... The complex number system exists. Model: R
2 with operations (a, b)+(c, d) = (a+c, b+d), (a, b)×( c, d) = (ac–bd, bc+ad), i= (0, 1) and identification but = (but, 0). Algebraic form of a complex number Representation of a complex number as z = a+bi where a, bÎ R
, i 2 = -1. The uniqueness of such a representation. Re z, Im z. Rules for performing arithmetic operations on complex numbers in algebraic form. Arithmetic n-dimensional vector space C
n... Systems of linear equations, matrices and determinants over C
. Extraction of square roots from complex numbers in algebraic form. Wikimedia Foundation. 2010. Reduced system of deductions- a part of the complete system of residues (see Complete system of residues), consisting of numbers relatively prime with modulus m. P. s. in. contains φ (m) numbers [φ (m) is the number of numbers coprime to m and less than m]. Any φ (m) numbers that are not comparable modulo m and ... ... Great Soviet Encyclopedia Reduced system of deductions- The reduced system of residues modulo m is a set composed of all numbers of the complete system of residues modulo m coprime to m. The reduced system of residues modulo m consists of φ (m) numbers, where φ (m) is the Euler function. As a given ... ... Wikipedia The multiplicative group of the residue ring- The reduced system of residues modulo m is the set of all numbers of the complete system of residues modulo m coprime to m. The reduced system of residues modulo m consists of φ (m) numbers, where φ (·) is the Euler function. As a reduced deduction system ... ... Wikipedia Euler function- Not to be confused with the prime number distribution function. The first thousand values Euler's function φ (n) is multiplicative ... Wikipedia Modulo comparison- Comparison modulo a natural number n in number theory, an equivalence relation on a ring of integers associated with divisibility by n. The factor ring in this relation is called the residue ring. The collection of corresponding identities and ... ... Wikipedia End group- The symmetry of a snowflake is associated with a group of rotations by an angle divisible by 60 °. A finite group is an algebraic group containing a finite number of elements (this number is called its order). Further, the group is assumed to be multiplicative, that is, the operation in ... ... Wikipedia Quadruple Klein group- The fourth Klein group is a fourth order group that plays an important role in higher algebra. Contents 1 Definition 2 Notation 3 ... Wikipedia Residue ring modulo n denote or. Its multiplicative group, as in the general case of groups of invertible elements of rings, is denoted by
∗
×
×
. To understand the structure of a group, you can consider a special case, where is a prime number, and generalize it. Consider the simplest case when, that is. Theorem: - cyclic group.
Example
: Consider a group To consider the general case, it is necessary to define a primitive root. A primitive root modulo is a number that, together with its residue class, generates a group. In the case of an entire module, the definition is the same. The structure of a group is determined by the following theorem: If p is an odd prime number and l is a positive integer, then there are primitive roots modulo, that is, a cyclic group. The reduced system of residues modulo consists of residue classes:. With respect to the multiplication defined for the residue classes, they form a group, moreover, and are mutually inverse (that is,
⋅
), but and are inverse to themselves. The entry means "cyclic group of order n". On difficulty, Farm, Hooley,. Waring formulated Wilson's theorem, and Lagrange proved it. Euler assumed the existence of primitive roots modulo a prime number. Gauss proved it. Artin put forward his hypothesis about the existence and quantification of primes, modulo which a given integer is a primitive root. Brower contributed to the study of the problem of the existence of sets of consecutive integers, each of which is the kth power modulo p. Bilharz proved an analogue of Artin's conjecture. Hooley proved Artin's conjecture under the assumption that the extended Riemann conjecture holds in algebraic number fields.Deductions. Complete and reduced deduction systems
Euler's and Fermat's theorems
See what the "Reduced system of deductions" is in other dictionaries:
The simplest case
General case
Example
Group structure
Group structure (Z / n Z) ×
×
φ
λ
Group generator
×
φ
λ
Group generator
×
φ
λ
Group generator
×
φ
λ
Group generator
1
C 1
1
1
0
33
C 2 × C 10
20
10
2, 10
65
C 4 × C 12
48
12
2, 12
97
C 96
96
96
5
2
C 1
1
1
1
34
C 16
16
16
3
66
C 2 × C 10
20
10
5, 7
98
C 42
42
42
3
3
C 2
2
2
2
35
C 2 × C 12
24
12
2, 6
67
C 66
66
66
2
99
C 2 × C 30
60
30
2, 5
4
C 2
2
2
3
36
C 2 × C 6
12
6
5, 19
68
C 2 × C 16
32
16
3, 67
100
C 2 × C 20
40
20
3, 99
5
C 4
4
4
2
37
C 36
36
36
2
69
C 2 × C 22
44
22
2, 68
101
C 100
100
100
2
6
C 2
2
2
5
38
C 18
18
18
3
70
C 2 × C 12
24
12
3, 69
102
C 2 × C 16
32
16
5, 101
7
C 6
6
6
3
39
C 2 × C 12
24
12
2, 38
71
C 70
70
70
7
103
C 102
102
102
5
8
C 2 × C 2
4
2
3, 5
40
C 2 × C 2 × C 4
16
4
3, 11, 39
72
C 2 × C 2 × C 6
24
6
5, 17, 19
104
C 2 × C 2 × C 12
48
12
3, 5, 103
9
C 6
6
6
2
41
C 40
40
40
6
73
C 72
72
72
5
105
C 2 × C 2 × C 12
48
12
2, 29, 41
10
C 4
4
4
3
42
C 2 × C 6
12
6
5, 13
74
C 36
36
36
5
106
C 52
52
52
3
11
C 10
10
10
2
43
C 42
42
42
3
75
C 2 × C 20
40
20
2, 74
107
C 106
106
106
2
12
C 2 × C 2
4
2
5, 7
44
C 2 × C 10
20
10
3, 43
76
C 2 × C 18
36
18
3, 37
108
C 2 × C 18
36
18
5, 107
13
C 12
12
12
2
45
C 2 × C 12
24
12
2, 44
77
C 2 × C 30
60
30
2, 76
109
C 108
108
108
6
14
C 6
6
6
3
46
C 22
22
22
5
78
C 2 × C 12
24
12
5, 7
110
C 2 × C 20
40
20
3, 109
15
C 2 × C 4
8
4
2, 14
47
C 46
46
46
5
79
C 78
78
78
3
111
C 2 × C 36
72
36
2, 110
16
C 2 × C 4
8
4
3, 15
48
C 2 × C 2 × C 4
16
4
5, 7, 47
80
C 2 × C 4 × C 4
32
4
3, 7, 79
112
C 2 × C 2 × C 12
48
12
3, 5, 111
17
C 16
16
16
3
49
C 42
42
42
3
81
C 54
54
54
2
113
C 112
112
112
3
18
C 6
6
6
5
50
C 20
20
20
3
82
C 40
40
40
7
114
C 2 × C 18
36
18
5, 37
19
C 18
18
18
2
51
C 2 × C 16
32
16
5, 50
83
C 82
82
82
2
115
C 2 × C 44
88
44
2, 114
20
C 2 × C 4
8
4
3, 19
52
C 2 × C 12
24
12
7, 51
84
C 2 × C 2 × C 6
24
6
5, 11, 13
116
C 2 × C 28
56
28
3, 115
21
C 2 × C 6
12
6
2, 20
53
C 52
52
52
2
85
C 4 × C 16
64
16
2, 3
117
C 6 × C 12
72
12
2, 17
22
C 10
10
10
7
54
C 18
18
18
5
86
C 42
42
42
3
118
C 58
58
58
11
23
C 22
22
22
5
55
C 2 × C 20
40
20
2, 21
87
C 2 × C 28
56
28
2, 86
119
C 2 × C 48
96
48
3, 118
24
C 2 × C 2 × C 2
8
2
5, 7, 13
56
C 2 × C 2 × C 6
24
6
3, 13, 29
88
C 2 × C 2 × C 10
40
10
3, 5, 7
120
C 2 × C 2 × C 2 × C 4
32
4
7, 11, 19, 29
25
C 20
20
20
2
57
C 2 × C 18
36
18
2, 20
89
C 88
88
88
3
121
C 110
110
110
2
26
C 12
12
12
7
58
C 28
28
28
3
90
C 2 × C 12
24
12
7, 11
122
C 60
60
60
7
27
C 18
18
18
2
59
C 58
58
58
2
91
C 6 × C 12
72
12
2, 3
123
C 2 × C 40
80
40
7, 83
28
C 2 × C 6
12
6
3, 13
60
C 2 × C 2 × C 4
16
4
7, 11, 19
92
C 2 × C 22
44
22
3, 91
124
C 2 × C 30
60
30
3, 61
29
C 28
28
28
2
61
C 60
60
60
2
93
C 2 × C 30
60
30
11, 61
125
C 100
100
100
2
30
C 2 × C 4
8
4
7, 11
62
C 30
30
30
3
94
C 46
46
46
5
126
C 6 × C 6
36
6
5, 13
31
C 30
30
30
3
63
C 6 × C 6
36
6
2, 5
95
C 2 × C 36
72
36
2, 94
127
C 126
126
126
3
32
C 2 × C 8
16
8
3, 31
64
C 2 × C 16
32
16
3, 63
96
C 2 × C 2 × C 8
32
8
5, 17, 31
128
C 2 × C 32
64
32
3, 127
Application
Notes (edit)
Literature
