?Bei manchen im Prinzip einfach erscheinenden Problemen treten sehr große Zahlen auf, die einem bei der Lösung leicht Kopfschmerzen bereiten. Hier nenne ich exemplarisch drei solcher Probleme, die wir im Verlaufe dieses Abschnitts lösen werden:
?Zur Lösung dieser und einer großen Anzahl verwandter Probleme wird im Folgenden ein Instrumentarium entwickelt. Der "Trick" liegt darin, nicht alle ganzen Zahlen zu betrachten, sondern sie vorher in bestimmte Klassen einzuteilen und dann mit diesen (endlich vielen) Klassen weiterzuarbeiten. Was man sich unter solchen Klassen vorzustellen hat, ist leicht erklärt:
Jede natürliche Zahl m>1 läßt sich benutzen, um die ganzen Zahlen in Gruppen von Resten, sogenannte Restklassen, einzuteilen. Wählt man z.B. m=8, so lassen die Zahlen 5, 13, 21, 29, aber auch -3, -11, -19 alle denselben Rest 5 bei Division durch m (man beachte: 21=2× 8+5, -3=-1·8+5, -19=-3 ·8+5 usw.). Ebenso gehören die Zahlen -17, -9, -1, 7, 15,... in eine Restklasse. Bezeichnet man diese Restklassen nach dem kleinsten positiven Rest, so gilt:
0*:={...,-24,-16,-8,0,8,16,24,...}={xï
x=k·8+0 und kÎZ}
1*:={...,-23,-15,-7,1,9,17,25,...}={xï
x=k·8+1 und kÎZ}
.....................................................................................
7*:={....,-17,-9,-1,7,15,23,31,..}={xï
x=k·8+7 und kÎZ}
Danach wiederholen sich die Elemente, so daß man genau 8 Klassen erhält. Eigentlich müßte man an die Klassen noch Indizes setzen nach der Zahl, die die Reste bestimmt. Da dies aber i.A. aus dem Zusammenhang hervorgeht, läßt man den Index zur Vereinfachung weg. Man nennt diese Zahl, in unserem Beispiel 8, den die Restklasse erzeugenden "Modul" und führt die folgende Bezeichnung ein:
DEFINITION 3.1
Zwei ganze Zahlen a und b heißen "kongruent modulo m" (mÎN>1), wenn sie bei Division durch m denselben Rest r lassen.
In Zeichen: aºb mod m Û
a=k·m+r und b=l·m+r mit k,lÎ
Z und 0£r<m.
Beispiel: 37º
73 mod 6, denn 37=6·6+1 und 73=12·6+1, aber 37¹
73 mod 7, da 37=57+2 und 73=10·7+3.
(Leider habe ich keinen Zeichensatz gefunden, der ein "Nichtkongruentzeichen" zu Verfügung stellt - es muß also statt dessen ein "¹
" genommen werden.)
1210º0 mod 11, denn 1210=110·11+0
Es gilt also aº b mod m, wenn a und b in derselben Restklasse mod m liegen. Ein beliebiger Modul m>1 erzeugt die m Restklassen 0*, 1*, 2*,...,(m-1)*. Eine Auswahl von m Zahlen, die paarweise aus verschiedenen Restklassen mod m stammen, nennt man ein "vollständiges Restsystem mod m" und schreibt dafür Rm (auch Z\m). So bilden z.B. die Zahlen 16,-7,2,43,-12,13,-2 und 23 ein vollständiges Restsystem mod 8. Der Einfachheit halber wählt man allerdings gewöhnlich R8={0,1,2,3,4,5,6,7} und läßt - ebenfalls zur Vereinfachung - die Sternchen weg.
AUFGABE 3.1
a) In welche Restklassen gehören die Zahlen 67, 2345, 99876, -345,
-12333 bezüglich der Moduln 8 bzw. 13 bzw. 137?
b) Wahr oder falsch? Falls falsch, korrigiere:
345º21 mod 47
8793º60 mod 123
345129º 335 mod 789
AUFGABE 3.2
Bestimme jeweils die kleinste natürliche Zahl n, für die gilt:
| a) 39ºn mod 5 | b) -39ºn mod 5 |
| c) 23768ºn mod 11709 |
d) nº234 mod 11 |
| e) 245º17 mod n | f) 7891º82 mod n |
| g) 11111º62 mod n | h) 22112º111 mod n |
| i) nº82 mod 131 Ù n>82 |
AUFGABE 3.3
Berechne alle nÎN mit:
| a) 187·41º0 mod n | b) 35·nº0 mod 7 |
| c) 35·nº0 mod 11 | d) 22·nº1 mod 7 |
| e) 345·nº7 mod 133 | f) 35·nº9 mod 135 |
Als nächstes wollen wir uns mit den Regeln der Operationen mit den neu eingeführten Restklassen beschäftigen. Wie wir gleich sehen werden, kann man mit ihnen beinahe genauso rechnen wir in Z.
Es seien also r* und s* zwei Restklassen mod m. Wenn wir je einen Vertreter (Fachsprache: Repräsentant) aus diesen Klassen nehmen, z.B. a=k·m+r und b=l·m+s, so gilt für die Summe a+b=(k+l)·m+(r+s). Ist r+s<m, so sei t:=r+s. Sonst gilt r+s=u·m+t mit 0£t<m. Somit gilt unabhängig von der Wahl der Repräsentanten a und b, daß die Summe von zwei Elementen aus r* und s* ein Repräsentant der Klasse t* ist. Wir können also auch kurz sagen: r*+s*=t*, wobei t* eindeutig bestimmt ist. Damit haben wir eine Addition auf Rm definiert.
Entsprechend können wir für eine Multiplikation sorgen. Mit den Bezeichnungen von oben gilt: ak·b=(klm+ks+rl)·m+rs, d.h., der Rest des Produktes von a und b bei Division durch m hängt nur davon ab, welchen Rest a und b selbst bei Division durch m lassen, d.h., aus welcher Restklasse a und b stammen; ansonsten muß über die Natur von a und b nichts bekannt sein. Wir können also analog zur Addition sagen: r*· s*=t*, wobei t* eindeutig bestimmt ist. Damit haben wir auch eine Multiplikation auf Rm definiert.
Wenn aus dem Zusammenhang klar ist, daß man sich mit den Restklassen mod m beschäftigt, läßt man die unhandlichen Sternchen an den Restklassen weg. Das wollen wir nun tun, wenn wir uns die Verknüpfungen in einigen Restklassen anschauen:
R2:
|
|
R3:
|
|
R5:
|
|
Manches wirkt schon etwas gewöhnungsbedürftig, wenn man die Tabellen inspiziert: z.B. 2·4=3 in R5 oder 2·2=1 in R3. Anderes ist aber doch gewohnt einfach: x·0=0 in allen Beispielen oder auch x+0=x. Man kann auch Gleichungen lösen:
2x+4=1 ï+(-4) [mit -4 wird das additiv inverse Element zu 4 bezeichnet, also 1]
2x = 2 ï·(2-1)
[entsprechend ist 2-1 das multiplikativ Inverse zu 2, also 3]
x = 2·3
x = 1
AUFGABE 3.4
Löse die folgenden Gleichungen in R5:
a) 3x+2=2 b) 4x+2=4 c) 3x-1=3
d) x2=4 e) x2-1=4
f) x2=2
Schauen wir uns ein weiteres Beispiel an:
R6:
|
|
Hier liegen die Dinge offensichtlich nicht mehr so einfach. Zwar sieht die Additionstafel noch recht ordentlich aus - jedes Element taucht in jeder Zeile und jeder Spalte auf; die Multiplikationstabelle läßt jedoch zu wünschen übrig. Sucht man z.B. das Inverse der Multiplikation von 3, so wird man enttäuscht: Es gibt kein Element xÎR6 mit 3·x=1. Man kann auch die Gleichung 3x+2=0 nicht lösen, denn die ist äquivalent zu 3x=4 - und dass diese Gleichung nicht lösbar ist, sieht man der entsprechenden Spalte der Multiplikationstabelle an.
Woran mag es liegen, daß es ganz angenehme und handliche Verknüpfungstabellen gibt und entsprechende Ekelstücke?
AUFGABE 3.5
Stelle Additions- und Multiplikationstafeln für R10 und R11 auf. Löse dann die folgenden Gleichungen jeweils in R10 und R11. Mache eine Probe!
a) 7x+8=5 b) 5x+9=3 c) 6x-2=8 d) 4x+9=8
e)x2=5
Es wäre selbstverständlich umständlich, wenn man sich bei allen möglichen Gelegenheiten für diverse m Additions- und Multiplikationstabellen aufstellen müßte. Nein, man kann den oben eingeführten Kalkül auch recht einfach direkt benutzen. Dazu werden wir im Folgenden die Rechenregeln für Kongruenzen aufstellen und beweisen, um sie dann zur Lösung der oben angesprochenen Probleme und vieler weiterer mehr zu benutzen.
Der erste Satz gibt uns einige einfache Umformungen an die Hand, von denen wir in den folgenden Beweisen eifrig Gebrauch machen werden:
SATZ 3.1
aºb mod m Û a-bº
0 mod m Û mïa-b
Beweis: aºb mod m Û a=k·m+r Ùb=l·m+r Û a-b=(k·m+r)-(l·m+r)=(k-l)·m+0 Û a-bº0 mod m Ûmï a-b
SATZ 3.2 (Rechenregeln für Kongruenzen)
Für a,b,c,dÎZ und mÎN>1 gilt:
(K1) aºb mod m Û bºa mod m
(K2) aºb mod m Ù
bºc mod m Þ
aºc mod m
(K3) aºb mod m Þ a+cº
b+c mod m
(K4) aºb mod m Þ a·c
ºb·c mod m
(K5) aºb mod m Þ
anºbn mod m für nÎN
(K6) aºb mod m Ù
cºd mod m Þ a+cº
b+d mod m
(K7) aºb mod m Ùcº
d mod m Þ a·cºb·d mod m
(K8) ggT(m,n)=1 Ùaº
b mod m Ùaº
b mod n Þ aºb mod m·n
(K9) a·bº0 mod p Ù
p prim Þ aº
0 mod p Ú bº0 mod p
(K10) ggT(a,m)=1: a·bºa·c mod m Û bºc mod m (Kürzungsregel)
Beweis zu (K3): Vor.: aºb mod m, also a-bº
0 mod m
zu zeigen: (a+c)-(b+c)º0 mod m
tatsächlich gilt: (a+c)-(b+c)=a-bº0 nach Vorauss. (q.e.d.)
Beweis zu (K4): zu zeigen: mï
ac-bc
gilt, denn wegen mïa-b gilt mïc(a-b)=ac-bc
Beweis zu (K5): mï
a-b Ù
a-bï
an-bn (Kap.1, Satz 2) Þ
mï
an-bn
AUFGABE 3.6
Beweise die Regeln (K1), (K2), (K6) und (K7).
AUFGABE 3.7
Zeige mit je zwei Beispielen und zwei Gegenbeispielen, daß die zusätzlichen Voraussetzungen in den Regeln (K8), (K9) und (K10) notwendig sind.
Beweis zu (K8): mï
a-b Ù nï
a-b Þ a-b=k×
m Ù a-b=l·n Þ
km=ln Þmï
l (wegen ggT(m,n)=1) Þ l=t×
m Þ
km=(tm)·n=t(mn) Þ a-b=t·(mn) Þ
mnïa-b (qed)
Beweis zu (K9): Für Primzahlen p gilt: wenn p nicht a teilt und p nicht b teilt, dann teilt p auch nicht a·b. Diese Aussage ist äquivalent zu : Wenn p a·
b teilt, dann teilt p a oder p teilt b. Das ist aber die Behauptung!
Beweis zu (K10): "Þ
" mïab-ac=a(b-c) Ù
m teilt nicht a Þ
mïb-c
"ܲ
mïb-c Þ
mïa(b-c) Þ
mïab-ac
Nun sind wir in der Lage, das erste der eingangs gestellten Probleme zu lösen:
222=31·7+5, also 222º5 mod 7 Þ
(mit K5) 222555º5555 mod 7
Nun untersuchen wir 5n mod 7:
52º
4 mod 7 Þ 53=52·
5º4·5=20º
6º-1 mod 7
also zusammengefaßt: 222555º5555º
5185·3=(53)185º
(-1)185=-1º6 mod 7
Entsprechen verfährt man mit dem zweiten Summanden:
555222º2222=(23)74
º174=1 mod 7
Aus beiden Überlegungen und (K6) folgt damit abschließend:
222555+555222º
-1+1=0 mod 7, also teilt 7 222555+555222.
(nur zur Information: 222555 hat 1303 Stellen, 555222 immerhin noch 610 Stellen!)
Neben einigen nützlichen Sätzen, die wir später noch herleiten werden, hilft bei Aufgaben mit hohen Potenzen der im folgenden Beispiel benutzte Algorithmus (fortlaufendes Quadrieren):
gesucht 2960 mod 99
Wir berechnen zunächst:
| 292=841º49 mod 99 |
| 294=(292)2º 492=2401º25 mod 99 und ebenso |
| 298º252=625º31 mod 99 |
| 2916º312=961º70 mod 99 |
| 2932º702=4900º49 mod 99 |
AUFGABE 3.8
(I) Berechne a) 3177 mod 57 b) 123345 mod 678 c) 731100 mod 567
(II) Auf welche Ziffern enden a) 6811 b) 21000
c) 3999 d) 6787 ?
(III) Bestimme die letzten beiden Ziffern der Potenzen aus (II)!
AUFGABE 3.9
Untersuche die Terme (a) 1055-5510 und (b) 111101-79100 auf ihren Rest bei Division durch 3, 4, 5, 7, 9, 11, 19 und 23.
AUFGABE 3.10
a) Zeige: (1+9+9+3)1+9+9+4-(1+9+9+5)º
1+9+9+2 mod (1+9+9+4)
b) Ist 1+19951995 durch 1996 teilbar?
c) Ist 19951994-19931994 durch 4 teilbar?
Wir können jetzt auch leichter lineare Kongruenzen nach beliebigen Moduln lösen:
Berechne: 37·xº15 mod 19
Wir formen um: 37x=k·19+15 Û
37x-19k=15 : Derartige Gleichungen haben wir bereits in 2.3 gelöst. Wir wissen sogar schon, wann diese Gleichungen lösbar sind! Es muß ggT(37,19) Teiler von 15 sein, was offensichtlich gilt. Mit dem BA folgt weiter:
| 37 | 1 | 0 | 0 |
| 19 | 0 | 1 | 1 |
| 18 | 1 | -1 | 1 |
| 1 | -1 | 2 | 18 |
| 0 | - | - | . |
Also ist x0=-1 und damit x=-15º
4 mod 19. Wir überprüfen: 37×
4=148=7×
19+15.
Das ist natürlich nur eine Lösung unter unendlich vielen, jedoch die kleinste positive.
Nach dem Beispiel ergibt sich sofort
SATZ 3.3
Die lineare Kongruenz a×xº
b mod m ist dann und nur dann lösbar, wenn ggT(a,m)ï
b. Die Lösungen der Gleichung erhält man aus ax-my=b gemäß Satz 2.2.
Bemerkung 1: Satz 3.3 stellt sicher, daß a·xº 1 mod p für ggT(a,p)=1 eindeutig lösbar ist. Damit existiert also für primes p für jedes a<p (also für alle aÎ Rp) ein multiplikativ inverses Element. Dies beantwortet also nachträglich die Frage auf Seite 3 unten.
Bemerkung 2: Es ist übrigens nicht immer nötig, mit dem BA zu arbeiten, wie das folgende Beispiel zeigt:
| 88xº16 mod 84 (*) |
| 22xº4 mod 21 (22º 1 mod 21) |
| xº4 mod 21 |
AUFGABE 3.11
Löse die folgenden linearen Kongruenzen:
| a) 23xº47 mod 253 | b) 67xº1 mod 127 |
| c) 1243xº1000 mod 2347 | d) 12123xº8765 mod 42017 |
| e) 11101xº11102 mod 42073 | f) 7307xº1001 mod 9999 |
| g) 21xº35 mod 77 | h) 88xº10 mod 84 |
| i) 1210xº 396 mod 77 |
| Mit dem nebenstehenden Button kannst Du ein Übungsprogramm zu Linearen Kongruenzen starten. |
AUFGABE 3.12
Oft interessiert das multiplikativ Inverse zu x. Berechne:
a) 66xº1 mod 109
b) 96xº1 mod 173
c) 324xº
1 mod 381
| Mit dem nebenstehenden Button kannst Du ein Übungsprogramm zu Berechnung des multiplikativ Inversen starten. |
Bemerkung 3: Auch diophantische Gleichungen lassen sich mit Hilfe des Kalküls der linearen Kongruenzen lösen.
Beispiel:
| 7x+3y=29 (*) |
| 7x=-3y+29 |
| 7xº29 mod 3 |
| xº2 mod 3 |
| x=3k+2 |
| in (*): 3y=29-7x=29-7(3k+2)=15-21k |
| y=5-7k |
Man löse mit diesem Verfahren:
(1) 10x+8y=6 (2) 33x+21y=9 (3) 22x-443y=159
Download Kap3_1(19 KB)
