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 (m Î N, t> 1).
Designation of a class of numbers that have a remainder r: .
Every number from the class is called a residue modulo m, and the class itself called the class of residues modulo m.
6. 2. Properties of the set of classes of residues modulo 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) "butÎ : butº r(mod m);
4) "a, bÎ : butº b(mod m), that is, any two deductions taken from one class, comparable modulo t;
5) "butÎ , " bÎ : but b(mod m), that is, no two deductions; taken from different classes, incomparable modulo t.
6. 3. Definition 3.
Any set of m numbers taken one and only one from each class of residues modulo m is called a complete system of residues modulo m.
Example: if a m= 5, then (10, 6, - 3, 28, 44) is a complete system of residues mod 5 (moreover, not the only one!)
In particular,
the set (0, 1, 2, 3, ..., m–1) is a system smallest non-negative deductions;
the set (1, 2, 3, ..., m –1, t) Is the system least positive deductions.
6. 4. Note that:
if a ( x 1 , x 2 , … , x t) Is a 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 the number m: "a, bÎ Þ ( but; t) = (b; t).
6. 7. Definition 4.
Deduction class modulo m is called coprime with modulus m,if at least one deduction of this class is coprime with t.
Note that in this case, by Theorem 2 everything the numbers of this class will be coprime with the modulus t.
6. 8. Definition 5.
A reduced system of residues for a given module m is a system of residues taken one and only one from each class, coprime with the module 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 residue classes:
Z 10 = (,,,,,,,,,) is the set of residue classes modulo 10. Full deduction system mod 10 will be, for example, like this: (0, 1, 2, 3, 4, 5, 6, 7, 8, 9).
Many classes of deductions, mutually simple with module m = 10: (,,,) (j (10) = 4).
Reduced system of deductions modulo 10 will 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 compose one of the possible reduced systems of residues 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
(but, 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.
The sum( Å ) deduction classes and +b equal to the sum of any two deductions, one taken from each given class, and : Å = , Where"butÎ , "bÎ .
6.13. Definition 7.
By product( Ä ) deduction classes and modulo m is the class of residues , that is, a residue class consisting of numbers a ´ b equal to the product of any two deductions, one taken from each given class, and : Ä = , Where"butÎ , "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 m modulo m is an associative commutative ring with unity:
< Z t , +, · > = < { , , ,…, }, +, · > – ring.
TYPICAL TASKS
1. Make modulo t= 9:
1) a complete system of least positive residues;
2) a complete system of least non-negative residues;
3) an arbitrary complete system of residues;
4) a complete system of the smallest in absolute value residues.
Answer:1) {1, 2, 3, 4, 5, 6, 7, 8, 9}; 2) {0, 1, 2, 3, 4, 5, 6, 7, 8};
2. Make a reduced system of residues modulo t= 12.
Decision.
1) We 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) Delete from this system numbers that are not coprime to 12:
{1, 2 , 3 , 4 , 5, 6 , 7, 8 , 9 , 10 , 11, 12 }.
3) The remaining numbers, coprime to 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 least positive deductions; 2) a complete system of least non-negative residues; 3) an arbitrary system of deductions; 4) a complete system of the smallest in absolute value deductions; 5) 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 deductions modulo m if a) m= 9; b) m= 24; in) m= 7. How many numbers should such a system contain?
134. Formulate the basic properties of the complete system of residues and the reduced system of residues modulo m .
135. What elements differ in the reduced and complete systems of least nonnegative residues modulo a simple modulus?
136. Under what condition the numbers but and - but belong to the same class of residues modulo m?
137. What classes of residues modulo 8 belong to all primes 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. To how many classes of residues mod 21 belong all the residues from one class of residues mod 7?
140. The set of integers Z distribute by classes of residues modulo 5. Make tables of addition and multiplication in the resulting set of classes of residues Z five . Is the set Z 5: a) a group with the operation of class addition? b) a group with the operation of class multiplication?
§ 7. EULER'S THEOREM. SMALL FARM THEOREM
BASIC INFORMATION FROM THE THEORY
7. 1. Theorem 1.
If aÎ Z,tÎ N, t>1 and(but;t) = 1, - then in an infinite sequence of degrees a 1 , but 2 , but 3 , ... , but s, ..., but t, ... there are at least two degrees with exponents s and t(s<t) such that 
. (*)
7. 2. Comment... By designating t– s = k> 0, from (*) we get: 
... Raising both sides of this comparison to the power nÎ N, we get: 
(**). This means that there is an infinite number of powers of the number a satisfying the comparison (**). But as find these indicators? What least indicator satisfying comparison (**)? The first question is answered Euler's theorem(1707 – 1783).
7. 3. Euler's theorem.
If aÎ Z,tÎ N, t>1 and(but;t) = 1, - then 
. (13)
Example.
Let be but = 2,t = 21, (but; 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 12 - the smallest satisfying comparison 2 nº 1 (mod 21)? It turns out not. The smallest indicator will be P= 6: 2 6 º 1 (mod 21), because 2 6 - 1 = 63, and 63 21. Note that least indicator should be looked for only among the divisors of the 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 be but = 3,R= 5, where 3 is not 5. Then 
or 
.
7. 5. Generalized Fermat's theorem.
For any prime number p and an arbitrary number aÎ Z there is a comparison 
(15)
TYPICAL TASKS
1. Prove that 38 73 º 3 (mod 35).
Decision.
1) Since (38; 35) = 1, then by Euler's theorem 
; j (35) = 24, so
(1).
2) From comparison (1) by Corollary 2 of property 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) , as required.
2. Given: but = 4, t= 15. Find the smallest exponent k satisfying the comparison 
(*)
Decision.
1) Since ( a; m) = (4; 25) = 1, then by Euler's theorem 
, j (25) = 20, therefore 
.
2) Is the exponent found - the number 20 - the smallest a natural number satisfying the comparison (*)? If there is an exponent less than 20, then it must be a divisor of 20. This means that the desired smallest exponent k you need to search among the set 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, the smallest exponent k satisfying the comparison (*) is k= 10.
Answer: 
.
EXERCISES FOR INDEPENDENT WORK
141. By Euler's theorem 
... When but = 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 (totally !?). 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 but j ( m) º 1 (mod m), then ( a, m) =1.
145. Find the smallest exponent kÎ N, satisfying this comparison: a) 
; b) 
; in) 
; d) 
;
e) 
; e) 
; g) 
; h) 
.
and) 
; to) 
; l) 
; m) 
.
146. Find the remainder of the division:
a) 7 100 by 11; b) 9 900 by 5; c) 5,176 by 7; d) 2 1999 to 5; e) 8 377 by 5;
f) 26 57 to 35; g) 35 359 to 22; h) 5,718 to 103; i) 27 260 by 40; j) 25 1998 to 62.
147 *. Prove that but 561 º but(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 with 1. Prove.
149 *. Prove that 2 64 º 16 (mod 360).
150 *. Prove: if ( but, 65) =1 , (b, 65) = 1, then a 12 –b 12 is divisible by 65 without remainder.
Chapter 3. ARITHMETIC APPENDICES
NUMERICAL COMPARISON THEORY
§ 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) – non-negative integers - digits, moreover 0 £ a i £ t– 1, t - base of the number system, tÎ N, t> 1.
For example, writing 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 don't write.
8. 3. Theorem 1.
Any non-negative integer number can be represented, moreover, 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) assigning 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 to multiplication this number on 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 translating a number written int -ary system, in 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 translating a number written in decimal system int - personal:
Example: (3 9 1) 10 = (x) 12 . To find x.
8. 7. Actions on systematic numbers
2. SYSTEMATIC FRACTIONS
8. 8. Definition 3.
A finite t-ary systematic fraction in the base t system is a number of the form
where c 0 Î Z, with i - digits– non-negative integers, moreover 0 £ with i£ t– 1, tÎ N, t> 1, kÎ N .
Designation: a = ( c 0 , from 1 from 2 …with k)t... When t= 10 the fraction is called decimal.
8. 9. Corollary 1.
Any 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. Generally speaking, the converse statement is not true. For example, a fraction cannot be converted to a final systematic (decimal) fraction.
8.10. Definition 4.
An infinite t-ary positive systematic fraction in the base t system is a number of the form
, where c 0Î N, with i(i =1, 2, …, to, …) - numbers– non-negative integers, moreover 0 £ with i£ t–1, tÎ N, t> 1, kÎ N.
Designation: a = ( from 0 , from 1 from 2 … with k…) t... When t= 10 the fraction is called decimal.
8.11. Definition 5.
There are three types of infinite systematic fractions:
I a = ( from 0 , 
)t= = 
t where = = = … In this case, the number a is called an infinite purely periodic fraction,(from 1 from 2 … with k) – period, k - the 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 = ( from 0 , from 1 from 2 … with k …)t . In this case, the number a is called an infinite non-periodic fraction.
TYPICAL TASKS
1. Number ( but) 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 .
Decision.
1) Convert the given number (2 1 4 3) 5 to the number ( at) 10, written in decimal:
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.
Decision.
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 we write, 1 goes into the next category, 6 + 3 + 1 = 10 = 1 × 6 + 4, 4 we write, 1 goes into the next category, 3 + 4 + 1 = 8 = 1 × 6 + 2, write 2, 1 goes to the next digit. |
| 4) (5 2 3 4) 7 – (2 3 5 1) 7 (2 5 5 3) 7 | Note: | we "occupy" a unit of the highest category, that is, "1" = 1 × 7: (3 + 1 × 7) - 5 = 10 - 5 = 5, (1 + 1 × 7) - 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 multiplied by 2: 3 × 2 = 6 = 1 × 5 + 1, 1 we write, 1 goes to the next bit, 2 × 2 + 1 = 5 = 1 × 5 +0, 0 we write, 1 goes to the next bit, 2 × 4 + 1 = 9 = 1 × 5 + 4, 4 we write, 1 goes to the next digit, When multiplied by 3: 3 × 3 = 9 = 1 × 5 + 4, 4 we write, 1 goes to the next digit, 3 × 2 + 1 = 7 = 1 × 5 +2, 2 we write, 1 goes to the next category, 3 × 4 + 1 = 13 = 2 × 5 +3, 3 we write, 2 goes to the next category. |
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 decimal system, convert to t-echnical system. Check it out.
a) (1 3 2) 10 = ( x) 7; b) (2 9 8) 10 = ( x) five ; 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 ;
and) (1 0 0 1 5) 10 = ( x) twenty ; j) (9 2 5) 10 = ( x) eight ; l) (6 3 3) 10 = ( x) fifteen ; m) (1 4 3) 10 = ( x) 2 .
153. Numbers given in t-parallel system, translate into q-ichny system (by going through the decimal system).
a) (3 7) 8 = ( x) 3; b) (1 1 0 1 1 0) 2 = ( x) five ; c) (6 2) 11 = ( x) 4 ;
d) (4) 12 = ( x) nine . e) (3 3 1 3 1) 5 = ( x) 12 .
154. a) How will the number (1 2 3) 5 change if zero is attributed 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. Do the following:
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; l) (7 4 1) 8 × (2 6) 8; m) (5 3 7 2) 8 × (2 4 6) 8;
n) (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; m) (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.
c) (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 the 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 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-
fraction.
The period length 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 an infinite periodic decimal fraction;
any infinite non-periodic decimal fraction is an irrational number.
TYPICAL TASKS
1. These ordinary fractions, written in the decimal system, convert to
decimal, preliminarily 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).
Decision.
1) Fraction = denominator - number b= 80 = 2 4 × 5 contains only "2" and "5". Therefore, this fraction is transformed into the final decimal fraction. Number of decimal places l naim is 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 transformed into an infinite purely periodic decimal fraction. Period length k naim is determined from the condition: 10 kº1 (mod27):
3) Fraction = denominator - number b= 24 = 2 3 × 3, that is, it has the form: b = b "× b 1 (except for "2" or "5" contains other factors, in this case the number 3). Therefore, this fraction is transformed into an infinite mixed batch decimal fraction. Period length k naim is determined from the condition: 10 kº1 (mod3), whence k naim= 1, that is, the length of the period k= 1. Preperiod length l naim is determined from the condition: 10 lº0 (mod8), whence l naim= 3, that is, the length of the pre-period l = 3.
Verification: divide 5 by 24 with a "corner" 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 decimal system, convert to decimal fractions. If the decimal fraction is periodic, then preliminarily find the number k- period length and number l is the length of the pre-period.
157. These ordinary fractions, written in the decimal system, convert to t-similar systematic fractions. Find the numbers k is the length of the period and l is the length of the pre-period.
158 *. In which number system is the number (4 6) 10 written in the same digits, but in
reverse order?
159 *. Which is bigger: 8th bit unit in binary system or 4th bit unit in octal system?
§ 10. PASCAL'S THEOREM. SIGNS OF SEPARABILITY
BASIC INFORMATION FROM THE THEORY
10. 1. Pascal's theorem (1623 – 1662).
Natural numbers are given: m> 1and n, written in t - ary system:
,where a i - - digits: a iÎ N, 0 £ a i £ t–1 (i = 0,1, 2,…, k), tÎ N, t> 1.
Let be 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 = 3by modulem = 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), that is, b 1 =1,
10 2 º1 (mod3), i.e. b 2 = 1, 10 2 º1 (mod9), that is, b
Usually, as a complete system of residues modulo m take the smallest non-negative residues
0,1,...,m − 1or the absolutely least residue consisting of numbers
,in case of odd m and numbers
in case of even m .
see also
Literature
- I. M. Vinogradov Fundamentals of number theory. - M.-L .: State. ed. technical and theoretical literature, 1952. - 180 p.
Wikimedia Foundation. 2010.
See what the "Complete system of deductions" is in other dictionaries:
Modulo m, any collection of integers containing one number from each class of numbers modulo m (two integers a and b belong to the same class modulo m if a b is divisible by m; see Residue). As P. with. in. most often… …
Modulo m any set of integers modulo m-incomparable. Usually as P. with. in. modulo the smallest non-negative residues 0, 1,. ... ., m 1 or absolutely the smallest residues consisting of the numbers 0, +1,. ... ., in… … Encyclopedia of mathematics
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
Comparison modulo a natural number n in number theory is an equivalence relation on the 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
In number theory, the comparison [to clarify] modulo a natural number n is an equivalence relation on the set of integers given by the designated number, associated with divisibility by it. The factor space in this relation is called "a ring ... ... Wikipedia
The symmetry of a snowflake is associated with a group of rotations by an angle that is a multiple of 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
The function to paradise can be represented by a power series. Eliminates the importance of class A. f. is defined as follows. Firstly, this class is quite wide: it covers most of the functions found in basic questions of mathematics and its ... ... Encyclopedia of mathematics
I Contents: I. Primary public education in general. II. Primary public education abroad: Austria Hungary, England, Belgium, Bulgaria, Germany, Holland, Denmark, Spain, Italy, Norway, Portugal, Romania, Serbia, ... ... Encyclopedic Dictionary of F.A. Brockhaus and I.A. Efron
- - was born on May 26, 1799 in Moscow, on Nemetskaya Street in the Skvortsov house; died on January 29, 1837 in St. Petersburg. From his father's side, Pushkin belonged to an old noble family, descended, according to the legend of genealogies, from a native "from ... ... Big biographical encyclopedia
A set of closed formulas of the 1st stage predicate logic. E. T. Th (K) of the class K of algebraic systems of signature is called. the set of all closed formulas of the predicate logic of the 1st stage of the signature, which are true on all systems from the class K. If the class ... ... Encyclopedia of mathematics
Clause 17. Complete and reduced deduction systems.
In the previous paragraph, it was noted that the relation є m comparability modulo m is an equivalence relation on the set of integers. This equivalence relation induces a partition of the set of integers into classes of elements equivalent to each other, i.e. numbers are combined into one class that give, when divided by m the same residues. Equivalence Classes є m(experts will say - "equivalence index є m") is exactly equal to m .
Definition. Any number from the equivalence class є m will be called the modulo residue m... A set of deductions taken one at a time from each equivalence class є m, is called a complete system of residues modulo m(in the complete system of deductions, thus, total m pieces of numbers). Directly the remainders themselves when divided by m are called the least non-negative residues and, of course, form a complete system of residues modulo m... A residue r is called absolutely smallest if п-п is the smallest among the modules of residues of a given class.
Example: Let be m= 5. Then:
0, 1, 2, 3, 4 - the smallest non-negative residues;
2, -1, 0, 1, 2 are absolutely the smallest residues.
Both the given collections of numbers form complete systems of residues modulo 5 .
Lemma 1. 1) Any m pieces pairwise incomparable modulo m numbers form a complete system of residues modulo m .
2) If but and m are mutually simple, and x m, then the values of the linear form ax + b where b- any integer, also run through the complete system of residues modulo m .
Evidence. Part 1) is obvious. Let us prove assertion 2). Numbers ax + b smooth m pieces. Let us show that they are not comparable with each other modulo m... Well let it be for some different x 1 and x 2 from the complete system of deductions it turned out that ax 1 + b є ax 2 + b (mod m)... Then, according to the properties of comparisons from the previous paragraph, we get:
ax 1 є ax 2 (mod m)
x 1 є x 2 (mod m)
- a contradiction with the fact that x 1 and x 2 are different and are taken from the complete deduction system.
Since all numbers from a given equivalence class є are obtained from one number of a given class by adding a multiple of m, then all numbers from this class have modulus m same greatest common factor. For some reasons, those deductions that have with the module m greatest common divisor equal to one, i.e. deductions that are relatively simple with the modulus.
Definition. The reduced system of residues modulo m is the set of all residues from the complete system, coprime to the modulus m .
The reduced system is usually chosen from the smallest non-negative residues. It is clear that the reduced system of residues modulo m contains j ( m) number of residues, where j ( m) Is the Euler function - the number of numbers less than m and mutually simple with m... If by this point you have already forgotten the Euler function, take a look at point 14 and make sure that something was said about it.
Example. Let be m= 42. Then the reduced system of residues is:
1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.
Lemma 2. 1) Any j ( m) numbers that are pairwise incomparable modulo m and coprime with the modulus, form a reduced system of residues modulo m .
2) If (a, m) = 1 and x runs the reduced system of residues modulo m then ax also runs the reduced system of residues modulo m .
Evidence. Part 1) is obvious. Let us prove assertion 2). The numbers ax are pairwise incomparable (this is proved in the same way as in Lemma 1 of this subsection), there are exactly j ( m) pieces. It is also clear that they are all coprime to the module, because (a, m) = 1, (x, m) = 1 10 (ax.m) = 1... Hence the numbers ax form the reduced system of deductions.
These are the definitions and basic properties of the complete and reduced systems of residues, however, in the baggage of mathematical knowledge there is still a number of very interesting and useful facts concerning deduction systems. If you keep silent about them at this point, then I am afraid it will be a direct violation of the Law. Russian Federation Information, the malicious withholding of which is, according to this law, an administrative and even a criminal offense. In addition, without acquaintance with the further important properties of deduction systems, paragraph 17 will turn out to be very short. Let's continue.
Lemma 3. Let be m 1, m 2, ..., m k- are pairwise coprime and m 1 m 2 ... m k = M 1 m 1 = M 2 m 2 = ... = M k m k where
1) If x 1, x 2, ..., x k run through complete deduction systems by modules m 1, m 2, ..., m k respectively, then the values of the linear form M 1 x 1 + M 2 x 2 + ... + M k x k run through the complete system of residues modulo m = m 1 m 2 ... m k .
2) If x 1, x 2, ..., x k run the reduced systems of deductions by modules m 1, m 2, ..., m k respectively, then the values of the linear form M 1 x 1 + M 2 x 2 + ... + M k x k run the reduced system of residues modulo m = m 1 m 2 ... m k .
Evidence.
1) Form M 1 x 1 + M 2 x 2 + ... + M k x k takes obviously m 1 m 2 ... m k = m values. Let us show that these values are pairwise incomparable. Well let
M 1 x 1 + M 2 x 2 + ... + M k x k є M 1 x 1 C + M 2 x 2 C + ... + M k x k C (mod m)
Anything M j other than M s, multiple m s... Removing the left and right terms in the last comparison, multiples m s, we get:
M s x s є M s x s С (mod m s) Ю x s є x s С (mod m s)
- a contradiction with the fact that x s runs the complete system of residues modulo m s .
2). The form M 1 x 1 + M 2 x 2 + ... + M k x k obviously takes j ( m 1) j ( m 2) H ... H j ( m k) = j ( m 1 m 2 H ... H m k) = j ( m) (Euler's function is multiplicative!) different values, which are among themselves modulo m = m 1 m 2 ... m k are pairwise incomparable. The latter is easily proved by arguments similar to those used in the proof of part 1) of this lemma. As ( M 1 x 1 + M 2 x 2 + ... + M k x k, m s) = (M s x s, m s) = 1 for each 1 Ј s Ј k, then ( M 1 x 1 + M 2 x 2 + ... + M k x k, m s) = 1, hence the set of values of the form M 1 x 1 + M 2 x 2 + ... + M k x k forms a reduced system of residues modulo m .
Lemma 4. Let be x 1, x 2, ..., x k, x run through full, and x 1, x 2, ..., x k, x- run the reduced systems of deductions by modules m 1, m 2, ..., m k and m = m 1 m 2 ... m k respectively, where (m i m j) = 1 at i no j... Then the fractions (x 1 / m 1 + x 2 / m 2 + ... + x k / m k) coincide with fractions (x / m), and fractions (x 1 / m 1 + x 2 / m 2 + ... + x k / m k) coincide with fractions (x / m) .
Evidence. The proofs of both assertions of Lemma 4 can be easily obtained by applying the previous Lemma 3 after you give each sum (x 1 / m 1 + x 2 / m 2 + ... + x k / m k) and (x 1 / m 1 + x 2 / m 2 + ... + x k / m k) to a common denominator:
(x 1 / m 1 + x 2 / m 2 + ... + x k / m k) = ((M 1 x 1 + M 2 x 2 + ... + M k x k) / m) ;
(x 1 / m 1 + x 2 / m 2 + ... + x k / m k) = ((M 1 x 1 + M 2 x 2 + ... + M k x k) / m) ,
Where M j = m 1 ... m j-1 m j + 1 ... m k .
If we now take into account that the fractional parts of the numbers obtained when dividing by the modulus m any two numbers comparable modulo m, are the same (they are equal r / m where r Is the smallest non-negative residue from this class), then the statements of this lemma become obvious.
In the rest of this section, the most interesting thing will happen - we will sum up the complex roots m-th degree of unity, in this case we will discover striking connections between the sums of roots, systems of residues, and the already familiar multiplicative Mobius function m ( m) .
We denote by e k k th root m- 1st degree of unity:
We remember these forms of writing complex numbers well from the first year. Here k = 0,1, ..., m-1- runs through the complete system of residues modulo m .
Let me remind you that the amount e 0 + e 1 + ... + e m-1 all roots m-th degree of unity is zero for any m... Indeed, let e 0 + e 1 + ... + e m-1 = a... We multiply this sum by a nonzero number e 1. Such multiplication geometrically in the complex plane means a rotation of the correct m-gons with roots at the vertices e 0, e 1, ..., e m-1, at a nonzero angle 2 p / m... It is clear that in this case the root e 0 will go to the root e 1, root e 1 will go to the root e 2, etc., and the root e m-1 will go to the root e 0, i.e. sum e 0 + e 1 + ... + e m-1 Will not change. We have e 1 a = a from where a = 0 .
Theorem 1. Let be m> 0- an integer, a О Z , x runs the complete system of residues modulo m... Then if but multiples m then
otherwise, for but not a multiple m ,
.
Evidence. When but multiple m we have: a = md and
When but not divisible by m, divide the numerator and denominator of the fraction a / m on the d- greatest common factor but and m, we get an irreducible fraction a 1 / m 1... Then, by Lemma 1, a 1 x will run through the complete system of residues modulo m... We have:
because the sum of all the roots of the degree m 1 of one is zero.
Let me remind you that the root e k m-th degree of unity is called antiderivative if its index k coprime with m... In this case, as proved in the first year, successive degrees e k 1, e k 2, ..., e k m-1 root e k form the entire set of roots m-th degree of unity or, in other words, e k is the generator of the cyclic group of all roots m-th degree of one.
Obviously, the number of distinct primitive roots m-th power of unity is equal to j ( m), where j is the Euler function, since the indices at the primitive roots form a reduced system of residues modulo m .
Theorem 2. Let be m> 0 Is an integer, x runs over the reduced system of residues modulo m... Then (the sum of antiderivative roots of degree m):
where m ( m) Is the Mobius function.
Evidence. Let be m = p 1 a 1 p 2 a 2 ... p k a k- canonical number decomposition m ; m 1 = p 1 a 1 , m 2 = p 2 a 2 , m 3 = p 3 a 3; x i runs the reduced system of residues modulo m i... We have:
When a s = 1 it turns out that only the root e 0 = 1 is not an antiderivative, so the sum of all antiderivative roots is the sum of all roots minus one:
so if m square-free (i.e. not divisible by r 2, at r> 1), then
If any indicator a s more than one (i.e. m divided by r 2, at r> 1), then the sum of all primitive roots of degree m s is the sum of all the roots of the degree m s minus the sum of all non-primitive roots, i.e. all roots of some degree less m s... Namely, if m s = p s m s * then:
Now, dear readers, when I have submitted for your consideration a fairly significant amount of information about the complete and reduced systems of deductions, no one can accuse me of maliciously violating the Law of the Russian Federation on Information by hiding it, so I am finishing this paragraph with satisfaction.
| Tasks |
1 ... Write on a piece of paper all the smallest non-negative residues and all the absolutely smallest residues. a) mod 6, b) mod 8. Below, write out the systems of deductions for these modules. Draw separately on the complex plane the roots of the sixth and the roots of the eighth degree from unity, in both figures circle the primitive roots and find in each case their sum. 2 ... Let be e- antiderivative root of degree 2n from one. Find the amount: 1+ e + e 2 + ... + e n-1 . 3 ... Find the sum of all primitive roots: a) 15th; b) the 24th; c) 30th degree of unity. 4 ... Find the sum of all possible products of primitive roots n-th degree of one, taken two at a time. 5 ... Find the amount k-x degrees of all roots n-th degree of one. 6 ... Let be m> 1 , (a, m) = 1 , b- an integer, x runs through the complete, and x is the reduced system of residues modulo m... Prove that: but) b) 7 ... Prove that:
Where R runs over all prime factors of a number but . |
,Definition. Numbers form a complete system of residues modulo if any integer is comparable modulo one and only one of these numbers.
Any complete system of residues modulo consists of numbers that are pairwise incomparable modulo.
Theorem. Let be a complete system of residues modulo. Let be an integer coprime with. Then - also a complete system of residues modulo.
Evidence. It is necessary to prove that these numbers are pairwise incomparable modulo. Suppose the opposite. Let be
Since gcd, what is contrary to the condition.
Theorem. Let be a complete system of residues modulo. Let be an integer. Then - also a complete system of residues modulo.
Lemma. If, then GOD GOD.
Evidence.
Is an integer.
From here. Any common divisor is a divisor. Hence the GCD GCD.
Definition. Numbers form a reduced system of residues modulo if they are coprime with and any integer coprime with is comparable to one and only one of these numbers modulo.
Example. Reduced system of deductions modulo 10: 1,3,7,9.
Lemma. All the reduced systems of residues modulo consist of the same number of numbers, which is denoted as the Euler function.
Evidence. Indeed, let there be two reduced systems of residues modulo, consisting of different numbers of numbers:
Then, since the numbers form a reduced system of residues modulo, each of the numbers is comparable to one and only one of these numbers. Since, then, according to the Dirichlet principle, at least two numbers from will be comparable with some number, which means they will be comparable in absolute value to each other. And this contradicts the fact that - the reduced system of residues modulo. Hence,.
Let us now prove that. Indeed, numbers that are less than and coprime to c form a reduced system of residues modulo. This follows from the lemma.
Definition. Euler's function (or totent) denotes the number of numbers that are less than and coprime to.
Theorem. If is a reduced system of residues modulo and is a coprime number with, then is also a reduced system of residues modulo.
If - simple, then.
Lemma. If - simple, then.
Evidence. Indeed, there are only numbers less than a prime and having a common divisor with it.
Lemma. Let the GCD. Then. Euler's function is multiplicative.
Evidence. Let's write all the numbers from 1 to as follows:
The numbers in each line form a complete system of residues modulo. Hence, mutually simple with among them. Moreover, these numbers are arranged in columns - one under the other, since each column contains numbers that are comparable in absolute value.
The numbers in each column form a complete system of residues modulo. Indeed, the th column is obtained by taking the numbers that form a complete system of residues modulo, multiplying them by a number coprime to, and adding to each of them.
Thus, in each column there are exactly numbers that are coprime to.
Since a number will be coprime with if and only if it is mutually simple with and mutually simple with, then the number of numbers that are coprime with is equal.
Theorem. Let be
Canonical decomposition of a number. Then
Evidence. By the lemma on the multiplicativity of the Euler function
Example.
Theorem (Euler). If and are coprime numbers, then
Let be some reduced system of residues modulo. ... Then is also a reduced system of residues modulo. Therefore, each of the numbers of the first sequence is comparable to one of the numbers of the second sequence modulo, and each of the numbers of the second sequence is comparable to one of the numbers of the first sequence. Then
Since each of the numbers is mutually simple with, the comparison can be shortened by them:
Consequence. Let - integers, - natural. If,, GCD, then.
Evidence. Let be . Since, then - a natural number. Then
Means, .
88question
Homotetia and the semblance of space
Homotetia with a center O and the coefficient k denote H k 0
The properties of transformations of homothety and similarity of space are similar to the properties of homothety and similarity of a plane, therefore, the study of the former should begin by repeating the latter. Similarity of space with coefficient k can be decomposed into a composition of motion and homothety with some center and the same coefficient.
Students should be aware that with such a transformation of space, the value of the angle (planar and dihedral) is preserved, parallel (perpendicular) straight lines and planes are mapped to parallel (perpendicular) lines and planes. This means that with such a transformation of space, the image of any figure is a figure that has the same shape as this figure, but differs from it only "in its dimensions."
Problem 12. Given a regular tetrahedron RAVS; points R 1 , BUT 1 , IN 1 , FROM 1 - the centers of its faces (Fig. 14). Prove that the tetrahedron R 1 BUT 1 IN 1 FROM 1 is like a tetrahedron RAVS; find the coefficient of this similarity.
Decision... Let the points H and K- the middle of the ribs, respectively AB and Sun tetrahedron RAVS, point BUT 1 - face center RVS, point R 1 - face center ABC(fig. 14). It means that
RA 1: BUT 1 K = AR 1: R 1 K = 2: 1,
BUT 1 K : PK = R 1 K : AK = 1: 3,
Similarly, one can prove that
A 1 B 1: AB= 1: 3 and A 1 B 1 AB,
A 1 C 1 : AS= 1: 3 and A 1 C 1 AS,
B 1 C 1 : Sun= 1: 3 and B 1 C 1 Sun,
B 1 R 1 : BP= 1: 3 and B 1 R 1 BP,
С 1 Р 1 : Wed= 1: 3 and С 1 Р 1 Wed.
From these ratios between the edges of the tetrahedra RAVS and R 1 A 1 B 1 C 1 it follows that the tetrahedron R 1 A 1 B 1 C 1- correct, therefore these tetrahedrons are similar; the coefficient of similarity is 1/3. (In profile classes, it is worth proving that these tetrahedra are homothetic.)
You can enter a definition: "The figure F 1 called like a figure F if there is a space similarity transformation displaying the figure F on the figure F 1". Then, to prove the similarity of the figure F 1 figure F it is enough to find at least one similarity transformation that the figure F maps to figure F 1..
Definition. Parallel transfer, or, in short, transfer of a figure, is such a display in which all its points are displaced in the same direction by equal distances, i.e. when transferring each two points X and Y of the figure, such points X "and Y" are matched that XX "= YY"
The main property of transfer:
Parallel translation preserves distances and directions; X "Y" = XY
Hence it follows that parallel transfer is a movement that preserves direction and vice versa, a movement that preserves direction is a parallel transfer
It also follows from these statements that the composition of parallel transfers is a parallel transfer
Parallel transfer of a figure is set by specifying one pair of corresponding points. For example, if it is indicated to which point A "this point A goes, then this translation is specified by the vector AA", which means that all points are shifted by the same vector, i.e. XX "= AA" for all X points
Central symmetry
Definition
Points A and A "are called symmetric with respect to point O if points A, A", O lie on one straight line and OX = OX ". Point O is considered symmetric to itself (with respect to O)
Two figures are called symmetric about point O if for each point of one figure there is a point symmetric to it about point O in another figure and vice versa
As a special case, a figure can be symmetrical to itself with respect to some point O. Then this point O is called the center of symmetry of the figure, and the figure is centrally symmetric
Definition
The central symmetry of a figure with respect to O is such a mapping of this figure, which assigns to each of its points a point symmetric with respect to O
Main property: Central symmetry maintains distance, but reverses direction. In other words, any two points X and Y of the figure F correspond to points X "and Y" such that X "Y" = -XY
Evidence. Suppose that with the central symmetry centered at point O, points X and Y are mapped to X "and Y". Then, as is clear from the definition of central symmetry, OX "= -OX, OY" = -OY
However, XY = OY - OX, X "Y" = OY "- OX"
Therefore, we have: X "Y" = -OY + OX = -XY
Hence it follows that central symmetry is a movement that changes direction to the opposite and vice versa, a movement that changes direction to the opposite is central symmetry
The central symmetry of the figure is specified by specifying one pair of existing points: if point A is mapped to A ", then the center of symmetry is the midpoint of segment AA"
Turn around a straight line
For a clearer idea of the turn around a straight line, remember the turn on a plane around this point. A rotation on a plane about a given point is a movement in which each ray emanating from a given point rotates by the same angle in the same direction. Now let's move on to a turn in space
Definition. Rotation of the figure around the straight line a by an angle (this is called such a mapping in which in each plane perpendicular to the straight line a, there is a rotation around the point of its intersection with the straight line a by the same angle (in the same direction. The straight line a is called the axis of rotation , and the angle is the angle of rotation)
From here we see that the rotation is always set by the axis, angle and direction of rotation.
Theorem 1. A rotation around a straight line preserves distances, that is, is a movement
Theorem 2. If the motion of space has a straight line with its set of fixed points, then it is a rotation around this straight line
Plane transformations
Deduction classes. Deduction systems
Summary of theory
By applying the remainder division theorem, the set of integers can be divided into a number of classes. Let's look at an example. Let be m = 6. Then we have six classes of partition of the set of integers modulo 6:
r = 1;
r = 2;
r = 3;
r = 4;
r = 5;
where through r denotes the remainder of dividing an integer by 6.
Let us recall the theorem on division with remainder:
Theorem: Divide number by number,, with remainder, then find a pair of integers q and r such that following conditions: 
.
It is easy to prove that for any integers but and division with remainder is possible and numbers q and r are uniquely determined. In our example, the complete system of least non-negative residues is the set (0, 1, 2, 3, 4, 5); complete system of least positive residues - set (0, 1, 2, 3, 4, 5); complete system of the smallest residues in absolute value - set (-2, -1, 0, 1, 2, 3); the reduced system of residues is the set (1,5), since; factor-set
One of the methods of performing arithmetic operations on given integers is based on simple provisions of number theory. The idea behind this method is that integers are represented in one of the non-positional systems - in the residual class system. Namely: instead of operations on integers, they operate with the remainders of dividing these numbers by preselected primes - modules 
.
Most often numbers selected from a variety of primes.
Let be 
…, 
.
Since the division theorem with remainder holds in the ring of integers, that is, where, then the ring Z, by definition, is Euclidean.
Thus, as numbers, you can choose the remainder of the division of the number BUT on the p i respectively.
The system of deductions allows performing arithmetic operations on a finite set of numbers without going beyond its limits. Complete deduction system modulo n- any set of n pairwise incomparable modulo n integers. Usually, as a complete system of residues modulo n take the smallest non-negative residues
Integer division a and m private q and the remainder r such that
a = m q + r, 0 r m-1. The remainder r are called DEDUCTION ohm modulo m.
For example, for m = 3 and for m = 5 we get:
| a = m q + r, m = 3 | a = m q + r, m = 5 |
| 0 = 3 + 0 | 0 = 5 + 0 |
| 1 = 3 + 1 | 1 = 5 + 1 |
| 2 = 3 + 2 | 2 = 5 + 2 |
| 3 = 3 + 0 | 3 = 5 + 3 |
| 4 = 3 + 1 | 4 = 5 + 4 |
| 5 = 3 + 2 | 5 = 5 + 0 |
| 6 = 3 + 0 | 6 = 5 + 1 |
| 7 = 3 + 1 | 7 = 5 + 2 |
If the remainder is zero ( r=0 ), then they say that m divides a whole (or m multiples a ), which means m a and the numbers q and m called divisors a ... Obviously 1 a and a a ... If a a has no divisors other than 1 and but then but - prime number, otherwise but called a composite number. Largest positive divisor d two numbers a and m called the greatest common divisor (GCD) and denote d = (a, m). If gcd (a, m) = 1 then a and m have no common divisors except 1 , and are called coprime relative to each other.
To each DEDUCTION at r = 0, 1, 2, ..., m-1 matches a set of integers a, b, ... They say that numbers with the same DEDUCTION ohm are comparable in modulus and denote a b (mod m) or (a b) m.
For example, for m = 3 :
For example, for m = 5 :
The numbers but which are comparable modulo m , form a class of their Deduction r and defined as a = m q + r.
The numbers but also called DEDUCTIONS modulo m ... Non-negative Deductions a = r (at q = 0 ) taking values from the interval , form a complete system of least residues modulo m.
Deductions but
taking values from the interval [-( ,…,( ]
, at odd m
or from the interval [-
at even m
form a complete system of absolutely smallest DEDUCTION ov modulo m.
For example, for m = 5 the least residue classes form
r = 0, 1, 2, 3, 4, a = -2, -1, 0, 1, 2. Both reduced sets of numbers form complete systems deduction ov modulo 5 .
Class Deductions whose elements are relatively simple with the module m
called reduced. Euler's function determines how much Deductions from the complete system of least residues modulo m are relatively simple with m ... With a simple m = p we have = p-1.
Definition... The maximum set of pairwise incomparable modulo m numbers coprime to m is called reduced system of deductions modulo m... Any reduced system of residues modulo m contains elements, where is the Euler function.
Definition. Any number from the equivalence class є m will call deduction ohm modulo m... The aggregate deduction s taken one from each equivalence class є m is called the complete system deduction ov modulo m(in full system deduction s, thus, total m pieces of numbers). Directly the remainders themselves when divided by m are called the smallest non-negative deduction ami and, of course, form a complete system deduction ov modulo m. Deduction r is called absolutely smallest if ïrï is the smallest among the modules deduction of this class.
Example... Check if the numbers 13, 8, - 3, 10, 35, 60 form a complete system of residues modulo m = 6.
Decision: By definition, numbers form a complete system of residues modulo m if there are exactly m of them and they are pairwise incomparable modulo m.
Pairwise incomparability can be verified by replacing each number with the smallest non-negative residue; if there are no repetitions, then this is a complete deduction system.
Apply the remainder division theorem: a = m q + r.
13 = 6 2 + 1 13 1 (mod 6); 8 = 6 1 + 2 8 2 (mod 6);
3 = 6 (-1) + 3 -3 3 (mod 6); 10 = 6 1 + 4 10 4 (mod 6);
35 = 6 5 + 5 35 5 (mod 6); 60 = 6 10 + 0 60 0 (mod 6).
We got a sequence of numbers: 1, 2, 3, 4, 5, 0, there are exactly 6 of them, there are no repetitions and they are incomparable in pairs. That is, they form a complete system of residues modulo m = 6.
Example... Replace with the smallest absolute value and also the smallest positive residue 185 modulo 16.
Decision. Apply the remainder division theorem:
185 = 16 11 + 9 185 9 (mod 16).
Example. Check if numbers form (13, -13, 29, -9) reduced system of residues modulo m = 10.
Solution: Any reduced system of residues modulo m contains elements, where is the Euler function. In our case = 4, because among natural numbers only 1, 3, 7, 9 are coprime to 10 and do not exceed it. That is, it is possible that these four numbers constitute the desired system. Let's check these numbers for their pairwise incomparability: = 4, because among natural numbers only 1, 3, 7, 9 are coprime to 10 and do not exceed it. That is, it is possible that these four numbers constitute the desired system. Let's check these numbers for their pairwise incomparability: m.
Option 1. a= 185, m = 12; Option 2. a = 84, m = 9;
Option 3. a= 180, m = 10; Option 4. a = 82, m = 9;
Option 5. a= 85, m = 11; Option 6. a = 84, m = 8;
Option 7. a= 103, m = 87; Option 8. a = 84, m = 16;
Option 9. a= 15, m = 10; Option 10. a = 81, m = 9;
Option 11. a= 85, m = 15; Option 12. a = 74, m = 13;
Option 13. a= 185, m = 16; Option 14. a = 14, m = 9;
Option 15. a= 100, m = 11; Option 16. a = 484, m = 15;
Option 17. a= 153, m = 61; Option 18. a = 217, m = 19;
Option 19. a= 625, m = 25; Option 20. a = 624, m = 25;
Task 3. Write down the complete and reduced system of least
