GRUNDINFORMATIONEN AUS DER THEORIE
6. 1. Definition 1.
Die Zahlenklasse modulo m ist die Menge all jener und nur der ganzen Zahlen, die bei Division durch m den gleichen Rest r haben, also vergleichbare modulo m (m Î N, t> 1).
Bezeichnung einer Klasse von Zahlen mit Rest R: .
Jede Zahl aus der Klasse heißt ein Rest modulo m, und die Klasse selbst die Klasse der Reste modulo m genannt.
6. 2. Eigenschaften der Menge von Restklassen modulo T:
1) Gesamtmodulo T Wille T Rückstandsklassen: Z t = { , , , … , };
2) jede Klasse enthält eine unendliche Menge von ganzen Zahlen (Reste) der Form: = ( ein= mq+ r / qÎ Z, 0£ R< m}
3) "einÎ : einº R(mod m);
4) "a, bÎ : einº B(mod m), d. h. zwei beliebige Abzüge von einem Klasse, vergleichbar modulo T;
5) "einÎ , " BÎ : ein B(mod m), d. h. keine zwei Abzüge; vergriffen von verschiedenen Klassen, unvergleichlich modulo T.
6. 3. Definition 3.
Jede Menge von m Zahlen, die aus jeder Klasse von Resten modulo m genommen werden, heißt ein vollständiges System von Resten modulo m.
Beispiel: wenn m= 5, dann ist (10, 6, - 3, 28, 44) ein komplettes Restsystem mod 5 (überdies nicht das einzige!)
Insbesondere,
die Menge (0, 1, 2, 3, ..., m–1) ist ein System kleinste nicht negativ Abzüge;
der Satz (1, 2, 3, ..., m –1, T) Ist das System am wenigsten positiv Abzüge.
6. 4. Beachten Sie, dass:
wenn ( NS 1 , NS 2 , … , x t) Ist ein komplettes Reststoffsystem modulo T, dann 
.
6. 5. Satz 1.
Wenn {NS 1 , NS 2 , … , x t} – komplettes Reststoffsystem modulo m, "a, bÎ Z und(bei) = 1, – dann das Zahlensystem {Oh 1 +B, Oh 2 + B, … , ah zu+B} bildet auch ein komplettes Restsystem modulo m .
6. 6. Satz 2.
Alle Reste derselben Klasse von Resten modulo m haben denselben größten gemeinsamen Teiler mit der Zahl m: "a, bÎ Þ ( ein; T) = (B; T).
6. 7. Definition 4.
Abzugsklasse modulo m heißt teilerfremd mit Modul m,wenn mindestens ein Abzug dieser Klasse mit dem sogenannten
Beachten Sie, dass in diesem Fall nach Satz 2 alle die Zahlen dieser Klasse sind relativ prim mit dem Modul T.
6. 8. Definition 5.
Ein reduziertes System von Residuen für einen gegebenen Modul m ist ein System von Residuen, von jeder Klasse ein und nur ein Rest genommen, gleichsam mit dem Modul m.
6. 9. Beachten Sie, dass:
1) reduziertes Reststoffsystem modulo T enthält j ( T) Zahlen ( NS 1 , NS 2 ,…, };
2) : 
.
3) "x ich : (x ich, m) = 1;
Beispiel : Sei modulo T= 10 gibt es 10 Rückstandsklassen:
Z 10 = (,,,,,,,,,) ist die Menge der Restklassen modulo 10. Vollständiges Abzugssystem mod 10 wird zum Beispiel so aussehen: (0, 1, 2, 3, 4, 5, 6, 7, 8, 9).
Viele Arten von Abzügen, gegenseitig einfach mit Modul m = 10: (,,,) (j (10) = 4).
Reduziertes Abzugssystem modulo 10 ist zum Beispiel
(1, 3, 7, 9) oder (11, 43, - 5, 17) oder (- 9, 13, - 5, 77) usw. (überall j (10) = 4 Zahlen).
6.10. Praktisch: eines der möglichen reduzierten Reststoffsysteme mod m . zusammensetzen, es ist notwendig, aus dem vollständigen System der Reste mod m diejenigen Reste auszuwählen, die mit m teilerfremd sind J ( T).
6.11. Satz 3.
Wenn{NS 1 , NS 2 ,…, } – reduziertes Restsystem modulo m und
(ein, m) = 1, – dann das Zahlensystem {Oh 1 , Oh 2 , … , ax j (t)} auch bildet
reduziertes Restsystem modulo m .
6.12. Definition 6.
Die Summe( Å ) Abzugsklassen und +b gleich der Summe von zwei beliebigen Abzügen, einer von jeder gegebenen Klasse, und : Å = , wo"einÎ , "BÎ .
6.13. Definition 7.
Nach Produkt( Ä ) Abzugsklassen und modulo m ist die Klasse der Reste , also eine Restklasse bestehend aus Zahlen a ´ b gleich dem Produkt von zwei beliebigen Abzügen, einer von jeder gegebenen Klasse, und : Ä = , wo"einÎ , "BÎ .
Somit ist in der Menge der Restklassen modulo T: Z t= (,,,…,) Es werden zwei algebraische Operationen definiert - "Addition" und "Multiplikation".
6.14. Satz 4.
Die Menge der Restklassen Z m modulo m ist ein assoziativer kommutativer Ring mit Eins:
< Z t , +, · > = < { , , ,…, }, +, · > – Ring.
TYPISCHE AUFGABEN
1. Aufbau nach Modul T= 9:
1) ein vollständiges System der am wenigsten positiven Rückstände;
2) ein vollständiges System der wenigsten nicht-negativen Reste;
3) ein beliebiges vollständiges System von Resten;
4) ein vollständiges System der kleinsten absoluten Wertreste.
Antworten:1) {1, 2, 3, 4, 5, 6, 7, 8, 9}; 2) {0, 1, 2, 3, 4, 5, 6, 7, 8};
2. Machen Sie ein reduziertes Reststoffsystem modulo T= 12.
Lösung.
1) Wir bilden ein vollständiges System der kleinsten positiven Reste modulo T= 12:
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12) (gesamt T= 12 Zahlen).
2) Löschen Sie aus diesem System Nummern, die nicht mit 12 übereinstimmen:
{1, 2 , 3 , 4 , 5, 6 , 7, 8 , 9 , 10 , 11, 12 }.
3) Die verbleibenden Zahlen, teilerfremd zu 12, bilden das erforderliche reduzierte Restsystem modulo T= 12 (Gesamt j ( T) = j (12) = 4 Zahlen).
Antworten:(1, 5, 7, 11) - reduziertes Restsystem modulo T= 12.
130. Machen Sie 1) ein vollständiges System der am wenigsten positiven Abzüge; 2) ein vollständiges System der wenigsten nicht-negativen Reste; 3) ein willkürliches System von Abzügen; 4) ein vollständiges System der kleinsten absoluten Wertabzüge; 5) reduziertes Restsystem: a) modulo m= 6; b) modulo m = 8.
131. Ist die Menge (9, 2, 16, 20, 27, 39, 46, 85) ein vollständiges System von Resten mod 8?
132 Um welchen Modul ist die Menge (20, - 4, 22, 18, - 1) ein vollständiges Restsystem?
133. Machen Sie das reduzierte System der Abzüge modulo m wenn eine) m= 9; B) m= 24; v) m= 7. Wie viele Zahlen sollte ein solches System enthalten?
134. Formulieren Sie die grundlegenden Eigenschaften des vollständigen Restsystems und des reduzierten Restsystems modulo m .
135. Was sind die Elemente des reduzierten und vollständigen Systems der kleinsten nichtnegativen Reste modulo simple?
136. Unter welchen Bedingungen die Zahlen ein und - ein gehören zur gleichen Klasse von Resten modulo m?
137. Welche Restklassen modulo 8 gehören zu allen Primzahlen R³ 3?
138. Bildet die Zahlenmenge (0, 2 0, 2 1, 2 2, ..., 2 9) ein vollständiges Restsystem mod 11?
139. Zu wie vielen Restklassen mod 21 gehören alle Reste einer Restklasse mod 7?
140. Die Menge der ganzen Zahlen Z nach Restklassen verteilen modulo 5. Erstellen Sie Additions- und Multiplikationstabellen in der resultierenden Menge von Restklassen Z 5. Ist die Menge Z 5: a) eine Gruppe mit der Operation der Klassenaddition? b) eine Gruppe mit der Operation der Klassenmultiplikation?
§ 7. THEOREM VON EULER. KLEINES BAUERNHOF THEOREM
GRUNDINFORMATIONEN AUS DER THEORIE
7. 1. Satz 1.
Wenn eineÎ Z,TÎ N, t>1 und(ein;T) = 1, - dann in einer unendlichen Folge von Graden a 1 , ein 2 , ein 3 , ... , ein S, ..., ein T, ... es gibt mindestens zwei Grad mit Exponenten s und t(S<T) so dass 
. (*)
7. 2. Kommentar... Durch die Benennung T– S = k> 0, aus (*) erhalten wir: 
... Beide Seiten dieses Vergleichs an die Macht bringen nÎ n, wir bekommen: 
(**). Das heißt, es gibt unendlich viele Potenzen der Zahl ein den Vergleich erfüllen (**). Aber wie finden Sie diese Indikatoren? Was am wenigsten Indikator befriedigender Vergleich (**)? Die erste Frage ist beantwortet Satz von Euler(1707 – 1783).
7. 3. Satz von Euler.
Wenn eineÎ Z,TÎ N, t>1 und(ein;T) = 1, - dann 
. (13)
Beispiel.
Lassen ein = 2,T = 21, (ein; T) = (2; 21) = 1. Dann 
... Da j (21) = 12, dann 2 12 º 1 (mod 21). Tatsächlich: 2 12 = 4096 und (4096 - 1) 21. Dann ist es offensichtlich, dass 2 24 º 1 (mod 21), 2 36 º 1 (mod 21) und so weiter. Aber ist der Exponent 12 - die kleinste befriedigender Vergleich 2 nº 1 (mod 21)? Es stellt sich nicht heraus. Der kleinste Indikator Wille NS= 6: 2 6 º 1 (mod 21), weil 2 6 - 1 = 63 und 63 21. Beachten Sie, dass am wenigsten der Indikator sollte gesucht werden nur unter den Teilern der Zahl J ( T) (in diesem Beispiel unter den Teilern der Zahl j (21) = 12).
7. 4. Fermats kleiner Satz (1601 - 1665).
Für jede Primzahl p und jede Zahl aÎ Z, nicht durch p teilbar, es gibt einen vergleich 
. (14)
Beispiel.
Lassen ein = 3,R= 5, wobei 3 nicht 5 ist. Dann 
oder 
.
7. 5. Der verallgemeinerte Satz von Fermat.
Für jede Primzahl p und eine beliebige Zahl aÎ Z ist der Vergleich 
(15)
TYPISCHE AUFGABEN
1. Beweisen Sie, dass 38 73 º 3 (mod 35).
Lösung.
1) Da (38; 35) = 1, dann nach dem Satz von Euler 
; j (35) = 24, also
(1).
2) Aus dem Vergleich (1) nach Korollar 2 der Eigenschaft 5 0 der numerischen Vergleiche ergibt sich:
3) Aus Vergleich (2) nach Korollar 1 von Eigenschaft 5 0 Vergleiche: 38 72 × 38 º 1 × 38 (mod 35) Þ Þ38 73 º38 º 38–35 = 3 (mod 35) Þ 38 73 º 3 (mod 35 ) nachzuweisen.
2. Gegeben: ein = 4, T= 15. Finden Sie den kleinsten Exponenten k den vergleich zufriedenstellend 
(*)
Lösung.
1) Seit ( ein; m) = (4; 25) = 1, dann nach dem Satz von Euler 
, j (25) = 20, also 
.
2) Ist der Exponent gefunden - die Zahl 20 - die kleinste eine natürliche Zahl, die den Vergleich (*) erfüllt? Wenn es einen Exponenten kleiner als 20 gibt, muss dieser ein Teiler von 20 sein. Dies bedeutet, dass der gewünschte kleinste Exponent k Sie müssen unter den Zahlen suchen n= (1, 2, 4, 5, 10, 20) - Teiler von 20.
3) Wann NS = 1: 
;
bei NS = 2: 
;
bei NS= 3: (nicht zu berücksichtigen);
bei NS = 4: ;
bei NS = 5: ;
bei NS= 6, 7, 8, 9: (nicht zu berücksichtigen);
bei NS = 10: .
So, die kleinste Exponent k den Vergleich erfüllen (*) ist k= 10.
Antworten: 
.
ÜBUNGEN FÜR UNABHÄNGIGE ARBEIT
141. Nach dem Satz von Euler 
... Bei ein = 3, T= 6 wir haben: 
.
Wegen j (6) = 2, dann 3 2 º1 (mod 6) oder 9º1 (mod 6) Dann nach dem Lemma (9 - 1) 6 oder 8 6 (total !?). Wo ist der Fehler?
142. Beweisen Sie, dass: a) 23 100 º1 (mod 101); b) 81 40 º 1 (mod100); c) 2 73 º 2 (mod 73).
143. Beweisen Sie, dass a) 1 16 + 3 16 + 7 16 + 9 16 º 4 (mod 10);
b) 5 4 NS + 1 + 7 4NS+ 1 ist ohne Rest durch 12 teilbar.
144. Beweisen Sie einen zum Satz von Euler umgekehrten Satz: if ein J ( m) º 1 (mod m), dann ( bin) =1.
145. Finden Sie den kleinsten Exponenten kÎ N, diesen Vergleich erfüllen: a) 
; B) 
; v) 
; G) 
;
e) 
; e) 
; g) 
; h) 
.
und) 
; Zu) 
; l) 
; m) 
.
146. Finden Sie den Rest der Division:
a) 7 100 mal 11; b) 9 900 mal 5; c) 5.176 mal 7; d) 2 1999 bis 5; e) 8 377 mal 5;
f) 26 57 bis 35; g) 35 359 bis 22; h) 5.718 bis 103; i) 27 260 mal 40; j) 25. 1998 bis 62.
147*. Beweise das ein 561 º ein(Mod11).
148*. Wenn die kanonische Zerlegung einer natürlichen Zahl NS die Faktoren 2 und 5 nicht enthält, dann endet die 12. Potenz dieser Zahl mit der Ziffer 1. Beweisen Sie.
149*. Beweisen Sie, dass 2 64 º 16 (mod 360).
150*. Beweisen Sie: wenn ( ein, 65) =1 , (B, 65) = 1, dann ein 12 –B 12 ist ohne Rest durch 65 teilbar.
Kapitel 3. ARITHMETISCHE ANHÄNGE
NUMERISCHE VERGLEICHSTHEORIE
§ 8. SYSTEMATISCHE ZAHLEN
GRUNDINFORMATIONEN AUS DER THEORIE
1. INTEGER SYSTEMATISCHE ZAHLEN
8. 1. Definition 1.
Jede Art, Zahlen zu schreiben, wird als Zahlensystem bezeichnet. Die Zeichen, mit denen diese Zahlen geschrieben werden, nennt man Zahlen.
8. 2. Definition 2.
Eine ganzzahlige nicht-negative systematische Zahl, die im t-ären Positionszahlensystem geschrieben ist, ist eine Zahl n der Form
,wo ein i(ich = 0,1, 2,…, k) – nicht negative ganze Zahlen - Ziffern, Außerdem 0 £ ein ich £ T– 1, t - Basis des Zahlensystems, tÎ N, t> 1.
Das Schreiben einer Zahl im 7-stelligen System lautet zum Beispiel: (5603) 7 = 5 × 7 3 + 6 × 7 2 + 0 × 7 1 + 3. Hier ein ich- das sind 5, 6, 0, 3 - Zahlen; sie alle erfüllen die Bedingung: 0 £ ein ich£ 6. Wann T= 10 sagen: Zahl n aufgenommen in dezimales Zahlensystem, und der Index t = 10 schreibe nicht.
8. 3. Satz 1.
Jede nicht negative ganze Zahl lässt sich zudem auf einzigartige Weise als systematische Zahl in jeder Basis t darstellen, wobei tÎ N, t> 1.
Beispiel:(1 3 9) 10 = (3 5 1) 6 = (1 0 2 4) 5 = …
8. 4. Beachten Sie, dass:
1) Zuordnung zur systematischen Anzahl von Nullen links ändert sich nicht diese Nummer:
(3 4) 5 = (0 3 4) 5 .
2) Zuordnung zu einer systematischen Zahl S Nullen rechts entspricht Multiplikation diese Nummer an t so: (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. Algorithmus zum Übersetzen einer Zahl, die in geschrieben istT -äres System, dezimal:
Beispiel: (287) 12 = 2 × 12 2 + 8 × 12 1 + 7 × 12 0 = 2 × 144 + 8 × 12 + 7 = 288 + 96 +7 = (391) 10.
8. 6. Algorithmus zum Übersetzen einer dezimal geschriebenen Zahl SystemeingangT - persönlich:
Beispiel: (3 9 1) 10 = (NS) 12. Finden NS.
8. 7. Aktionen zu systematischen Zahlen
2. SYSTEMATISCHE FRAKTIONEN
8. 8. Definition 3.
Ein endlicher t-ärer systematischer Bruch im System zur Basis t ist eine Zahl der Form
wo C 0 Î Z, mit i - Ziffern– nicht negative ganze Zahlen, Außerdem 0 £ mit ich£ T– 1, TÎ N, t> 1, kÎ n .
Bezeichnung: a = ( C 0 , mit 1 mit 2 …mit k)T... Bei T= 10 heißt der Bruch Dezimal.
8. 9. Folgerung 1.
Jeder endliche systematische Bruch ist eine rationale Zahl, die dargestellt werden kann als , wo einÎ Zum BeispielÎ N.
Beispiel.
a = (3 1, 2 4) 6 = 3 × 6 + 1 + = 19 + 
Ist eine rationale Zahl. Im Allgemeinen ist die umgekehrte Aussage nicht richtig. Ein Bruch kann beispielsweise nicht in einen endgültigen systematischen (dezimalen) Bruch umgewandelt werden.
8.10. Definition 4.
Ein unendlicher t-ärer positiver systematischer Bruch in der Basis t ist eine Zahl der Form
, wo c 0Î n, mit ich(ich =1, 2, …, Zu, …) - Zahlen– nicht negative ganze Zahlen, Außerdem 0 £ mit ich£ T–1, TÎ N, t> 1, kÎ n.
Bezeichnung: a = ( mit 0 , mit 1 mit 2 … mit k…) T... Bei T= 10 heißt der Bruch Dezimal.
8.11. Definition 5.
Es gibt drei Arten von unendlichen systematischen Brüchen:
Ich a = ( mit 0 , 
)T= = 
T wo = = = … In diesem Fall ist die Zahl ein heißt ein unendlicher rein periodischer Bruch,(mit 1 mit 2 … mit k) – Zeitraum, k - die Anzahl der Stellen in der Periode - die Länge der Periode.
II a = 
.
In diesem Fall ist die Zahl a heißt ein unendlicher gemischter periodischer Bruch, – Vorperiode, (
) – Zeitraum, k - die Anzahl der Stellen in der Periode - die Länge der Periode, l - die Anzahl der Stellen zwischen dem ganzzahligen Teil und der ersten Periode - die Länge der Vorperiode.
IIIa = ( mit 0 , mit 1 mit 2 … mit k …)T . In diesem Fall ist die Zahl ein heißt unendlicher nichtperiodischer Bruch.
TYPISCHE AUFGABEN
1. Nummer ( ein) 5 = (2 1 4 3) 5, gegeben im 5-är-System, übersetze in das 7-är-System, d. h. finde NS wenn (2 1 4 3) 5 = ( NS) 7 .
Lösung.
1) Wandle die angegebene Zahl (2 1 4 3) 5 in die Zahl ( bei) 10, geschrieben im Dezimalsystem:
2. Folgen Sie den Schritten:
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.
Lösung.
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 | Notiz: | 4 + 5 = 9 = 1 × 6 + 3, 3 wir schreiben, 1 geht in die nächste Kategorie, 6 + 3 + 1 = 10 = 1 × 6 + 4, 4 wir schreiben, 1 geht in die nächste Kategorie, 3 + 4 + 1 = 8 = 1 × 6 + 2, schreibe 2, 1 geht zur nächsten Ziffer. |
| 4) (5 2 3 4) 7 – (2 3 5 1) 7 (2 5 5 3) 7 | Notiz: | wir "besetzen" die Einheit der höchsten Kategorie, dh "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 | Notiz: | Wenn mit 2 multipliziert: 3 × 2 = 6 = 1 × 5 + 1, 1 schreiben wir, 1 geht zum nächsten Bit, 2 × 2 + 1 = 5 = 1 × 5 + 0, 0 schreiben wir, 1 geht zum nächstes Bit, 2 × 4 + 1 = 9 = 1 × 5 + 4, 4 wir schreiben, 1 geht zur nächsten Ziffer, Wenn mit 3: 3 × 3 = 9 = 1 × 5 + 4, 4 multipliziert, schreiben wir, 1 geht zur nächsten Ziffer, 3 × 2 + 1 = 7 = 1 × 5 +2, 2 wir schreiben, 1 geht zur nächsten Kategorie, 3 × 4 + 1 = 13 = 2 × 5 +3, 3 wir schreiben, 2 geht in die nächste Kategorie. |
6) (3 0 1 4 1) 5 | (4 2 3) 5
2 3 2 4 (3 2) 5
1 4 0 1 Antworten: 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 .
ÜBUNGEN FÜR UNABHÄNGIGE ARBEIT
151. Zahlen in T-äres System, in Dezimalsystem umwandeln:
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. Zahlen. im Dezimalsystem angegeben, umrechnen in T-technisches System. Hör zu.
a) (1 3 2) 10 = ( NS) 7; b) (2 9 8) 10 = ( NS) 5 ; c) (3 7) 10 = ( NS) 2; d) (3 2 4 5) 10 = ( NS) 6 ;
e) (4 4 4 4) 10 = ( NS) 3; f) (5 6 3) 10 = ( NS) 12 ; g) (5 0 0) 10 = ( NS) acht ; h) (6 0 0) 10 = ( NS) 2 ;
und) (1 0 0 1 5) 10 = ( NS) zwanzig ; j) (9 2 5) 10 = ( NS) acht ; l) (6 3 3) 10 = ( NS) fünfzehn ; m) (1 4 3) 10 = ( NS) 2 .
153. Zahlen in T-paralleles System, übersetzen in Q-ichny-System (durch das Dezimalsystem).
a) (3 7) 8 = ( NS) 3; b) (1 1 0 1 1 0) 2 = ( NS) 5 ; c) (6 2) 11 = ( NS) 4 ;
d) (4) 12 = ( NS) neun . e) (3 3 1 3 1) 5 = ( NS) 12 .
154. a) Wie ändert sich die Zahl (1 2 3) 5, wenn ihr rechts eine Null zugeordnet wird?
b) Wie ändert sich die Zahl (5 7 6) 8 wenn rechts zwei Nullen dazu kommen?
155. Gehen Sie wie folgt vor:
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 Dann:
I Wenn der Nenner B = B "(enthält nur "2" und/oder "5"), dann wird der Bruch umgerechnet in der endgültige Dezimalbruch. Die Anzahl der Nachkommastellen ist gleich der kleinsten natürlichen Zahl l lº 0( mod b").
II Wenn der Nenner B = b 1(enthält nicht "2" und "5"), dann wird der Bruch umgerechnet in unendlich rein periodisch gleich der kleinsten natürlichen Zahl k befriedigender Vergleich 10 kº 1 ( mod b 1).
III Wenn der Nenner B = B "× B 1 (enthält "2" und / oder "5", sowie andere Primfaktoren), dann wird der Bruch in . umgerechnet unendlich gemischt periodisch zehn-
Fraktion.
Die Periodenlänge ist gleich der kleinsten natürlichen Zahl k befriedigender Vergleich 10 kº 1 ( mod b 1).
Die Länge der Vorperiode ist gleich der kleinsten natürlichen Zahl l befriedigender Vergleich 10 lº 0( mod b").
9. 2. Schlussfolgerungen.
9. 3. Beachten Sie, dass:
eine rationale Zahl ist ein endlicher Dezimalbruch oder ein unendlicher periodischer Dezimalbruch;
Jeder unendliche nichtperiodische Dezimalbruch ist eine irrationale Zahl.
TYPISCHE AUFGABEN
1. Diese im Dezimalsystem geschriebenen gewöhnlichen Brüche wandeln sich in um
Dezimal, vorläufig nachdem die Art des gewünschten Bruches bestimmt wurde (endlich oder unendlich; periodisch oder nicht periodisch; wenn - periodisch, dann rein periodisch oder gemischt periodisch); in letzteren Fällen - vorfinden Nummer k- Periodenlänge und -anzahl l Ist die Länge der Vorperiode. 1) ; 2); 3).
Lösung.
1) Bruch = Nenner - Zahl B= 80 = 2 4 × 5 enthält nur "2" und "5". Daher wird dieser Bruch umgewandelt in der endgültige Dezimalbruch. Anzahl der Nachkommastellen l naim wird bestimmt aus der Bedingung: 10 lº0 (mod80):
2) Bruch = Nenner - Zahl B= 27 = 3 3 enthält nicht "2" und "5". Daher wird dieser Bruch in einen unendlichen rein periodisch Dezimalbruch. Periodenlänge k naim wird bestimmt aus der Bedingung: 10 kº1 (mod27):
3) Bruch = Nenner - Zahl B= 24 = 2 3 × 3, d. h. es hat die Form: B = B "× B 1 (außer "2" oder "5" enthält andere Faktoren, in in diesem Fall Nummer 3). Daher wird dieser Bruch in einen unendlichen gemischte Charge Dezimalbruch. Periodenlänge k naim wird bestimmt aus der Bedingung: 10 kº1 (mod3), woher k naim= 1, d. h. die Länge der Periode k= 1. Vorperiodenlänge l naim wird bestimmt aus der Bedingung: 10 lº0 (mod8), woher l naim= 3, d. h. die Länge der Vorperiode l = 3.
Überprüfung: 5 durch 24 mit einer "Ecke" teilen und erhalten: = 0, 208 (3).
Antworten: 1) 0, 0375; 2) 0, (074); 3) 0, 208 (3).
ÜBUNGEN FÜR UNABHÄNGIGE ARBEIT
156. Diese im Dezimalsystem geschriebenen gewöhnlichen Brüche werden in Dezimalbrüche umgewandelt. Wenn der Dezimalbruch periodisch ist, dann vorläufig finde die nummer k- Periodenlänge und -anzahl l ist die Länge der Vorperiode.
157. Diese im Dezimalsystem geschriebenen gewöhnlichen Brüche wandeln sich in um T-ähnliche systematische Brüche. Finde die Zahlen k ist die Länge der Periode und l ist die Länge der Vorperiode.
158*. In welchem Zahlensystem wird die Zahl (4 6) 10 in den gleichen Ziffern geschrieben, aber in
umgekehrte Reihenfolge?
159*. Was ist größer: die 8. Bit-Einheit im Binärsystem oder die 4. Bit-Einheit im Oktalsystem?
§ 10. THEOREM VON PASCAL. ZEICHEN DER TRENNBARKEIT
GRUNDINFORMATIONEN AUS DER THEORIE
10. 1. Satz von Pascal (1623 – 1662).
Natürliche Zahlen sind gegeben: m> 1und n, geschrieben im t - ären System:
,wobei a i - - Ziffern: a iÎ N, 0 £ ein ich £ T–1 (ich = 0,1, 2,…, k), TÎ N, t> 1.
Lassen n= (ein k ein k - 1 … ein 1 ein 0) 10 = ein k× 10 k +ein k - 1 × 10 k - 1 +…+ein 1 × 10 + ein 0 , m= 3 und m = 9.
1) Finden b ich: modulom = 3nach Modulm = 9
10 0 º1 (mod3), d.h. B 0 = 1, 10 0 º1 (mod9), d.h. B 0 =1,
10 1 º1 (mod3), d.h. B 1 = 1, 10 1 º1 (mod9), d.h. B 1 =1,
10 2 º1 (mod3), d.h. B 2 = 1, 10 2 º1 (mod9), d.h. B
Üblicherweise als komplettes Reststoffsystem modulo m nehmen die kleinsten nicht-negativen Reste
0,1,...,m − 1oder der absolut kleinste Rest aus Zahlen
,im Falle von ungeraden m und Zahlen
bei sogar m .
siehe auch
Literatur
- I. M. Vinogradov Grundlagen der Zahlentheorie. - M.-L.: Staat. Hrsg. technische und theoretische Literatur, 1952. - 180 S.
Wikimedia-Stiftung. 2010.
Sehen Sie in anderen Wörterbüchern nach, was das "Vollständige System der Abzüge" ist:
Modulo m, jede Sammlung von ganzen Zahlen, die eine Zahl aus jeder Zahlenklasse modulo m enthält (zwei ganze Zahlen a und b gehören zur gleichen Klasse modulo m, wenn a b durch m teilbar ist; siehe Rest). Als P. mit. V. am häufigsten… …
Modulo m jede Menge von ganzen Zahlen modulo m-unvergleichbar. Meist als P. mit. V. modulo die kleinsten nicht-negativen Reste 0, 1,. ... ., m 1 oder absolut die kleinsten Reste bestehend aus den Zahlen 0, +1,. ... ., v… … Enzyklopädie der Mathematik
Teil des vollständigen Restsystems (Siehe Vollständiges Restsystem), bestehend aus Zahlen, die mit dem Modul m coprime sind. P.s. V. enthält φ (m) Zahlen [φ (m) ist die Zahl der Zahlen, die zu m teilerfremd und kleiner als m sind]. Alle φ (m) Zahlen, die nicht modulo m vergleichbar sind und ... ... Große sowjetische Enzyklopädie
Vergleich modulo einer natürlichen Zahl n in der Zahlentheorie ist eine Äquivalenzrelation auf dem Ring der ganzen Zahlen, die mit der Teilbarkeit durch n verbunden ist. Der Faktorring in dieser Beziehung wird als Restring bezeichnet. Die Sammlung entsprechender Identitäten und ... ... Wikipedia
In der Zahlentheorie ist der Vergleich [zur Verdeutlichung] modulo einer natürlichen Zahl n eine Äquivalenzrelation auf der Menge der ganzen Zahlen, die durch die bezeichnete Zahl gegeben sind, verbunden mit der Teilbarkeit durch sie. Der Faktor Raum in dieser Beziehung heißt "ein Ring ... ... Wikipedia
Die Symmetrie einer Schneeflocke ist mit einer Gruppe von Drehungen um einen Winkel verbunden, der ein Vielfaches von 60 ° ist Eine endliche Gruppe ist eine algebraische Gruppe, die eine endliche Anzahl von Elementen enthält (diese Zahl wird ihre Ordnung genannt). Weiterhin wird angenommen, dass die Gruppe multiplikativ ist, d. h. die Operation in ... ... Wikipedia
Die Funktion zum Paradies kann durch eine Potenzreihe dargestellt werden. Eliminiert die Bedeutung der Klasse A. f. ist wie folgt definiert. Erstens ist diese Klasse ziemlich breit gefächert: Sie deckt die meisten Funktionen ab, die in den Grundfragen der Mathematik und ihrer ... ... Enzyklopädie der Mathematik
I Inhalt: I. Öffentliche Grundschulbildung im Allgemeinen. II. Öffentliche Grundschulbildung im Ausland: Österreich, Ungarn, England, Belgien, Bulgarien, Deutschland, Holland, Dänemark, Spanien, Italien, Norwegen, Portugal, Rumänien, Serbien, ... ... Enzyklopädisches Wörterbuch von F.A. Brockhaus und I.A. Efron
- - wurde am 26. Mai 1799 in Moskau in der Nemetskaya-Straße im Skvortsov-Haus geboren; starb am 29. Januar 1837 in St. Petersburg. Puschkin gehörte väterlicherseits einer alten Adelsfamilie an, die nach der Legende der Genealogie von einem Eingeborenen "aus ... ... Große biographische Enzyklopädie
Ein Satz geschlossener Formeln der Prädikatenlogik der 1. Stufe. E. T. Th (K) der Klasse K der algebraischen Signatursysteme heißt. die Menge aller abgeschlossenen Formeln der Prädikatenlogik der 1. Stufe der Signatur, die auf allen Systemen der Klasse K wahr sind. Wenn die Klasse ... ... Enzyklopädie der Mathematik
Klausel 17. Vollständiges und reduziertes Abzugssystem.
Im vorherigen Absatz wurde darauf hingewiesen, dass die Beziehung m Vergleichbarkeit modulo m ist eine Äquivalenzrelation auf der Menge der ganzen Zahlen. Diese Äquivalenzrelation induziert eine Unterteilung der Menge von ganzen Zahlen in Klassen von Elementen, die einander äquivalent sind, d.h. Zahlen werden zu einer Klasse zusammengefasst, die ergibt, wenn sie durch . geteilt wird m die gleichen Rückstände. Äquivalenzklassen m(Experten werden sagen - "Äquivalenzindex" m") ist genau gleich m .
Definition. Beliebige Zahl aus der Äquivalenzklasse m heißt Modulo-Rest m... Eine Reihe von Abzügen, einzeln von jeder Äquivalenzklasse m, heißt ein vollständiges Restsystem modulo m(im Gesamtsystem der Abzüge also insgesamt m Zahlenstücke). Direkt die Reste selbst bei Division durch m heißen die kleinsten nichtnegativen Reste und bilden natürlich ein vollständiges Restsystem modulo m... Ein Rest r heißt absolut kleinster, wenn п-п der kleinste unter den Modulen von Resten einer gegebenen Klasse ist.
Beispiel: Lassen m= 5. Dann:
0, 1, 2, 3, 4 - die kleinsten nicht-negativen Reste;
2, -1, 0, 1, 2 sind absolut die kleinsten Reste.
Die beiden gegebenen Zahlensammlungen bilden vollständige Restsysteme modulo 5 .
Lemma 1. 1) Beliebig m Stücke paarweise unvergleichbar modulo m Zahlen bilden ein vollständiges System von Resten modulo m .
2) Wenn ein und m sind gegenseitig einfach, und x m, dann die Werte der Linearform ax + b, wo B- beliebige ganze Zahl, auch das komplette Restsystem modulo . durchlaufen m .
Nachweisen. Teil 1) ist offensichtlich. Beweisen wir Behauptung 2). Zahlen ax + b glatt m Dinge. Zeigen wir, dass sie nicht modulo . miteinander vergleichbar sind m... Nun, lass es für etwas anderes sein x 1 und x 2 aus dem kompletten Abzugssystem hat sich herausgestellt, dass ax 1 + b є ax 2 + b (mod m)... Dann erhalten wir gemäß den Eigenschaften der Vergleiche aus dem vorherigen Absatz:
ax 1 є ax 2 (mod m)
x 1 є x 2 (mod m)
- ein Widerspruch dazu, dass x 1 und x 2 sind unterschiedlich und werden aus dem gesamten Abzugssystem entnommen.
Da alle Zahlen einer gegebenen Äquivalenzklasse є aus einer Zahl einer gegebenen Klasse durch Addition eines Vielfachen von m, dann haben alle Zahlen dieser Klasse den Modulus m gleichen größten gemeinsamen Faktor. Aus einigen Gründen sind die Abzüge, die mit dem Modul m größter gemeinsamer Teiler gleich eins, d.h. Abzüge, die mit dem Modul relativ einfach sind.
Definition. Das reduzierte Reststoffsystem modulo m ist die Menge aller Reste des Gesamtsystems, coprime zum Modul m .
Das reduzierte System wird normalerweise aus den kleinsten nicht-negativen Resten ausgewählt. Es ist klar, dass das reduzierte Restsystem modulo m enthält j ( m) Anzahl der Reste, wobei j ( m) Ist die Euler-Funktion - die Anzahl der Zahlen kleiner als m und gegenseitig einfach mit m... Wenn Sie die Euler-Funktion zu diesem Zeitpunkt bereits vergessen haben, schauen Sie sich Punkt 14 an und vergewissern Sie sich, dass etwas dazu gesagt wurde.
Beispiel. Lassen m= 42. Dann ist das reduzierte Restsystem:
1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.
Lemma 2. 1) Beliebiges j ( m) Zahlen, die paarweise nicht vergleichbar sind modulo m und coprime mit dem Modul, bilden ein reduziertes System von Resten modulo m .
2) Wenn (a, m) = 1 und x läuft das reduzierte Reststoffsystem modulo m, dann Axt läuft auch das reduzierte Reststoffsystem modulo m .
Nachweisen. Teil 1) ist offensichtlich. Beweisen wir Behauptung 2). Zahlen Axt paarweise unvergleichbar sind (dies wird auf die gleiche Weise bewiesen wie in Lemma 1 dieses Unterabschnitts), gibt es genau j ( m) Dinge. Es ist auch klar, dass sie alle dem Modul entsprechen, denn (a, m) = 1, (x, m) = 1 10 (ax.m) = 1... Daher die Zahlen Axt bilden das reduzierte Abzugssystem.
Dies sind die Definitionen und Grundeigenschaften der vollständigen und reduzierten Reststoffsysteme, aber im Gepäck mathematischen Wissens gibt es auch eine Reihe sehr interessanter und nützliche Faktenüber Abzugssysteme. Wenn Sie an dieser Stelle darüber schweigen, fürchte ich, dass es ein direkter Verstoß gegen das Gesetz ist. Russische Föderationüber Informationen, deren arglistige Zurückhaltung nach diesem Gesetz eine Ordnungswidrigkeit und sogar eine Straftat darstellt. Außerdem wird Absatz 17 ohne Kenntnis der weiteren wichtigen Eigenschaften von Abzugssystemen sehr kurz ausfallen. Lass uns weitermachen.
Lemma 3. Lassen m 1, m 2, ..., m k- sind paarweise coprime und m 1 m 2 ... m k = M 1 m 1 = M 2 m 2 = ... = M k m k, wo
1) Wenn x 1, x 2, ..., x k komplette Abzugssysteme nach Modulen durchlaufen m 1, m 2, ..., m k bzw. dann die Werte der linearen Form M 1 x 1 + M 2 x 2 + ... + M k x k das komplette Reststoffsystem modulo . durchlaufen m = m 1 m 2 ... m k .
2) Wenn x 1, x 2, ..., x k die reduzierten Abzugssysteme nach Modulen ausführen m 1, m 2, ..., m k bzw. dann die Werte der linearen Form M 1 x 1 + M 2 x 2 + ... + M k x k das reduzierte Reststoffsystem modulo . ausführen m = m 1 m 2 ... m k .
Nachweisen.
1) Formular M 1 x 1 + M 2 x 2 + ... + M k x k dauert offensichtlich m 1 m 2 ... m k = m Werte. Zeigen wir, dass diese Werte paarweise nicht vergleichbar sind. Gut lass
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)
Irgendetwas M j außer MS, mehrere Frau... Entfernen der linken und rechten Terme im letzten Vergleich, Vielfache Frau, wir bekommen:
M s x s є M s x s С (mod m s) Ю x s є x s С (mod m s)
- ein Widerspruch dazu, dass x s betreibt das komplette Reststoffsystem modulo Frau .
2). Die Form M 1 x 1 + M 2 x 2 + ... + M k x k nimmt offensichtlich j ( m 1) J ( m2) H ... H j ( m k) = j ( m 1 m 2 H ... H m k) = j ( m) (Eulersche Funktion ist multiplikativ!) verschiedene Werte, die untereinander modulo m = m 1 m 2 ... m k sind paarweise unvergleichbar. Letzteres lässt sich leicht durch ähnliche Argumente beweisen, wie sie im Beweis von Teil 1) dieses Lemmas verwendet wurden. Als ( M 1 x 1 + M 2 x 2 + ... + M k x k, m s) = (M s x s, m s) = 1 für jeden 1 Ј s Ј k, dann ( M 1 x 1 + M 2 x 2 + ... + M k x k, m s) = 1, daher die Wertemenge der Form M 1 x 1 + M 2 x 2 + ... + M k x k bildet ein reduziertes Reststoffsystem modulo m .
Lemma 4. Lassen x 1, x 2, ..., x k, x voll durch, und x 1, x 2, ..., x k, x- die reduzierten Abzugssysteme nach Modulen durchlaufen m 1, m 2, ..., m k und m = m 1 m 2 ... m k bzw. wo (m i m j) = 1 bei ich nein j... Dann die Brüche (x 1 / m 1 + x 2 / m 2 + ... + x k / m k) stimmen mit Brüchen überein (x/m), und Brüche (x 1 / m 1 + x 2 / m 2 + ... + x k / m k) stimmen mit Brüchen überein (x/m) .
Nachweisen. Die Beweise beider Behauptungen von Lemma 4 können leicht erhalten werden, indem man das vorherige Lemma 3 anwendet, nachdem Sie jede Summe angegeben haben (x 1 / m 1 + x 2 / m 2 + ... + x k / m k) und (x 1 / m 1 + x 2 / m 2 + ... + x k / m k) auf einen gemeinsamen Nenner:
(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) ,
wo M j = m 1 ... m j-1 m j + 1 ... m k .
Berücksichtigt man nun, dass die Bruchteile der Zahlen, die man bei der Division durch den Modul erhält, m zwei beliebige Zahlen vergleichbar modulo m, sind gleich (sie sind gleich r / m, wo R ist der kleinste nicht-negative Rest aus dieser Klasse), dann werden die Aussagen dieses Lemmas offensichtlich.
Im Rest dieses Abschnitts wird das Interessanteste passieren - wir werden die komplexen Wurzeln zusammenfassen m-te Potenz der Einheit, während wir auffallende Zusammenhänge zwischen den Summen von Wurzeln, Residuensystemen und der bereits bekannten multiplikativen Möbius-Funktion m entdecken werden ( m) .
Wir bezeichnen mit e k k Wurzel m- 1. Grad der Einheit:
Wir erinnern uns gut an diese Formen des Schreibens komplexer Zahlen aus dem ersten Jahr. Hier k = 0,1, ..., m-1- durchläuft das komplette Reststoffsystem modulo m .
Lassen Sie mich Sie daran erinnern, dass der Betrag e 0 + e 1 + ... + e m-1 alle Wurzeln m-ter Einheitsgrad ist null für alle m... In der Tat, lass e 0 + e 1 + ... + e m-1 = a... Wir multiplizieren diese Summe mit einer von Null verschiedenen Zahl e 1. Eine solche Multiplikation geometrisch in der komplexen Ebene bedeutet eine Drehung des korrekten m-Gons mit Wurzeln an den Scheitelpunkten e 0, e 1, ..., e m-1, bei einem Winkel ungleich Null 2 p / m²... Es ist klar, dass in diesem Fall die Wurzel e 0 wird zur Wurzel gehen e 1, Wurzel e 1 wird zur Wurzel gehen e 2, usw. und die Wurzel e m-1 wird zur Wurzel gehen e 0, d.h. Summe e 0 + e 1 + ... + e m-1 Wird sich nicht ändern. Wir haben e 1 a = a, wo a = 0 .
Satz 1. Lassen m> 0- ganze Zahl, ein Z , x betreibt das komplette Reststoffsystem modulo m... Dann wenn ein Vielfaches m, dann
ansonsten für ein kein Vielfaches m ,
.
Nachweisen. Bei ein mehrere m wir haben: a = md und
Bei ein nicht teilbar durch m, dividiere Zähler und Nenner des Bruchs bin An D- größter gemeinsamer Teiler ein und m, erhalten wir einen irreduziblen Bruch a 1 / m 1... Dann ist nach Lemma 1 ein 1 x durchläuft das komplette Reststoffsystem modulo m... Wir haben:
weil die Summe aller Wurzeln des Grades m 1 von eins ist null.
Lass mich dich daran erinnern, dass die Wurzel e k m-ten Einheitsgrad heißt Stammfunktion, wenn sein Index k coprime mit m... In diesem Fall, wie im ersten Jahr bewiesen, aufeinanderfolgende Abschlüsse ek 1, ek 2, ..., ek m-1 Wurzel e k bilden den gesamten Wurzelsatz m-ter Einheitsgrad oder mit anderen Worten, e k ist der Generator der zyklischen Gruppe aller Wurzeln m-ten Grad von eins.
Offensichtlich ist die Anzahl der verschiedenen primitiven Wurzeln m-te Potenz der Einheit ist gleich j ( m), wobei j die Euler-Funktion ist, da die Indizes an den Primitivwurzeln ein reduziertes Restsystem modulo m .
Satz 2. Lassen m> 0 Ist eine ganze Zahl, reicht x über das reduzierte Restsystem modulo m... Dann (die Summe der Stammwurzeln vom Grad m):
wo m ( m) Ist die Mobius-Funktion.
Nachweisen. Lassen m = p 1 a 1 p 2 a 2 ... p k a k- kanonische Zahlenzerlegung m ; m 1 = p 1 a 1 , m 2 = p 2 a 2 , m 3 = p 3 a 3; x i führt das reduzierte Restsystem modulo . aus ich bin... Wir haben:
Bei a s = 1 es stellt sich heraus, dass nur die Wurzel e 0 = 1 ist keine Stammfunktion, also ist die Summe aller Stammwurzeln die Summe aller Wurzeln minus eins:
also wenn m quadratfrei (d.h. nicht teilbar durch r 2, bei r> 1), dann
Wenn irgendein Indikator wie mehr als eine (d.h. m geteilt durch r 2, bei r> 1), dann die Summe aller primitiven Gradwurzeln Frau ist die Summe aller Wurzeln der Kraft Frau minus der Summe aller nicht-primitiven Wurzeln, d.h. alle Wurzeln etwas weniger Frau... Nämlich, wenn m s = p s m s *, dann:
Nun, liebe Leser, wenn ich Ihnen eine ziemlich bedeutende Menge an Informationen über das vollständige und reduzierte Abzugssystem vorgelegt habe, kann mir niemand vorwerfen, das Informationsgesetz der Russischen Föderation böswillig zu verletzen, indem ich es verstecke, also schließe ich diesen Absatz mit Genugtuung.
| Aufgaben |
1 ... Schreiben Sie alle kleinsten nicht-negativen Reste und alle absolut kleinsten Reste auf ein Blatt Papier. a) Mod 6, b) Mod8. Schreiben Sie unten die Abzugssysteme für diese Module auf. Zeichne getrennt auf der komplexen Ebene die Wurzeln des sechsten und des achten Grades aus der Einheit, umkreise in beiden Figuren die primitiven Wurzeln und finde jeweils ihre Summe. 2 ... Lassen e- Stammwurzel des Grades 2n von einem. Finden Sie den Betrag: 1+ e + e 2 + ... + e n-1 . 3 ... Finden Sie die Summe aller primitiven Wurzeln: a) 15.; b) der 24.; c) 30. Grad der Einheit. 4 ... Finden Sie die Summe aller möglichen Produkte von primitiven Wurzeln n-ten Grad von eins, genommen zwei auf einmal. 5 ... Finden Sie den Betrag k-x Grad aller Wurzeln n-ten Grad von eins. 6 ... Lassen m> 1 , (a, m) = 1 , B- ganze Zahl, NS durchläuft das Ganze, und x ist das reduzierte Restsystem modulo m... Beweise das: ein) B) 7 ... Beweise das:
wo R läuft über alle Primfaktoren einer Zahl ein . |
,Definition. Zahlen bilden ein vollständiges System von Resten modulo, wenn eine ganze Zahl mit einer und nur einer dieser Zahlen modulo kongruent ist.
Jedes vollständige Restsystem modulo besteht aus Zahlen, die paarweise modulo unvergleichbar sind.
Satz. Sei ein vollständiges System von Resten modulo. Sei eine ganze Zahl teilerfremd mit. Dann - auch ein komplettes Reststoffsystem modulo.
Nachweisen. Es ist zu beweisen, dass diese Zahlen paarweise unvergleichbar modulo sind. Nehmen wir das Gegenteil an. Lassen
Da GCD, was der Bedingung widerspricht.
Satz. Sei ein vollständiges System von Resten modulo. Sei eine ganze Zahl. Dann - auch ein komplettes Reststoffsystem modulo.
Lemma. Wenn, dann GOTT GOTT.
Nachweisen.
- ganze Zahl.
Von hier. Jeder gemeinsame Teiler ist ein Teiler. Daher das NOD NOD.
Definition. Zahlen bilden ein reduziertes System von Resten modulo, wenn sie teilerfremd sind mit und jede ganzzahlige teilerfremde Zahl mit ist mit einer und nur einer dieser Zahlen modulo vergleichbar.
Beispiel. Reduziertes Abzugssystem modulo 10: 1,3,7,9.
Lemma. Alle reduzierten Restsysteme im Modulus bestehen aus der gleichen Anzahl von Zahlen, die als Euler-Funktion bezeichnet wird.
Nachweisen. In der Tat gebe es zwei reduzierte Residuensysteme modulo, die aus unterschiedlich vielen Zahlen bestehen:
Da die Zahlen dann ein reduziertes System von Resten modulo bilden, ist jede der Zahlen mit einer und nur einer dieser Zahlen vergleichbar. Denn nach dem Dirichlet-Prinzip sind dann mindestens zwei Zahlen aus einer Zahl vergleichbar, das heißt, sie sind im absoluten Wert miteinander vergleichbar. Und dies widerspricht der Tatsache, dass - das reduzierte System der Reste modulo. Meint, .
Lassen Sie uns das nun beweisen. Tatsächlich bilden Zahlen kleiner als und relativ prim zu c ein reduziertes System von Resten modulo. Dies folgt aus dem Lemma.
Definition. Die Eulersche Funktion (oder das Totent) bezeichnet die Anzahl der Zahlen, die kleiner als und zu denen coprim sind.
Satz. Wenn ein reduziertes System von Resten modulo und eine Primzahl mit ist, dann ist auch ein reduziertes System von Resten modulo.
Wenn - einfach, dann.
Lemma. Wenn - einfach, dann.
Nachweisen. Tatsächlich gibt es nur Zahlen, die kleiner als eine Primzahl sind und mit ihr einen gemeinsamen Teiler haben.
Lemma. Lassen Sie die GCD. Dann . Die Euler-Funktion ist multiplikativ.
Nachweisen. Schreiben wir alle Zahlen von 1 bis wie folgt:
Die Zahlen in jeder Zeile bilden ein vollständiges System von Resten modulo. Daher gegenseitig einfach mit unter ihnen. Darüber hinaus sind diese Zahlen in Spalten angeordnet - untereinander, da jede Spalte Zahlen enthält, die im absoluten Wert vergleichbar sind.
Die Zahlen in jeder Spalte bilden ein vollständiges System von Resten modulo. Tatsächlich erhält man die te Spalte, indem man die Zahlen nimmt, die das vollständige System der Reste modulo bilden, sie mit einer zu primren Zahl multipliziert und zu jeder von ihnen addiert.
Somit gibt es in jeder Spalte genau Zahlen, die relativ prim sind.
Da eine Zahl dann und nur dann wechselseitig prim ist, wenn sie wechselseitig einfach mit und wechselseitig einfach mit ist, ist die Anzahl der wechselseitig primitivierten Zahlen gleich.
Satz. Lassen
Kanonische Zerlegung einer Zahl. Dann
Nachweisen. Nach dem Lemma über die Multiplikativität der Euler-Funktion
Beispiel.
Satz (Euler). Wenn und teilerfremde Zahlen sind, dann
Sei ein reduziertes System von Resten modulo. ... Dann gilt auch ein reduziertes Restsystem modulo. Daher ist jede der Zahlen der ersten Folge mit einer der Zahlen der zweiten Folge modulo vergleichbar, und jede der Zahlen der zweiten Folge ist mit einer der Zahlen der ersten Folge vergleichbar. Dann
Da jede der Zahlen miteinander einfach ist, kann der Vergleich durch sie abgekürzt werden:
Folge. Lassen Sie - ganze Zahlen, - natürlich. Wenn,, GCD, dann.
Nachweisen. Lassen . Seitdem - eine natürliche Zahl. Dann
Meint, .
88Frage
Homotetia und der Anschein von Raum
Homoteti mit Zentrum Ö und der Koeffizient k bezeichnen Hk 0
Die Eigenschaften der Transformationen der Homothetie und der Ähnlichkeit des Raumes sind den Eigenschaften der Homothetie und der Ähnlichkeit einer Ebene ähnlich, daher sollte das Studium der ersteren mit der Wiederholung der letzteren beginnen. Raumähnlichkeit mit Koeffizient k kann in eine Komposition aus Bewegung und Homothetie mit einem bestimmten Zentrum und demselben Koeffizienten zerlegt werden.
Den Studierenden sollte bewusst sein, dass bei einer solchen Raumtransformation der Wert des Winkels (planar und Dieder) erhalten bleibt, parallele (senkrechte) Geraden und Ebenen auf parallele (senkrechte) Geraden und Ebenen abgebildet werden. Das bedeutet, dass bei einer solchen Raumtransformation das Bild jeder Figur eine Figur ist, die die gleiche Form wie diese Figur hat, sich aber nur "in ihren Dimensionen" von ihr unterscheidet.
Aufgabe 12. Gegeben ein regelmäßiges Tetraeder RAVS; Punkte R 1 , EIN 1 , V 1 , MIT 1 - die Mitten seiner Gesichter (Abb. 14). Beweisen Sie, dass das Tetraeder R 1 EIN 1 V 1 MIT 1 ist wie ein Tetraeder RAVS; Finden Sie den Koeffizienten dieser Ähnlichkeit.
Lösung... Lass die Punkte n und K- jeweils die Mitte der Rippen AB und Sonne Tetraeder RAVS, Punkt EIN 1 - Gesichtsmitte RVS, Punkt R 1 - Gesichtsmitte ABC(Abb. 14). Es bedeutet, dass
RA 1: EIN 1 K = AR 1: R 1 K = 2: 1,
EIN 1 K : RK = R 1 K : AK = 1: 3,
Ähnlich kann man beweisen, dass
A 1 B 1: AB= 1: 3 und A 1 B 1 AB,
A 1 C 1 : WIE= 1: 3 und A 1 C 1 WIE,
B1 C1 : Sonne= 1: 3 und B1 C1 Sonne,
B1 R1 : BP= 1: 3 und B1 R1 BP,
1 Р 1 : Heiraten= 1: 3 und 1 Р 1 Heiraten.
Aus diesen Verhältnissen zwischen den Kanten der Tetraeder RAVS und R 1 A 1 B 1 C 1 daraus folgt, dass das Tetraeder R 1 A 1 B 1 C 1- richtig, daher sind diese Tetraeder ähnlich; der Ähnlichkeitskoeffizient beträgt 1/3. (In spezialisierten Klassen lohnt es sich zu beweisen, dass diese Tetraeder homothetisch sind.)
Sie können eine Definition eingeben: "Die Figur F 1 genannt wie eine figur F wenn es eine Raumähnlichkeitstransformation gibt, die die Figur anzeigt F auf der figur F 1". Um dann die Ähnlichkeit der Figur zu beweisen F 1 Abbildung F es genügt, mindestens eine Ähnlichkeitstransformation zu finden, die die Figur F Karten zu Figur F 1..
Definition. Die parallele Übertragung oder kurz die Übertragung einer Figur ist eine solche Darstellung, bei der alle ihre Punkte um gleiche Entfernungen in die gleiche Richtung verschoben sind, d. beim Übertragen von jeweils zwei Punkten X und Y der Figur werden solche Punkte X "und Y" mit XX "= YY" übereinstimmen
Die Haupteigenschaft der Übertragung:
Die parallele Übersetzung bewahrt Entfernungen und Richtungen, d.h. X "Y" = XY
Daraus folgt, dass eine parallele Übertragung eine richtungserhaltende Bewegung ist und umgekehrt, eine richtungserhaltende Bewegung eine parallele Übertragung
Aus diesen Aussagen folgt auch, dass die Zusammensetzung von Paralleltransfers ein Paralleltransfer ist
Die parallele Übertragung einer Figur wird durch die Angabe eines Paars entsprechender Punkte eingestellt. Wenn zum Beispiel angegeben ist, zu welchem Punkt A "dieser Punkt A geht, dann wird diese Translation durch den Vektor AA" angegeben, und dies bedeutet, dass alle Punkte um denselben Vektor verschoben werden, d.h. XX "= AA" für alle X Punkte
Zentrale Symmetrie
Definition
Die Punkte A und A" heißen symmetrisch bezüglich Punkt O, wenn die Punkte A, A", O auf einer Geraden liegen und OX = OX ". Punkt O gilt als symmetrisch zu sich selbst (bezüglich O)
Zwei Figuren heißen symmetrisch um Punkt O, wenn es zu jedem Punkt einer Figur in einer anderen Figur einen dazu symmetrischen Punkt um Punkt O gibt und umgekehrt
Als Sonderfall kann eine Figur bezüglich eines Punktes O zu sich selbst symmetrisch sein. Dann heißt dieser Punkt O Symmetriezentrum der Figur, und die Figur ist zentralsymmetrisch
Definition
Die zentrale Symmetrie einer Figur bezüglich O ist eine solche Abbildung dieser Figur, die jedem ihrer Punkte einen bezüglich O symmetrischen Punkt zuordnet
Haupteigenschaft: Zentrale Symmetrie hält den Abstand aufrecht und kehrt die Richtung um. Mit anderen Worten, zwei beliebige Punkte X und Y der Figur F entsprechen den Punkten X "und Y", so dass X "Y" = -XY
Nachweisen. Nehmen Sie an, dass die Punkte X und Y mit zentraler Symmetrie, die um Punkt O zentriert ist, auf X "und Y" abgebildet werden. Dann gilt, wie aus der Definition der Zentralsymmetrie hervorgeht, OX "= -OX, OY" = -OY
Gleichzeitig XY = OY - OX, X "Y" = OY "- OX"
Daher gilt: X "Y" = -OY + OX = -XY
Daraus folgt, dass zentrale Symmetrie eine Bewegung ist, die die Richtung in die entgegengesetzte Richtung ändert und umgekehrt, eine Bewegung, die die Richtung in die entgegengesetzte Richtung ändert, ist zentrale Symmetrie
Die zentrale Symmetrie der Figur wird durch Angabe eines Paares vorhandener Punkte angegeben: Wenn Punkt A auf A " abgebildet wird, dann ist der Symmetriezentrum der Mittelpunkt des Segments AA"
Dreh dich um eine gerade Linie
Um eine klarere Vorstellung von der Drehung um eine gerade Linie zu erhalten, erinnern Sie sich an die Drehung in einer Ebene um diesen Punkt. Die Drehung auf einer Ebene um einen bestimmten Punkt ist eine Bewegung, bei der sich jeder Strahl, der von einem bestimmten Punkt ausgeht, um den gleichen Winkel in die gleiche Richtung dreht. Kommen wir nun zu einer Drehung im Weltraum
Definition. Drehung der Figur um die Gerade a um einen Winkel (dies wird eine solche Abbildung genannt, bei der in jeder Ebene senkrecht zur Geraden a um den Schnittpunkt mit der Geraden a um den gleichen Winkel gedreht wird (in die gleiche Richtung. Die Gerade a heißt Drehachse und der Winkel ist der Drehwinkel)
Von hier aus sehen wir, dass die Drehung immer durch die Achse, den Winkel und die Drehrichtung bestimmt wird.
Satz 1. Eine Drehung um eine Gerade erhält Abstände, d.h. ist eine Bewegung
Satz 2. Hat die Raumbewegung eine Gerade mit ihrer Fixpunktmenge, dann ist sie eine Drehung um diese Gerade
Ebenentransformationen
Abzugsklassen. Abzugssysteme
Zusammenfassung der Theorie
Unter Anwendung des Theorems über die Division mit Rest kann die Menge der ganzen Zahlen in eine Anzahl von Klassen unterteilt werden. Schauen wir uns ein Beispiel an. Lassen m = 6. Dann haben wir sechs Partitionsklassen der Menge der ganzen Zahlen modulo 6:
R = 1;
R = 2;
R = 3;
R = 4;
R = 5;
wo durch R bezeichnet den Rest der Division einer ganzen Zahl durch 6.
Erinnern Sie sich an den Satz über die Division mit Rest:
Satz: Dividiere Zahl durch Zahl, mit Rest, dann finde ein Paar ganzer Zahlen Q und R so dass folgende Bedingungen: 
.
Es ist leicht zu beweisen, dass für beliebige ganze Zahlen ein und Division mit Rest ist möglich und Zahlen Q und R sind eindeutig bestimmt. In unserem Beispiel ist das vollständige System der kleinsten nicht-negativen Reste die Menge (0, 1, 2, 3, 4, 5); vollständiges System der am wenigsten positiven Reste - Satz (0, 1, 2, 3, 4, 5); komplettes System der kleinsten Reste in absoluten Werten - Menge (-2, -1, 0, 1, 2, 3); das reduzierte Restsystem ist die Menge (1,5), da; Faktor-Set
Eine der Methoden zur Durchführung arithmetischer Operationen an gegebenen ganzen Zahlen basiert auf einfachen Bestimmungen der Zahlentheorie. Die Idee hinter dieser Methode ist, dass ganze Zahlen in einem der nicht-positionalen Systeme dargestellt werden - im Restklassensystem. Nämlich: anstelle von Operationen mit ganzen Zahlen arbeiten sie mit den Resten der Division dieser Zahlen durch vorausgewählte Primzahlen - Module 
.
Am häufigsten Zahlen aus einer Vielzahl von Primzahlen ausgewählt.
Lassen 
…, 
.
Da der Divisionssatz mit Rest im Ring der ganzen Zahlen gilt, d. h. wo, dann ist der Ring Z, ist per Definition euklidisch.
Als Zahlen können Sie also die Reste der Division der Zahl wählen EIN An p ich bzw.
Das System der Ableitungen erlaubt es, arithmetische Operationen an einer endlichen Menge von Zahlen durchzuführen, ohne seine Grenzen zu überschreiten. Komplettes Abzugssystem modulo n- jeder Satz von n paarweise unvergleichbar modulo n ganze Zahlen. Üblicherweise als komplettes Reststoffsystem modulo n nehmen die kleinsten nicht-negativen Reste
Integer-Division ein und m Privatgelände Q und der Rest R so dass
a = m q + r, 0 R m-1. Rest R werden genannt ABZUG Ohm modulo m.
Zum Beispiel für m = 3 und für m = 5 erhalten wir:
| 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 |
Wenn der Rest null ist ( R=0 ), dann sagen sie das m teilt ein ganz (oder m Vielfaches ein ), was bedeutet m ein und die Zahlen Q und m Teiler genannt ein ... Offensichtlich 1 ein und ein ein ... Wenn ein hat keine anderen Teiler als 1 und ein , dann ein - Primzahl, sonst ein eine zusammengesetzte Zahl genannt. Größter positiver Teiler D zwei Zahlen ein und m bezeichnet den größten gemeinsamen Teiler (GCD) und bezeichnet d = (a, m). Wenn gcd (a, m) = 1 , dann ein und m haben keine gemeinsamen Teiler außer 1 , und werden relativ zueinander als teilerfremd bezeichnet.
Zu jedem ABZUG bei r = 0, 1, 2, ..., m-1 entspricht einer Reihe von ganzen Zahlen a, b, ... Sie sagen, dass Zahlen mit dem gleichen ABZUG Ohm sind im Modul vergleichbar und bezeichnen a b (mod m) oder (a b) m.
Zum Beispiel für m = 3 :
Zum Beispiel für m = 5 :
Zahlen ein die im Modul vergleichbar sind m , bilden eine Klasse von ihnen Abzug R und definiert als a = m q + r.
Zahlen ein auch genannt ABZÜGE modulo m ... Nicht negativ Abzüge a = r (bei q = 0 ) Werte aus dem Intervall nehmen , bilden ein vollständiges System der kleinsten Reste modulo m.
Abzüge ein
Werte aus dem Intervall nehmen [-( ,…,( ]
, bei seltsam m
oder aus dem Intervall [-
bei sogar m
bilden ein komplettes System von absolut kleinsten ABZUG ov modulo m.
Zum Beispiel für m = 5 Form der kleinsten Restklassen
r = 0, 1, 2, 3, 4, a = -2, -1, 0, 1, 2. Beide reduzierten Zahlenmengen bilden vollständige Systeme Abzug ov modulo 5 .
Klasse Abzüge deren Elemente mit dem Modul relativ einfach sind m
genannt reduziert. Die Euler-Funktion bestimmt, wie viel Abzüge aus dem Gesamtsystem der kleinsten Reststoffe modulo m sind relativ einfach mit m ... Mit einem einfachen m = p wir haben = p-1.
Definition... Die maximale Menge von paarweise nicht vergleichbaren Modulo m Zahlen coprime zu m wird genannt reduziertes Abzugssystem modulo m... Jedes reduzierte Reststoffsystem modulo m enthält Elemente, wobei die Euler-Funktion ist.
Definition. Beliebige Zahl aus der Äquivalenzklasse m werde anrufen Abzug Ohm modulo m... Das Aggregat Abzug s entnommen aus jeder Äquivalenzklasse m heißt das komplette System Abzug ov modulo m(im Vollsystem Abzug s, also insgesamt m Zahlenstücke). Direkt die Reste selbst bei Division durch m heißen die kleinsten nicht-negativen Abzug ami und bilden natürlich ein komplettes System Abzug ov modulo m. Abzug r heißt absolut kleinste, wenn ïrï der kleinste unter den Modulen ist Abzug dieser Klasse.
Beispiel... Prüfen Sie, ob die Zahlen 13, 8, - 3, 10, 35, 60 ein vollständiges Restsystem modulo m = 6 bilden.
Lösung: Zahlen bilden per Definition ein vollständiges System von Resten modulo m wenn es genau m davon gibt und sie paarweise nicht vergleichbar sind modulo m.
Paarweise Unvergleichbarkeit kann verifiziert werden, indem jede Zahl durch den kleinsten nicht-negativen Rest ersetzt wird; wenn es keine Wiederholungen gibt, dann ist dies ein komplettes Abzugssystem.
Wende den Restdivisionssatz an: 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).
Wir haben eine Zahlenfolge: 1, 2, 3, 4, 5, 0, es gibt genau 6 davon, es gibt keine Wiederholungen und sie sind paarweise unvergleichbar. Das heißt, sie bilden ein vollständiges Restsystem modulo m = 6.
Beispiel... Ersetze durch den kleinsten absoluten Wert und auch den kleinsten positiven Rest 185 modulo 16.
Lösung. Wende den Restdivisionssatz an:
185 = 16 11 + 9 185 9 (mod 16).
Beispiel.Überprüfen Sie, ob sich Zahlen bilden (13, -13, 29, -9) reduziertes Restsystem modulo m = 10.
Lösung: Jedes reduzierte Reststoffsystem modulo m enthält Elemente, wobei die Euler-Funktion ist. In unserem Fall = 4, weil unter natürliche Zahlen nur 1, 3, 7, 9 sind coprime zu 10 und überschreiten diese nicht. Das heißt, es ist möglich, dass diese vier Zahlen das gewünschte System bilden. Prüfen wir diese Zahlen auf ihre paarweise Unvergleichbarkeit: = 4, weil von den natürlichen Zahlen nur 1, 3, 7, 9 zu 10 teilerfremd sind und diese nicht überschreiten. Das heißt, es ist möglich, dass diese vier Zahlen das gewünschte System bilden. Prüfen wir diese Zahlen auf ihre paarweise Unvergleichbarkeit: m.
Variante 1. ein= 185, m = 12; Option 2. a = 84, m = 9;
Möglichkeit 3. ein= 180, m = 10; Option 4. a = 82, m = 9;
Möglichkeit 5. ein= 85, m = 11; Option 6. a = 84, m = 8;
Möglichkeit 7. ein= 103, m = 87; Option 8. a = 84, m = 16;
Möglichkeit 9. ein= 15, m = 10; Option 10. a = 81, m = 9;
Variante 11. ein= 85, m = 15; Option 12. a = 74, m = 13;
Variante 13. ein= 185, m = 16; Option 14. a = 14, m = 9;
Variante 15. ein= 100, m = 11; Option 16. a = 484, m = 15;
Variante 17. ein= 153, m = 61; Option 18. a = 217, m = 19;
Möglichkeit 19. ein= 625, m = 25; Option 20. a = 624, m = 25;
Aufgabe 3. Notieren Sie das vollständige und reduzierte System von mind
