The sum of the reduced residues modulo n. Withdrawal systems. Exercises for independent work
![The sum of the reduced residues modulo n. Withdrawal systems. Exercises for independent work](https://i2.wp.com/konspekta.net/lektsianew/baza13/30078065046.files/image063.gif)
or any consecutive p numbers.
This system is called a complete system of numbers that are not comparable in modulus p or complete system of residues modulo p. It is obvious that any p consecutive numbers form such a system.
All numbers belonging to the same class have many common properties, therefore, in relation to the modulus, they can be considered as one number. Each number included in the comparison as a summand or factor can be replaced, without violating the comparison, by a number comparable to it, i.e. with a number belonging to the same class.
The other element that is common to all numbers of a given class is the greatest common divisor of each element of this class and module p.
Let a and b comparable modulo p, then
Theorem 1. If in ax+b instead of x let's put everything in order p members of the complete system of numbers
Therefore all numbers ax+b, where x=1,2,...p-1 are not comparable modulo p(otherwise, numbers 1,2,... p-1 would be comparable modulo p.
Notes
1) In this article, the word number will mean an integer.
Literature
- 1. K. Ireland, M. Rosen. Classical introduction to modern number theory. - M: Mir, 1987.
- 2. G. Davenport. Higher arithmetic. - M: Nauka, 1965.
- 3. P.G. Lejeune Dirichlet. Lectures on number theory. − Moscow, 1936.
Modulo residue ring n denote or . Its multiplicative group, as in the general case of groups of invertible elements of rings, is denoted ∗ × × .
The simplest case
To understand the structure of the group , we 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
= (1,2,4,5,7,8) The group generator is the number 2. ≡ ≡ ≡ ≡ ≡ ≡ As you can see, any element of the group can be represented as , where ≤ℓφ . That is, the group is cyclic.General case
To consider the general case, it is necessary to define a primitive root. A primitive root modulo a prime is a number which, together with its residue class, gives rise to a group.
Examples: 2 11 ; 8 - primitive root modulo 11 ; 3 is not a primitive modulo root 11 .In the case of an entire module, the definition is the same.
The structure of the 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.
Example
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, ⋅ ) and are inverse to themselves.
Group structure
The entry means "cyclic group of order n".
× | φ | λ | Group generator | × | φ | λ | Group generator | × | φ | λ | Group generator | × | φ | λ | Group generator | |||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | C1 | 1 | 1 | 0 | 33 | C2×C10 | 20 | 10 | 2, 10 | 65 | C4×C12 | 48 | 12 | 2, 12 | 97 | C96 | 96 | 96 | 5 | |||
2 | C1 | 1 | 1 | 1 | 34 | C 16 | 16 | 16 | 3 | 66 | C2×C10 | 20 | 10 | 5, 7 | 98 | C42 | 42 | 42 | 3 | |||
3 | C2 | 2 | 2 | 2 | 35 | C2×C12 | 24 | 12 | 2, 6 | 67 | C66 | 66 | 66 | 2 | 99 | C2×C30 | 60 | 30 | 2, 5 | |||
4 | C2 | 2 | 2 | 3 | 36 | C2×C6 | 12 | 6 | 5, 19 | 68 | C2×C16 | 32 | 16 | 3, 67 | 100 | C2×C20 | 40 | 20 | 3, 99 | |||
5 | C4 | 4 | 4 | 2 | 37 | C 36 | 36 | 36 | 2 | 69 | C2×C22 | 44 | 22 | 2, 68 | 101 | C 100 | 100 | 100 | 2 | |||
6 | C2 | 2 | 2 | 5 | 38 | C 18 | 18 | 18 | 3 | 70 | C2×C12 | 24 | 12 | 3, 69 | 102 | C2×C16 | 32 | 16 | 5, 101 | |||
7 | C6 | 6 | 6 | 3 | 39 | C2×C12 | 24 | 12 | 2, 38 | 71 | C70 | 70 | 70 | 7 | 103 | C 102 | 102 | 102 | 5 | |||
8 | C2×C2 | 4 | 2 | 3, 5 | 40 | C2×C2×C4 | 16 | 4 | 3, 11, 39 | 72 | C2×C2×C6 | 24 | 6 | 5, 17, 19 | 104 | C2×C2×C12 | 48 | 12 | 3, 5, 103 | |||
9 | C6 | 6 | 6 | 2 | 41 | C40 | 40 | 40 | 6 | 73 | C72 | 72 | 72 | 5 | 105 | C2×C2×C12 | 48 | 12 | 2, 29, 41 | |||
10 | C4 | 4 | 4 | 3 | 42 | C2×C6 | 12 | 6 | 5, 13 | 74 | C 36 | 36 | 36 | 5 | 106 | C 52 | 52 | 52 | 3 | |||
11 | C 10 | 10 | 10 | 2 | 43 | C42 | 42 | 42 | 3 | 75 | C2×C20 | 40 | 20 | 2, 74 | 107 | C 106 | 106 | 106 | 2 | |||
12 | C2×C2 | 4 | 2 | 5, 7 | 44 | C2×C10 | 20 | 10 | 3, 43 | 76 | C2×C18 | 36 | 18 | 3, 37 | 108 | C2×C18 | 36 | 18 | 5, 107 | |||
13 | C 12 | 12 | 12 | 2 | 45 | C2×C12 | 24 | 12 | 2, 44 | 77 | C2×C30 | 60 | 30 | 2, 76 | 109 | C 108 | 108 | 108 | 6 | |||
14 | C6 | 6 | 6 | 3 | 46 | C 22 | 22 | 22 | 5 | 78 | C2×C12 | 24 | 12 | 5, 7 | 110 | C2×C20 | 40 | 20 | 3, 109 | |||
15 | C2×C4 | 8 | 4 | 2, 14 | 47 | C46 | 46 | 46 | 5 | 79 | C78 | 78 | 78 | 3 | 111 | C 2×C 36 | 72 | 36 | 2, 110 | |||
16 | C2×C4 | 8 | 4 | 3, 15 | 48 | C2×C2×C4 | 16 | 4 | 5, 7, 47 | 80 | C2×C4×C4 | 32 | 4 | 3, 7, 79 | 112 | C2×C2×C12 | 48 | 12 | 3, 5, 111 | |||
17 | C 16 | 16 | 16 | 3 | 49 | C42 | 42 | 42 | 3 | 81 | C 54 | 54 | 54 | 2 | 113 | C 112 | 112 | 112 | 3 | |||
18 | C6 | 6 | 6 | 5 | 50 | C 20 | 20 | 20 | 3 | 82 | C40 | 40 | 40 | 7 | 114 | C2×C18 | 36 | 18 | 5, 37 | |||
19 | C 18 | 18 | 18 | 2 | 51 | C2×C16 | 32 | 16 | 5, 50 | 83 | C82 | 82 | 82 | 2 | 115 | C 2×C 44 | 88 | 44 | 2, 114 | |||
20 | C2×C4 | 8 | 4 | 3, 19 | 52 | C2×C12 | 24 | 12 | 7, 51 | 84 | C2×C2×C6 | 24 | 6 | 5, 11, 13 | 116 | C2×C28 | 56 | 28 | 3, 115 | |||
21 | C2×C6 | 12 | 6 | 2, 20 | 53 | C 52 | 52 | 52 | 2 | 85 | C4×C16 | 64 | 16 | 2, 3 | 117 | C6×C12 | 72 | 12 | 2, 17 | |||
22 | C 10 | 10 | 10 | 7 | 54 | C 18 | 18 | 18 | 5 | 86 | C42 | 42 | 42 | 3 | 118 | C 58 | 58 | 58 | 11 | |||
23 | C 22 | 22 | 22 | 5 | 55 | C2×C20 | 40 | 20 | 2, 21 | 87 | C2×C28 | 56 | 28 | 2, 86 | 119 | C 2×C 48 | 96 | 48 | 3, 118 | |||
24 | C2×C2×C2 | 8 | 2 | 5, 7, 13 | 56 | C2×C2×C6 | 24 | 6 | 3, 13, 29 | 88 | C2×C2×C10 | 40 | 10 | 3, 5, 7 | 120 | C2×C2×C2×C4 | 32 | 4 | 7, 11, 19, 29 | |||
25 | C 20 | 20 | 20 | 2 | 57 | C2×C18 | 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 | C2×C12 | 24 | 12 | 7, 11 | 122 | C60 | 60 | 60 | 7 | |||
27 | C 18 | 18 | 18 | 2 | 59 | C 58 | 58 | 58 | 2 | 91 | C6×C12 | 72 | 12 | 2, 3 | 123 | C2×C40 | 80 | 40 | 7, 83 | |||
28 | C2×C6 | 12 | 6 | 3, 13 | 60 | C2×C2×C4 | 16 | 4 | 7, 11, 19 | 92 | C2×C22 | 44 | 22 | 3, 91 | 124 | C2×C30 | 60 | 30 | 3, 61 | |||
29 | C 28 | 28 | 28 | 2 | 61 | C60 | 60 | 60 | 2 | 93 | C2×C30 | 60 | 30 | 11, 61 | 125 | C 100 | 100 | 100 | 2 | |||
30 | C2×C4 | 8 | 4 | 7, 11 | 62 | C 30 | 30 | 30 | 3 | 94 | C46 | 46 | 46 | 5 | 126 | C6×C6 | 36 | 6 | 5, 13 | |||
31 | C 30 | 30 | 30 | 3 | 63 | C6×C6 | 36 | 6 | 2, 5 | 95 | C 2×C 36 | 72 | 36 | 2, 94 | 127 | C 126 | 126 | 126 | 3 | |||
32 | C2×C8 | 16 | 8 | 3, 31 | 64 | C2×C16 | 32 | 16 | 3, 63 | 96 | C2×C2×C8 | 32 | 8 | 5, 17, 31 | 128 | C 2×C 32 | 64 | 32 | 3, 127 |
Application
On difficulty, Farm, Hooley, . Waring formulated Wilson's theorem, and Lagrange proved it. Euler suggested the existence of primitive roots modulo a prime number. Gauss proved it. Artin put forward his hypothesis about the existence and quantification of prime numbers modulo which a given integer is a primitive root. Brouwer contributed to the study of the problem of the existence of sets of consecutive integers, each of which is the kth power modulo p. Bielhartz proved an analogue of Artin's conjecture. Hooley proved Artin's conjecture with the assumption that the extended Riemann hypothesis is valid in algebraic number fields.
Notes
Literature
- Ireland K., Rosen M. A classic introduction to modern number theory. - M.: Mir, 1987.
- Alferov A.P., Zubov A.Yu., Kuzmin A.S. Cheremushkin A.V. Fundamentals of cryptography. - Moscow: "Helios ARV", 2002.
- Rostovtsev A.G., Makhovenko E.B. Theoretical cryptography. - St. Petersburg: NPO "Professional", 2004.
BASIC INFORMATION FROM THE THEORY
6. 1. Definition 1.
The class of numbers modulo m is the set of all those and only those integers that, when divided by m, have the same remainder r, that is, comparable modulo m (t Î N, t> 1).
Designation for a class of numbers with a remainder r: .
Each number from the class is called a residue modulo m, and the class itself is called the class of residues modulo m.
6. 2. Properties of the set of modulo residue classes t:
1) total modulo t will be t Residue classes: Z t = { , , , … , };
2) each class contains an infinite set of integers (residues) of the form: = ( a= mq+ r/qÎ Z, 0£ r< m}
3) "aÎ : aº r(mod m);
4) "a, bÎ : aº b(mod m), that is, any two residues taken from one class, comparable modulo t;
5) "aÎ , " bÎ : a b(mod m), that is, no two residues; taken from different classes incomparable modulo t.
6. 3. Definition 3.
A complete system of residues modulo m is any set of m numbers taken one and only one from each class of residues modulo m.
Example: if m= 5, then (10, 6, - 3, 28, 44) is a complete system of residues modulo 5 (and not the only one!)
In particular,
set (0, 1, 2, 3, … , m–1) is a system the smallest non-negative deductions;
set (1, 2, 3, ... , m –1, t) is the system least positive deductions.
6. 4. Note that:
if ( X 1 , X 2 , … , x t) is the complete system of residues modulo t, then
.
6. 5. Theorem 1.
If a {X 1 , X 2 , … , x t} – complete system of residues modulo m, "a, bÎ Z and(a, t) = 1, – then the number system {Oh 1 +b, Oh 2 + b, … , ah t+b} also forms a complete system of residues modulo m .
6. 6. Theorem 2.
All residues of the same class of residues modulo m have the same greatest common divisor with m: "a, bÎ Þ ( a; t) = (b; t).
6. 7. Definition 4.
Residue class modulo m is called coprime with modulo m,if at least one residue of this class is coprime with i.e.
Note that in this case, by Theorem 2 all the numbers of this class will be coprime with the modulus t.
6. 8. Definition 5.
A reduced system of residues modulo m is a system of residues taken one and only one from each class coprime to m.
6. 9. Note that:
1) reduced system of residues modulo t contains j( t) numbers ( X 1 , X 2 ,…, };
2) :
.
3) "x i : (x i, m) = 1;
Example : Let modulo t= 10 there are 10 classes of residues:
Z 10 = ( , , , , , , , , , ) is the set of residue classes modulo 10. Complete system of deductions mod 10 would be, for example, this: (0, 1, 2, 3, 4, 5, 6, 7, 8, 9).
Many classes of residues, coprime with module m= 10: ( , , , )(j(10) = 4).
The reduced system of deductions modulo 10 would be, for example,
(1, 3, 7, 9), or (11, 43, – 5, 17), or ( – 9, 13, – 5, 77), etc. (everywhere j(10) = 4 numbers).
6.10. Practically: to form one of the possible reduced residue systems mod m, it is necessary to choose from the complete system of residues mod m those residues that are coprime with m. Such numbers will be j( t).
6.11. Theorem 3.
If a{X 1 , X 2 ,…, } – reduced system of residues modulo m and
(a, m) = 1, – then the number system {Oh 1 , Oh 2 , … , ax j (t)} also forms
reduced system of residues modulo m .
6.12. Definition 6.
sum( Å ) deduction classes and +b equal to the sum of any two deductions taken one from each given class and : Å = , where"aÎ , "bÎ .
6.13. Definition 7.
work( Ä ) deduction classes and modulo m is called the residue class , that is, the class of residues consisting of numbers a ´ b equal to the product of any two residues taken one by one from each given class and : Ä = , where"aÎ , "bÎ .
Thus, in the set of residue classes modulo t: Z t= ( , , ,…, ) two algebraic operations are defined – "addition" and "multiplication".
6.14. Theorem 4.
The set of residue classes Z t modulo t is an associative-commutative ring with a unit:
< Z t , +, · > = < { , , ,…, }, +, · > – ring.
TYPICAL TASKS
1. Modulo t= 9:
1) a complete system of least positive residues;
2) a complete system of least non-negative residues;
3) an arbitrary full system of deductions;
4) a complete system of the least absolute deductions.
Answer:1) {1, 2, 3, 4, 5, 6, 7, 8, 9}; 2) {0, 1, 2, 3, 4, 5, 6, 7, 8};
2. Compile the reduced system of residues modulo t= 12.
Solution.
1) Compose a complete system of least positive residues modulo t= 12:
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12) (total t= 12 numbers).
2) We delete from this system the numbers that are not coprime with the number 12:
{1, 2 , 3 , 4 , 5, 6 , 7, 8 , 9 , 10 , 11, 12 }.
3) The remaining numbers, coprime with the number 12, form the desired reduced system of residues modulo t= 12 (total j( t) = j(12) = 4 numbers).
Answer:(1, 5, 7, 11) - reduced system of residues modulo t= 12.
130. Make 1) a complete system of the least positive residues; 2) a complete system of least non-negative residues; 3) an arbitrary system of deductions; 4) a complete system of the smallest absolute deductions; 5) the reduced system of residues: a) modulo m= 6; b) modulo m = 8.
131. Is the set (9, 2, 16, 20, 27, 39, 46, 85) a complete system of residues modulo 8?
132 By what modulus is the set (20, - 4, 22, 18, - 1) a complete system of residues?
133. Make the reduced system of residues modulo m if a) m= 9; b) m= 24; in) m= 7. How many numbers should such a system contain?
134. Formulate the main properties of the complete system of residues and the reduced system of residues modulo m .
135. What elements distinguish the reduced and complete systems of least non-negative residues modulo prime?
136. Under what condition are the numbers a and - a belong to the same class of modulo residues m?
137. To what classes of residues modulo 8 do all prime numbers belong? R³ 3 ?
138. Does the set of numbers (0, 2 0 , 2 1 , 2 2 , ... , 2 9 ) form a complete system of residues modulo 11?
139. How many classes of residues modulo 21 belong to all residues from one class of residues modulo 7?
140. Set of integers Z distribute by residue classes modulo 5. Make addition and multiplication tables in the resulting set of residue classes Z 5 . Is the set Z 5: a) a group with a class addition operation? b) a group with the operation of class multiplication?
§ 7. Euler's theorem. FERMAT'S LITTLE THEOREM
BASIC INFORMATION FROM THE THEORY
7. 1. Theorem 1.
If aÎ Z,tÎ N, t>1 and(a;t) = 1, – then in an infinite sequence of powers a 1 , a 2 , a 3 , ... , a s , … , a t, … there are at least two powers with exponents s and t(s<t) such that . (*)
7. 2. Comment. Denoting t– s = k> 0, from (*) we get: . Raising both sides of this comparison to a power nÎ N, we get:
(**). This means that there are an infinite number of powers a, satisfying the comparison (**). But how find these indicators? What least indicator that satisfies the comparison (**) ? Answers the first question Euler's theorem(1707 – 1783).
7. 3. Euler's theorem.
If aÎ Z,tÎ N, t>1 and(a;t) = 1, - then . (13)
Example.
Let a = 2,t = 21, (a; t) = (2; 21) = 1. Then . Since j (21) = 12, then 2 12 º 1(mod 21). Indeed: 2 12 = 4096 and (4096 - 1) 21. Then it is obvious that 2 24 º 1(mod 21), 2 36 º 1(mod 21) and so on. But is the exponent of 12 - least satisfying comparison 2 nº 1(mod 21) ? It turns out not. The lowest indicator will be P= 6: 2 6 º 1(mod 21), since 2 6 – 1 = 63 and 63 21. Note that least index to be looked for only among divisors of a number j( t) (in this example, among the divisors of the number j(21) = 12).
7. 4. Fermat's Little Theorem (1601 - 1665).
For any prime number p and any number aÎ Z, not divisible by p, there is a comparison . (14)
Example.
Let a = 3,R= 5, where 3 is not 5. Then or
.
7. 5. Generalization of Fermat's theorem.
For any prime number p and arbitrary number aÎ Z is compared (15)
TYPICAL TASKS
1. Prove that 38 73 º 3(mod 35).
Solution.
1) Since (38; 35) = 1, then by the Euler theorem ; j(35) = 24, so
(1).
2) From comparison (1), by Corollary 2, properties 5 0 of numerical comparisons, we have:
3) From comparison (2), by Corollary 1 of property 5 0 comparisons: 38 72 ×38 º 1×38 (mod 35) Þ Þ38 73 º38 º 38–35 = 3(mod 35) Þ 38 73 º 3 (mod 35) , which was to be proved.
2. Given: a = 4, t= 15. Find the smallest exponent k, satisfying the comparison (*)
Solution.
1) Since ( a; m) = (4; 25) = 1, then by the Euler theorem , j(25) = 20, so
.
2) Is the found exponent - the number 20 - least a natural number that satisfies comparison (*)? If there is an exponent less than 20, then it must be a divisor of 20. Hence, the required minimum exponent k you have to search among a lot of numbers n= (1, 2, 4, 5, 10, 20) – divisors of 20.
3) When P = 1: ;
at P = 2: ;
at P= 3: (no need to consider);
at P = 4: ;
at P = 5: ;
at P= 6, 7, 8, 9: (no need to consider);
at P = 10: .
So, least exponent k, satisfying comparison(*), is k= 10.
Answer: .
EXERCISES FOR INDEPENDENT WORK
141. By Euler's theorem . At a = 3, t= 6 we have:
.
Since j(6) = 2, then 3 2 º1(mod 6), or 9º1(mod 6), Then, by the lemma, (9 – 1) 6 or 8 6 (completely!?). Where is the mistake?
142. Prove that: a) 23 100 º1(mod 101); b) 81 40 º 1(mod100); c) 2 73 º 2 (mod 73).
143. Prove that a) 1 16 + 3 16 + 7 16 + 9 16 º 4 (mod 10);
b) 5 4 P + 1 + 7 4P+ 1 is divisible by 12 without a remainder.
144. Prove a theorem converse to Euler's theorem: if a j ( m) º 1(mod m), then ( a, m) =1.
145. Find the smallest exponent kÎ N, satisfying this comparison: a) ; b)
; in)
; G)
;
e) ; e)
; and)
; h)
.
and) ; to)
; l)
; m)
.
146. Find the remainder of the division:
a) 7,100 for 11; b) 9,900 for 5; c) 5,176 by 7; d) 2 1999 by 5; e) 8 377 for 5;
f) 26 57 by 35; g) 35 359 for 22; h) 5,718 per 103; i) 27,260 to 40; j) 25 1998 at 62.
147*. Prove that a 561 º a(mod 11).
148*. If the canonical decomposition of a natural number P does not contain factors 2 and 5, then the 12th power of this number ends in 1. Prove.
149*. Prove that 2 64 º 16 (mod 360).
150*. Prove: if ( a, 65) =1 , (b, 65) =1, then a 12 –b 12 is evenly divisible by 65.
Chapter 3. ARITHMETIC APPLICATIONS
THEORIES OF NUMERICAL COMPARISONS
§ 8. SYSTEMATIC NUMBERS
BASIC INFORMATION FROM THE THEORY
1. INTEGER SYSTEMATIC NUMBERS
8. 1. Definition 1.
A number system is any way of writing numbers. The signs with which these numbers are written are called numbers.
8. 2. Definition 2.
An integer non-negative systematic number written in the t-ary positional number system is a number n of the form
,where a i(i = 0,1, 2,…, k) – integer non-negative numbers - digits, and 0 £ a i £ t– 1, t is the base of the number system, tÎ N, t > 1.
For example, the notation of a number in the 7-ary system is: (5603) 7 = 5 × 7 3 + 6 × 7 2 + 0 × 7 1 + 3. Here a i- these are 5, 6, 0, 3 - numbers; they all satisfy the condition: 0 £ a i£ 6. When t=10 say: number n recorded in decimal number system, and the index t= 10 do not write.
8. 3. Theorem 1.
Any non-negative integer can be represented, and in a unique way, as a systematic number in any base t, where tÎ N, t > 1.
Example:(1 3 9) 10 = (3 5 1) 6 = (1 0 2 4) 5 = …
8. 4. Note that:
1) assignment to the systematic number of zeros on the left does not change this number:
(3 4) 5 = (0 3 4) 5 .
2) attribution to a systematic number s zeros on the right is equivalent multiplication this number for t s: (3 4) 5 = 3×5 1 + 4; (3 4 0 0) 5 = 3×5 3 + 4×5 2 + 0×5 1 + 0 = 5 2 ×(3×5 1 + 4).
8. 5. Algorithm for converting a number written int -ary system, to decimal:
Example: (287) 12 = 2×12 2 + 8×12 1 +7×12 0 = 2×144 + 8×12 + 7 = 288 + 96 +7 = (391) 10 .
8. 6. Algorithm for converting a number written in decimal system, int -personal:
Example: (3 9 1) 10 = (X) 12 . Find X.
8. 7. Actions on systematic numbers
2. SYSTEMATIC FRACTIONS
8. 8. Definition 3.
A finite t-ary systematic fraction in a number system with base t is a number of the form
where c 0 Î Z, with i - numbers– integer non-negative numbers, and 0 £ with i£ t– 1, tÎ N, t > 1, kÎ N .
Notation: a = ( c 0 , With 1 With 2 …with k)t. At t= 10 the fraction is called decimal.
8. 9. Consequence 1.
Every finite systematic fraction is a rational number that can be represented as , where aÎ Z,bÎ N.
Example.
a = (3 1, 2 4) 6 = 3×6 + 1 + =19 + is a rational number. The converse statement is not true in general. For example, a fraction cannot be converted to a finite systematic (decimal) fraction.
8.10. Definition 4.
An infinite t-ary positive systematic fraction in a number system with base t is a number of the form
, where from 0Î N, with i(i =1, 2, …, to, …) - numbers– integer non-negative numbers, and 0 £ with i£ t–1, tÎ N, t > 1, kÎ N.
Notation: a = ( With 0 , With 1 With 2 … with k…) t. At t=10 the fraction is called decimal.
8.11. Definition 5.
There are three types of infinite systematic fractions:
I a = ( With 0 , )t= =
t, where =
= = … In this case, the number a is called an infinite purely periodic fraction,(With 1 With 2 … with k) – period, k - number of digits in the period - the length of the period.
II a = .
In this case, the number a is called an infinite mixed periodic fraction, – pre-period, () – period, k - the number of digits in the period - the length of the period, l - the number of digits between the integer part and the first period - the length of the pre-period.
III a = ( With 0 , With 1 With 2 … with k …)t . In this case, the number a is called an infinite non-periodic fraction.
TYPICAL TASKS
1. Number ( a) 5 = (2 1 4 3) 5 , given in the 5-ary system, translate into the 7-ary system, that is, find X, if (2 1 4 3) 5 = ( X) 7 .
Solution.
1) Convert the given number (2 1 4 3) 5 into the number ( at) 10 written in decimal system:
2. Follow the steps:
1) (7) 8 + (5) 8 ; 2) (7) 8 × (5) 8 ; 3) (3 6 4 2) 6 + (4 3 5 1) 6 ;
4) (5 2 3 4) 7 – (2 3 5 1) 7 ; 5) (4 2 3) 5 × (3 2) 5 ; 6) (3 0 1 4 1) 5: (4 2 3) 5 .
Solution.
1) (7) 8 + (5) 8 = (7) 10 + (5) 10 = (12) 10 = 1×8 + 4 = (1 4) 8 ;
2) (7) 8 × (5) 8 = (7) 10 × (5) 10 = (35) 10 = 4×8 + 3 = (4 3) 8 ;
3) (3 6 4 2) 6 + (4 3 5 1) 6 (1 2 4 3 3) 6 | Note: | 4+5 = 9 = 1×6+3, 3 is written, 1 goes to the next digit, 6+3+1=10 =1×6+4, 4 is written, 1 goes to the next digit, 3+4+1= 8 \u003d 1 × 6 + 2, 2 is written, 1 goes to the next digit. |
4) (5 2 3 4) 7 – (2 3 5 1) 7 (2 5 5 3) 7 | Note: | "occupy" a unit of the highest rank, i.e. "1" = 1x7: (3 + 1x7) - 5 = 10 - 5 = 5, (1 + 1x7) - 3 = 8 - 3 = 5 , |
5) (4 2 3) 5 ´ (3 2) 5 (1 4 0 1) 5 + (2 3 2 4) 5__ (3 0 1 4 1) 5 | Note: | When multiplying by 2: 3 × 2 = 6 = 1 × 5 + 1, we write 1, 1 goes to the next digit, 2 × 2 +1=5 = 1 × 5 +0, we write 0, 1 goes to the next digit, 2 ×4 +1=9 = 1×5 +4, 4 is written, 1 goes to the next digit, When multiplied by 3: 3 ×3 = 9 = 1×5 + 4, 4 is written, 1 goes to the next digit, 3 × 2 +1=7 = 1×5 +2, 2 is written, 1 goes to the next digit, 3×4 +1=13=2×5 +3, 3 is written, 2 goes to the next digit. |
6) (3 0 1 4 1) 5 | (4 2 3) 5
2 3 2 4 (3 2) 5
1 4 0 1 Answer: 1) (1 4) 8 ; 2) (4 3) 8 ; 3) (1 2 4 3 3) 6 ; 4) (2 5 5 3) 7 ;
(0) 5 5) (3 0 1 4 1) 5 ; 6) (3 2) 5 .
EXERCISES FOR INDEPENDENT WORK
151. Numbers given in t-ary system, convert to decimal system:
a) (2 3 5) 7 ; b) (2 4 3 1) 5 ; c) (1 0 0 1 0 1) 2 ; d) (1 3 ) 15 ;
e) (2 7) 11; f) (3 2 5 4) 6 ; g) (1 5 0 1 3) 8 ; h) (1 1 0 1 1 0 0 1) 2 ;
i) (7 6 2) 8 ; j) (1 1 1 1) 20 .
152. Numbers. given in the decimal system, convert to t-ic system. Make a check.
a) (1 3 2) 10 = ( X) 7 ; b) (2 9 8) 10 = ( X) 5 ; c) (3 7) 10 = ( X) 2 ; d) (3 2 4 5) 10 = ( X) 6 ;
e) (4 4 4 4) 10 = ( X) 3 ; f) (5 6 3) 10 = ( X) 12 ; g) (5 0 0) 10 = ( X) eight ; h) (6 0 0) 10 = ( X) 2 ;
i)(1 0 0 1 5) 10 =( X) twenty ; j) (9 2 5) 10 = ( X) eight ; k) (6 3 3) 10 = ( X) fifteen ; m) (1 4 3) 10 = ( X) 2 .
153. Numbers given in t-ary system, translate into q-ic system (by passing through the decimal system).
a) (3 7) 8 = ( X) 3 ; b) (1 1 0 1 1 0) 2 = ( X) 5 ; c) ( 6 2) 11 = ( X) 4 ;
d) (4 ) 12 = ( X) 9 . e) (3 3 1 3 1) 5 = ( X) 12 .
154. a) How will the number (1 2 3) 5 change if zero is added to it on the right?
b) How will the number (5 7 6) 8 change if two zeros are added to it on the right?
155. Follow these steps:
a) (3 0 2 1) 4 + (1 2 3 3) 4 ; b) (2 6 5 4) 8 + (7 5 4 3) 8 ; c) (1 0 1 1 0 1) 2 +(1 1 0 1 10) 2 ;
d) (5 2 4 7) 9 + (1 3 7 6) 9 ; e) (4 7 6) 9 - (2 8 7) 9; f) (2 4 5 3) 7 – (1 6 4 5) 7 ;
g) (8 3) 12 - (5 7 9) 12; h) (1 7 5) 11 – ( 6) 11 ; i) (3 6 4 0 1) 7 – (2 6 6 6 3) 7 ;
j) (1 0 0 1 0) 2 × (1 1 0 1) 2 ; k) (7 4 1) 8 × (2 6) 8; m) (5 3 7 2) 8 × (2 4 6) 8;
m) (3 3 2 1) 4 × (2 3 0) 4 ; o) (1 0 2 2 2 2) 3: (1 2 2) 3 ; n) (2 1 0 3 2) 4: (3 2 3) 4 ;
p) (2 6 1 7 4) 8: (5 4 6) 8 ; c) (4 3 2 0 1) 5: (2 1 4) 5 ; t)(1 1 0 1 0 0 1 0) 2:(1 0 1 0 1) 2
y) (1 1 0 1 1 0) 2: (1 1 1) 2 ; f) (1 1 1 0) 6: (2 1 5) 6 ; x)(3 2 3 8 2 2 1 7 0) 9:(7 6 4 2) 9 .
v) (1 6 3 5) 8 + (7 6 4) 8; h) (1 1 1 1) 3 - (2 1 2) 3; w)(1 2 7) 12 +(9 1 3 5 ) 12b" × b 1 Then:
I If the denominator b = b"(contains only "2" and/or "5") - then the fraction is converted to final decimal fraction. The number of decimal places is equal to the smallest natural number l lº 0( mod b").
II If the denominator b = b 1(does not contain "2" and "5"), then the fraction is converted to infinite purely periodic is equal to the smallest natural number k, satisfying comparison 10 kº 1( mod b 1).
III If the denominator b = b"× b 1 (contains "2" and / or "5", as well as other prime factors), then the fraction is converted to infinite mixed periodic ten-
ticking fraction.
The length of the period is equal to the smallest natural number k, satisfying comparison 10 kº 1( mod b 1).
The length of the pre-period is equal to the smallest natural number l, satisfying comparison 10 lº 0( mod b").
9. 2. Conclusions.
9. 3. Note that:
a rational number is any finite decimal fraction or infinite periodic decimal fraction;
An irrational number is any infinite non-periodic decimal fraction.
TYPICAL TASKS
1. These common fractions, written in the decimal system, are converted to
decimal, previously having determined the type of the desired fraction (finite or infinite; periodic or non-periodic; if - periodic, then purely periodic or mixed periodic); in the latter cases pre-find number k– period length and number l is the length of the pre-period. one) ; 2) ; 3).
Solution.
1) Fraction = denominator - number b= 80 = 2 4 × 5 contains only "2" and "5". Therefore, this fraction is converted to final decimal fraction. Number of decimal places l name determined from the condition: 10 lº0(mod80):
2) Fraction = denominator - number b= 27 = 3 3 does not contain "2" and "5". Therefore, this fraction is converted to an infinite purely periodic decimal fraction. Period length k name determined from the condition: 10 kº1(mod27):
3) Fraction = denominator - number b= 24 = 2 3 × 3, that is, it looks like: b = b"× b 1 (except for "2" or "5" contains other factors, in this case the number 3). Therefore, this fraction is converted to an infinite mixed periodic decimal fraction. Period length k name determined from the condition: 10 kº1(mod3), whence k name= 1, that is, the length of the period k= 1. Pre-period length l name determined from the condition: 10 lº0(mod8), whence l name= 3, that is, the length of the pre-period l = 3.
Check: divide the "corner" 5 by 24 and get: = 0, 208 (3).
Answer: 1) 0, 0375; 2) 0, (074); 3) 0, 208 (3).
EXERCISES FOR INDEPENDENT WORK
156. These ordinary fractions, written in the decimal system, convert to decimal fractions. If the decimal is periodic, then previously find the number k- period length and number l- the length of the pre-period.
157. These ordinary fractions, written in the decimal system, convert to t-ary systematic fractions. Find the numbers k- period length and l- the length of the pre-period.
158*. In what number system is the number (4 6) 10 written in the same numbers, but in
reverse order?
159*. Which is greater: the unit of the 8th digit in the binary system or the unit of the 4th digit in the octal system?
§ 10. PASCAL'S THEOREM. SIGNS OF DIVISIBILITY
BASIC INFORMATION FROM THE THEORY
10. 1. Pascal's theorem (1623 – 1662).
Natural numbers are given: t > 1and n, written in t-ary system:
,where a i are numbers: a iÎ N, 0 £ a i £ t–1 (i = 0,1, 2,…, k), tÎ N, t > 1.
Let n= (a k a k - 1 … a 1 a 0) 10 = a k×10 k +a k - 1×10 k- 1 +…+a 1×10+ a 0 , m=3 and m = 9.
1) Find b i: modulom = 3modulom = 9
10 0 º1(mod3), i.e. b 0 =1, 10 0 º1(mod9), i.e. b 0 =1,
10 1 º1(mod3), i.e. b 1 =1, 10 1 º1(mod9), i.e. b 1 =1,
10 2 º1(mod3), i.e. b 2 =1, 10 2 º1(mod9), i.e. b
Complete billing system. The given system of deductions. The most common deduction systems are: least positive, least non-negative, absolutely least, etc.
Theorem 1. Properties of the complete and reduced system of residues.
1°. Criteria for a complete system of deductions. Any combination of m integers that are pairwise incomparable modulo m, forms a complete system of residues modulo m.
2°. If numbers x 1 , x 2 , ..., x m– complete system of residues modulo m, (a, m) = 1, b is an arbitrary integer, then the numbers ax 1 +b, ax 2 +b, ..., ax m+b also constitute a complete system of residues modulo m.
3°. Criterion of the Reduced Reduction System. 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 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 the reduced system of residues modulo m.
Theorem 2. Euler's theorem.
If numbers a and m coprime, 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 decision. Equivalence. The degree of comparison.
Theorem. Properties of solutions of congruences.
1°. Solutions of congruences are entire classes of residues.
2°. (" k)(a k º b k(mod m))Ù k= z of the comparison º 0 (mod m) and º 0 (mod m) are equivalent.
3°. If both parts of the comparison are multiplied by a number coprime with the modulus, then a comparison is obtained that is equivalent to the original one.
4°. Any comparison modulo a prime p is equivalent to a comparison, the degree of which does not exceed p–1.
5°. Comparison º 0 (mod p), where p is a prime number, has at most n various solutions.
6°. Wilson's theorem. ( n-one)! º –1 (mod n) Û n Prime number.
§ 5. Solving comparisons of the first degree
ax º b(mod m).
Theorem. 1°. If a ( a, m) = 1, then the comparison has a solution, and it is unique.
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 modulo residues.
Ways to solve comparisons ax º b(mod m) when ( a, m) = 1:
1) selection (enumeration of elements of a complete system of deductions);
2) use of Euler's theorem;
3) use of the Euclid algorithm;
4) variation of the coefficients (using property 2° of the complete system of residues from Theorem 2.2);
§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 some 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 system of complex numbers 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 a = (a, 0).
Algebraic form of a complex number
Representation of a complex number in the form 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 .
Extracting square roots from complex numbers in algebraic form.
part of the complete system of residues (See. Complete system of residues), consisting of numbers coprime with modulus m. P. s. in. contains φ( m) numbers [φ( m) is the number of numbers coprime with m and smaller m]. Any φ( m) numbers that are not comparable in modulo m and coprime with it, form P. s. in. for this module.
- - see Reduced mass...
Physical Encyclopedia
- - conditional characteristic of the distribution of masses in a moving mechanical. or mixed system, depending on physical. parameters of the system and from the law of its motion...
Physical Encyclopedia
- - modulo m - any set of integers that are incomparable modulo one. Usually as P. with. in. modulo the smallest non-negative residues 0, 1, . . ...
Mathematical Encyclopedia
- - the sum of the usable area of an apartment building, as well as the areas of loggias, verandas, balconies with the corresponding reduction factors - the total area is given - přepočtená užitková plocha - Gesamtfläche - fajlagos alapterület - hörvüulsen...
Construction dictionary
- - See the coefficient of porosity of rocks ...
- - the ratio of the pore volume of the rock to the volume of the rock skeleton, usually expressed in fractions of a unit ...
Dictionary of hydrogeology and engineering geology
- - see porosity coefficient...
Explanatory Dictionary of Soil Science
- - the same as the base part...
- - a conditional character of the distribution of masses in a system of moving bodies, introduced in mechanics to simplify the equations of motion of the system ...
Big encyclopedic polytechnic dictionary
- - Tax levied at source on dividends or other income received by a non-resident of the country...
Financial vocabulary
- - Tax levied at source on dividends or other income received by a non-resident of the country...
Glossary of business terms
- - modulo m, any collection of integers containing one number from each class of numbers modulo m. As P. with. in. the most commonly used system of least positive residues 0, 1, 2,.....
- - a conditional characteristic of the distribution of masses in a moving mechanical or mixed system, depending on the physical parameters of the system and on the law of its motion ...
Great Soviet Encyclopedia
- - REDUCED mass - a conditional characteristic of the distribution of masses in a moving mechanical or mixed system, depending on the physical parameters of the system and on the law of its motion ...
Big encyclopedic dictionary
- - general, all, cumulative, ...
Synonym dictionary
- - adj., number of synonyms: 1 pure ...
Synonym dictionary
"Reduced system of deductions" in books
What is the present value of the core competencies?
From the book Weightless Wealth. Determine the value of your company in the intangible asset economy author Thyssen ReneWhat is the present value of the core competencies? Based on the above, we can say that the present value of a core competency is calculated by multiplying all the indicators for a certain time, taking into account the cost of attracting
Net Present Value (NPV)
From the MBA book in 10 days. The most important program of the world's leading business schools author Silbiger StephenNet present value (NPV) Present value (NPV) analysis helps to calculate how much an employee needs to invest in order to receive a decent pension in 30 years, but this analysis is not useful in assessing current investments and projects. Investments must be valued in
ACCOUNTING FOR DETAILS AND DEDUCTIONS FROM SALARY
From the book Accounting author Melnikov IlyaRECOGNITION OF DETAILS AND DEDUCTIONS FROM WAGES In accordance with the legislation, the following deductions are made from the wages of employees: - income tax (state tax, object of taxation - wages);
10.6. Accounting for deductions and deductions from wages
From the book Accounting in agriculture author Bychkova Svetlana Mikhailovna10.6. Accounting for deductions and deductions from wages Certain deductions are made from the wages of employees of the enterprise, which are divided as follows: mandatory deductions (tax on personal income, deductions on enforcement orders);
From the book Intangible Assets: Accounting and Tax Accounting the author Zakharyin V R<...>
4.1. General issues of granting social tax deductions
author Makurova Tatiana4.1. General issues of providing social tax deductions Social tax deductions (Article 219 of the Tax Code), as well as a property deduction for the purchase of housing, mean a decrease in the taxable base by the amount of social expenses incurred, taking into account the legislation
4.3. Features of the provision of educational deductions
From the book Self-Tutorial on Personal Income Taxes author Makurova Tatiana4.3. Peculiarities of granting educational deductions 142) What expenses can be accepted as a deduction for education? What are the limits of educational deductions? The following are accepted for the social tax deduction for education: expenses in the amount paid by the taxpayer in
3.4. Quantification and frequency of occurrence and application of tax deductions
From the book The tax burden of an enterprise: analysis, calculation, management author Chipurenko Elena Viktorovna3.4. Quantification and frequency of occurrence and application of tax deductions 3.4.1. VAT as a potential tax deduction When calculating VAT, the amounts of tax deductions are determined only in accordance with the data of tax accounting registers - purchase books. At
Complete system of deductions
From the book Great Soviet Encyclopedia (PO) of the author TSBReduced mass
TSBThe reduced system of deductions
From the book Great Soviet Encyclopedia (PR) of the author TSB88. Structural and reduced forms of a system of simultaneous equations. Model identification
From the book Answers to Exam Tickets in Econometrics author Yakovleva Angelina Vitalievna88. Structural and reduced forms of a system of simultaneous equations. Model identification Structural equations are the equations that make up the original system of simultaneous equations. In this case, the system has a structural form. Structural form
From the book New in the Tax Code: a commentary on the changes that entered into force in 2008 author Zrelov Alexander PavlovichArticle 172. Procedure for applying tax deductions
author author unknownArticle 172
From the book Tax Code of the Russian Federation. Parts one and two. Text with amendments and additions as of October 1, 2009 author author unknownArticle 201. The procedure for applying tax deductions