Zum Inhalt springen

Kurs:Elemente der Algebra (Osnabrück 2015)/Vorlesung 16/kontrolle



Der Chinesische Restsatz für ℤ



Satz  Referenznummer erstellen

Es sei n eine positive natürliche Zahl mit kanonischer Primfaktorzerlegung

n=p1r1⋅p2r2⋯pkrk

(die pi seien also verschieden und ri≥1).

Dann induzieren die kanonischen Ringhomomorphismen ℤ/(n)→ℤ/(piri) einen Ringisomorphismus

ℤ/(n)≅ℤ/(p1r1)×ℤ/(p2r2)×⋯×ℤ/(pkrk).

Zu gegebenen ganzen Zahlen (a1,a2,…,ak) gibt es also genau eine natürliche Zahl  a<n,  die die simultanen Kongruenzen

a=a1modp1r1,a=a2modp2r2,…,a=akmodpkrk

löst.

Beweis  

Dies folgt unmittelbar aus Satz 15.7.

◻


Beweisvariante

Da die Ringe links und rechts beide endlich sind und die gleiche Anzahl von Elementen haben, nämlich n, genügt es, die Injektivität zu zeigen. Es sei x eine natürliche Zahl, die im Produktring (rechts) zu 0 wird, also modulo piri den Rest 0 hat für alle  i=1,2,…,k.  Dann ist x ein Vielfaches von piri für alle  i=1,2,…,k,  d.h. in der Primfaktorzerlegung von x muss pi zumindest mit dem Exponenten ri vorkommen. Also muss x nach Lemma 9.9 ein Vielfaches des Produktes sein, also ein Vielfaches von n. Damit ist  x=0  in ℤ/(n) und die Abbildung ist injektiv.


Unter den Basislösungen zu einer simultanen Kongruenz versteht man die kleinsten natürlichen Zahlen, die modulo den vorgegebenen Zahlen ein Restetupel ergeben, das an genau einer Stelle den Wert 1 und sonst überall den Wert 0 besitzt. Aus diesen Basislösungen kann man die Lösungen zu sämtlichen simultanen Kongruenzen berechnen.

Beispiel

Aufgabe


a) Bestimme für die Zahlen 3, 5 und 7 modulare Basislösungen, finde also die kleinsten positiven Zahlen, die in

ℤ/(3)×ℤ/(5)×ℤ/(7)

die Restetupel (1,0,0),(0,1,0) und (0,0,1) repräsentieren.


b) Finde mit den Basislösungen die kleinste positive Lösung x der simultanen Kongruenzen

x=2mod3,x=4mod5 und x=3mod7.


Lösung



a) (1,0,0): Alle Vielfachen von  5⋅7=35  haben modulo 5 und modulo 7 den Rest 0. Unter diesen Vielfachen muss also die Lösung liegen. 35 hat modulo 3 den Rest 2, somit hat 70 modulo 3 den Rest 1. Also repräsentiert 70 das Restetupel (1,0,0).

(0,1,0): Hier betrachtet man die Vielfachen von 21, und 21 hat modulo 5 den Rest 1. Also repräsentiert 21 das Restetupel (0,1,0).

(0,0,1): Hier betrachtet man die Vielfachen von 15, und 15 hat modulo 7 den Rest 1. Also repräsentiert 15 das Restetupel (0,0,1).


b) Man schreibt (in ℤ/(3)×ℤ/(5)×ℤ/(7))

(2,4,3)=2(1,0,0)+4(0,1,0)+3(0,0,1).

Die Lösung ist dann

2⋅70+4⋅21+3⋅15=140+84+45=269.

Die minimale Lösung ist dann  269−2⋅105=59. 



Korollar  Korollar 16.3 ändern

Es sei n eine positive natürliche Zahl mit kanonischer Primfaktorzerlegung  n=p1r1⋅p2r2⋯pkrk  (die pi seien also verschieden und ri≥1).

Dann gibt es einen kanonischen Gruppenisomorphismus

(ℤ/(n))×≅(ℤ/(p1r1))××⋯×(ℤ/(pkrk))×.

Insbesondere ist eine Zahl a genau dann eine Einheit modulo n, wenn sie eine Einheit modulo piri ist für  i=1,…,k. 

Beweis  

Dies folgt aus dem chinesischen Restsatz und Lemma 15.6.

◻



Die Eulersche φ-Funktion



Satz  Satz 16.4 ändern

Genau dann ist  a∈ℤ  eine Einheit modulo n (d.h. a repräsentiert eine Einheit in ℤ/(n)), wenn a und n teilerfremd sind.

Beweis  

Dies folgt aus Lemma 14.9.

◻


Beweisvariante

Sind a und n teilerfremd, so gibt es nach Satz 8.5 eine Darstellung der 1, es gibt also ganze Zahlen r,s mit

ra+sn=1.

Betrachtet man diese Gleichung modulo n, so ergibt sich  ra=1  in ℤ/(n). Damit ist a eine Einheit mit dem inversen Element  a−1=r. 

Ist umgekehrt a eine Einheit in ℤ/(n), so gibt es ein  r∈ℤ/(n)  mit  ar=1  in ℤ/(n). Das bedeutet aber, dass ar−1 ein Vielfaches von n ist, sodass also

ar−1=sn

gilt. Dann ist aber wieder  ar−sn=1  und a und n sind teilerfremd.




Zu einer natürlichen Zahl n bezeichnet φ(n) die Anzahl der Elemente von (ℤ/(n))×. Man nennt φ(n) die Eulersche Funktion.

Die Eulersche Funktion φ(n) gibt also für  n≥1  nach Satz 16.4 an, wie viele Zahlen r, 0≤r<n, zu n teilerfremd sind.


Für eine Primzahl p ist  φ(p)=p−1.  Eine Verallgemeinerung des kleinen Fermat ist der folgende Satz von Euler.


Satz  Referenznummer erstellen

Es sei n eine natürliche Zahl.

Dann gilt für jede zu n teilerfremde Zahl a die Beziehung

aφ(n)=1modn.

Beweis  

Das Element a gehört zur Einheitengruppe (ℤ/(n))×, die φ(n) Elemente besitzt. Nach dem Satz von Lagrange ist aber die Gruppenordnung ein Vielfaches der Ordnung des Elementes.

◻


Wir geben abschließend Formeln an, wie man die Eulersche φ-Funktion berechnet, wenn die Primfaktorzerlegung bekannt ist.



Lemma  Lemma 16.8 ändern

Es sei p eine Primzahl und pr eine Potenz davon.

Dann ist

φ(pr)=pr−1(p−1).

Beweis  

Eine Zahl a ist genau dann teilerfremd zu einer Primzahlpotenz pr, wenn sie teilerfremd zu p selbst ist, und dies ist genau dann der Fall, wenn sie kein Vielfaches von p ist. Unter den natürlichen Zahlen <pr sind genau die Zahlen

0,p,2p,3p,…,(pr−1−1)p

Vielfache von p. Das sind pr−1 Stück, und daher gibt es

pr−pr−1=pr−1(p−1)

Einheiten in ℤ/(pr). Also ist  φ(pr)=pr−1(p−1). 

◻



Korollar  Korollar 16.9 ändern

Es sei n eine positive natürliche Zahl mit kanonischer Primfaktorzerlegung

n=p1r1⋯pkrk

(die pi seien also verschieden und ri≥1).

Dann ist

φ(n)=φ(p1r1)⋯φ(pkrk)=(p1−1)p1r1−1⋯(pk−1)pkrk−1.

Beweis  

Die erste Gleichung folgt aus Korollar 16.3 und die zweite aus Lemma 16.8.

◻


<< | Kurs:Elemente der Algebra (Osnabrück 2015) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)