Kap. II: Der Kleine Satz von Fermat

35
Chr.Nelius : Zahlentheorie (SoSe 2016)
Kap. II: Der Kleine Satz von Fermat
§ 7. Reste von Potenzen
Für spätere Anwendungszwecke ist es nötig, Reste von Potenzen bei Division durch eine
Primzahl berechnen zu können. Dazu dienen die Überlegungen in diesem Paragraphen. Wir
bestimmen zunächst einmal Reste von Potenzen ai bei Division durch eine Zahl n für konkrete
Zahlenbeispiele:
(7.1) BEISPIELE:
rn (ai )
a
n
1
2
3
4
5
6
7
8
9
10
4
6
4
4
4
4
4
4
4
4
4
4
8
6
2
4
2
4
2
4
2
4
2
4
9
3
0
0
0
0
0
0
0
0
0
0
5 12
5
1
5
1
5
1
5
1
5
1
4
7
4
2
1
4
2
1
4
2
1
4
5 11
5
3
4
9
1
5
3
4
9
1
6 11
6
3
7
9
10
5
8
4
2
1
Während in den letzten vier Beispielen die Zahlen a und n teilerfremd sind, ist dies in den
ersten drei Beispielen nicht der Fall. Wir sehen, dass es in den Fällen mit ggT(a, n) = 1 mindestens eine Potenz mit dem Rest 1 gibt, danach wiederholen sich dann die Reste periodisch.
Im folgenden werden wir zeigen, dass es für eine Zahl a ∈ , die teilerfremd zu einer Primzahl
p ist, immer eine Potenz gibt, die den Rest 1 bei Division durch p hat. Dies ist die Aussage des
Kleinen Satzes von Fermat. Es gilt auch eine Verallgemeinerung dieses Satzes, die von L.Euler
bewiesen wurde, bei der p nicht unbedingt Primzahl sein muss. Diese Verallgemeinerung werden wir aber nicht behandeln. Im folgenden stellen wir ein Hilfsmittel bereit, das wir für den
Beweis des Kleinen Satzes von Fermat benötigen.
Z
(7.2) BEISPIEL: Für a = 4 und p = 7 bilden wir die Reste von k · a (k = 1, 2, . . . , 6)
bei Division durch 7:
k·a
r7 (k · a)
1·a 2·a 3·a 4·a 5·a 6·a
4
8
12
16
20
24
4
1
5
2
6
3
Wir sehen, dass wieder die Reste 1, 2, 3, 4, 5, 6 entstehen. Dieses Ergebnis gilt auch allgemein:
36
Chr.Nelius : Zahlentheorie (SoSe 2016)
(7.3) SATZ:
Seien a ∈
Z und p ∈ IP mit ggT(a, p) = 1 . Dann gilt
{ rp (1 · a), rp (2 · a), rp (3 · a), . . . , rp ((p − 1) · a) } = { 1, 2, 3, . . . , p − 1 } .
Wir können jetzt den Kleinen Satz von Fermat beweisen. Es sei daran erinnert, dass eine
Primzahl p genau dann zu einer ganzen Zahl a teilerfremd ist, wenn p 6 | a gilt (s. (3.5c)).
(7.4)
Der Kleine Satz von Fermat (1640)
Seien a eine ganze Zahl und p eine Primzahl mit p 6 | a .
Dann gilt
rp (ap−1 ) = 1 .
(7.5) BEM: Ohne die Voraussetzung p 6 | a ist die Aussage des Satzes (7.4) nicht mehr
richtig. Es gilt nämlich allgemeiner:
a∈
Z , k, n ∈ N , r (a ) = 1
n
k
=⇒ ggT(a, n) = 1 .
(7.6) BEM: In (7.4) gilt zwar rp (ap−1 ) = 1 , aber p − 1 muss nicht der kleinste Exponent
mit dieser Eigenschaft sein, wie die folgenden Beispiele für p = 13 zeigen: Für jedes a ∈
{1, 2, 3, . . . , 12} gilt zwar
r13 (a12 ) = 1 ,
aber es kann auch kleinere Exponenten k mit r13 (ak ) = 1 geben:
In der folgenden Tabelle sind für einige Werte von a die Reste von ai bei Division durch 13
angegeben.
r13 (ai )
i
1
2
3
4
5
6
7
8
9
10 11 12
a=1
1
1
1
1
1
1
1
1
1
1
1
1
a=2
2
4
8
3
6
12 11 9
5
10
7
1
a=3
3
9
1
3
9
1
3
9
1
3
9
1
a=4
4
3
12 9 10
1
4
3 12
9
10
1
a=5
5
12
8
5
12
8
1
5
12
8
1
a = 12
12
1
12 1 12
1
12 1 12
1
12
1
1
37
Chr.Nelius : Zahlentheorie (SoSe 2016)
Dabei fällt auf:
• Für a = 1 ist 1 der kleinste der Exponenten k mit r13 (ak ) = 1
• Für a = 2 ist 12 der kleinste der Exponenten k mit r13 (ak ) = 1
• Für a = 3 ist 3 der kleinste der Exponenten k mit r13 (ak ) = 1 . Danach wiederholen
sich die Reste periodisch.
• Auch für a ∈ {4, 5, 12} gibt es kleinste Exponenten 6, 4 bzw. 2.
• Der kleinste der Exponenten k mit r13 (ak ) = 1 ist jeweils ein Teiler von 12 .
(Dies lässt sich auch allgemein beweisen!)
(7.7) SATZ:
Sind a ∈
Z und m, n ∈ N , so gilt
rn (am ) = 1
(7.8) SATZ:
Seien a ∈
=⇒
rn (ak·m) = 1 (für alle k ∈
N ).
0
Z und p ∈ IP mit ggT(a, p) = 1 . Dann gilt für alle k, l ∈ N:
p − 1 | k − l =⇒ rp (ak ) = rp (al ) .
Als Spezialfall erhalten wir hieraus:
Z
(7.9) SATZ: Seien a ∈
und p ∈ IP mit ggT(a, p) = 1 und n ∈
r = rp−1 (n) den Rest von n bei Division durch p − 1 , so gilt
N . Bezeichnet dann
rp (an ) = rp (ar ) .
Mit Hilfe der gewonnenen Ergebnisse lässt sich jetzt die Berechnung des Restes einer Potenz
stark vereinfachen. Dazu ein Beispiel:
38
Chr.Nelius : Zahlentheorie (SoSe 2016)
(7.10) BEISPIEL: Wir wollen den Rest von a = 340209 bei Division durch 101 berechnen.
a ist eine Zahl mit 530 Dezimalstellen. p = 101 ist eine Primzahl (s. Liste), und es gilt
p 6 | a . Wir gehen in zwei Schritten vor:
1) Reduktion der Basis:
Nach (2.13g) gilt rp (an ) = rp (rp (a)n ) . Hier also r101 (340) = 37 und
r101(340209 ) = r101 (37209 )
Jetzt ist 37209 eine Zahl mit ”nur” noch 328 Stellen.
2) Reduktion des Exponenten:
Es ist r100 (209) = 9 , so dass nach (7.9)
r101 (37209 ) = r101 (379 )
gilt. 379 ist eine Zahl mit 15 Dezimalstellen, so dass die Aufgabe jetzt machbarer geworden
ist. Den Rest von 379 berechnen wir schrittweise unter Verwendung von (2.13f), wobei wir
darauf achten, dass die vorkommenden Zahlen nicht zu groß werden. Wir berechnen zunächst
r101 (374 ) und r101(375 ) und daraus dann r101 (379 ) .
r101 (372 ) = r101 (1369) = 56 (1369 = 13 · 101 + 56)
r101 (374 ) = r101 (372 ·372 ) = r101 (r101 (372 )·r101 (372 )) = r101 (56·56) = r101 (3136) = 5
(3136 = 31 · 101 + 5)
r101 (375 ) = r101 (374 · 37) = r101 (r101 (374 ) · r101(37)) = r101 (5 · 37) = r101 (185) = 84
Mit diesen beiden Zwischenergebnissen können wir jetzt r101 (379 ) berechnen:
r101 (379 ) = r101 (374 ·375 ) = r101 (r101(374 )·r101(375 )) = r101 (5·84) = r101 (420) = 16
Als Endergebnis erhalten wir schließlich
r101 (340209) = r101 (37209 ) = r101 (379 ) = 16 .
(7.11) SATZ: p und q seien zwei verschiedene Primzahlen. Ist dann a eine zu p · q teilerfremde ganze Zahl, so gilt
rp·q (a(p−1)·(q−1) ) = 1 .