1.Thema ab Klasse 11: Elementare Zahlentheorie II (Kongruenzen und Fermat) < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:31 Sa 24.07.2004 | | Autor: | Stefan |
Weiter geht es endlich (!) mit meinem Tutorium zur Vorbereitung auf Mathematik-Wettbewerbe.
Definition 1 (Kongruenzen)
Es sei [mm] $\red{m \in \IN}$. [/mm] Man sagt für zwei ganze Zahlen [mm] $\red{a}$ [/mm] und [mm] $\red{b}$:
[/mm]
[mm] $\red{a}$ [/mm] ist kongruent zu [mm] $\red{b}$ [/mm] modulo [mm] $\red{m}$, [/mm] wenn gilt:
[mm] $\red{m \, \vert\, (a-b)}$,
[/mm]
d.h.wenn es eine ganze Zahl [mm] $\red{q \in \IZ}$ [/mm] mit [mm] $\red{a-b=q\cdot m}$ [/mm] gibt, und schreibt dafür:
[mm] $\red{a \equiv b \pmod{m}}$.
[/mm]
Wenn $a$ kongruent zu $b$ modulo $m$ ist, dann ist auch $b$ kongruent zu $a$ modulo $m$ (wir haben also eine Symmetrieeigenschaft). (Daher sagt man auch: $a$ und $b$ sind kongruent modulo $m$.)
Weiterhin gilt: Ist $a$ kongruent zu $b$ modulo $m$ und $b$ kongruent zu $c$ modulo $m$, dann ist auch $a$ kongruent zu $c$ modulo $m$ (d.h. wir haben auch eine Transitivitätseigenschaft).
Kongruenzen können addiert, subtrahiert und multipliziert werden:
Satz 1 Es seien [mm] $\blue{a,b,c,d \in \IZ}$ [/mm] und [mm] $\blue{m \in \IN}$. [/mm] Dann folgen aus [mm] $\blue{a \equiv b \pmod{m}}$ [/mm] und [mm] $\blue{c \equiv d \pmod{m}}$ [/mm] die Beziehungen:
[mm] $\blue{a + c \equiv b + d \pmod{m}}$,
[/mm]
[mm] $\blue{a -c \equiv b - d \pmod{m}}$,
[/mm]
[mm] $\blue{a \cdot c \equiv b \cdot d \pmod{m}}$.
[/mm]
Man kann nun daraus induktiv ableiten:
Satz 2 Es seien [mm] $\blue{m \in \IN}$, $\blue{a,b \in \IZ}$ [/mm] und
[mm] $\blue{f(x) = a_n x^n + a_{n-1}x^{n-1} + \ldots + a_1x + a_0}$
[/mm]
ein Polynom mit ganzzahligen Koeffizienten [mm] $\blue{a_i \in \IZ}$ $\blue{(i=0,1,\ldots,n)}$.
[/mm]
Dann folgt aus [mm] $\blue{a \equiv b \pmod{m}}$ [/mm] die Beziehung:
[mm] $\blue{f(a) \equiv f(b) \pmod{m}}$. [/mm]
Darf man in Kongruenzen auch "kürzen"? Nein, nicht immer. Es gilt aber die folgende "Kürzungsregel":
Satz 3 Es seien [mm] $\blue{a,b,c \in \IZ}$ [/mm] und [mm] $\blue{m\in \IN}$ [/mm] gegeben. Dann gilt:
[mm] $\blue{ggT(c,m)=1\ , \quad ca \equiv cb \pmod{m} \qquad \Rightarrow \qquad a \equiv b \pmod{m}}$.
[/mm]
Jetzt kommt ein ganz wichtiger "Klassiker":
Satz 4 (Kleiner Satz von Fermat, 1640) Es sei [mm] $\blue{a \in \IN}$ [/mm] und [mm] $\blue{p \in \IN}$ [/mm] eine Primzahl. Dann gilt:
[mm] $\blue{a^p \equiv a \pmod{p}}$.
[/mm]
Ist [mm] $\blue{a}$ [/mm] kein Vielfaches von [mm] $\blue{p}$, [/mm] so folgt daraus mit der Kürzungsregel:
[mm] $\blue{a^{p-1} \equiv 1 \pmod{p}}$.
[/mm]
(Wer den Beweis sehen möchte: Ich kann drei elementare Beweisalternativen anbieten.  Meldet euch oder versucht den Satz selber zu beweisen.)
Bemerkung
Die "Umkehrung" (salopp gesagt) von Satz 4 ist falsch!
Aus [mm] $a^p \equiv [/mm] a [mm] \pmod{p}$ [/mm] für ein $a [mm] \in \IN$ [/mm] folgt also nicht, dass $p$ eine Primzahl ist.
(Gegenbeispiel: $341 [mm] \, \vert \, (2^{341} [/mm] - 2)$, aber $341=31 [mm] \cdot [/mm] 11$).
Definition 2 (Eulersche [mm] $\red{\phi}$-Funktion)
[/mm]
Es sei [mm] $\red{m \in \IN}$. [/mm] Dann bezeichnet [mm] $\red{\phi(m)}$ [/mm] die Anzahl der Elemente der Menge [mm] $\red{\{1,2,\ldots,m\}}$, [/mm] die teilerfremd zu [mm] $\red{m}$ [/mm] sind.
Beispiele: [mm] $\phi(p)=p-1$ [/mm] für jede Primzahl $p$, [mm] $\phi(10) [/mm] = 4$.
Nun können wir die kanonische Erweiterung von Satz 4 formulieren:
Satz 5 (Satz von Fermat-Euler) Es seien [mm] $\blue{a \in \IN}$ [/mm] und [mm] $\blue{m \in \IN}$ [/mm] mit [mm] $\blue{ggT(a,m)=1}$. [/mm] Dann gilt:
[mm] $\blue{a^{\phi(m)} \equiv 1 \pmod{m}}$.
[/mm]
Es folgen noch Tipps und Beispiele, wie man diese Dinge in Wettbewerbsaufgaben u.a. verwenden kann und dann zahlreiche Aufgaben, die ihr versuchen könnt zu lösen und über die wir dann zusammen diskutieren.
Zwei Bitten noch zum Schluss:
Wenn was unklar ist, dann fragt mich unbedingt!
Wenn ich Fehler gemacht habe, dann weist mich bitte darauf hin! (bitte per PN)
Liebe Grüße
Stefan
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:11 Sa 24.07.2004 | | Autor: | Hanno |
Hier die Beweise, die manche vielleicht interessieren könnten:
[mm]a\equiv b \pmod{m}[/mm]
[mm]c\equiv d \pmod{m}[/mm]
Es gilt
[mm]a-b=k_1\cdot m[/mm]
[mm]c-d=k_2\cdot m[/mm]
Addition beider Gleichungen ergibt
[mm](a+c)-(b+d)=(k_1+k_2)\cdot m[/mm],
womit die Additionsregel bewiesen wäre.
Des Weiteren gilt
[mm]a-b=k_1\cdot m[/mm]
[mm]\gdw a-k_1\cdot m=b[/mm]
und
[mm]c-d=k_2\cdot m[/mm]
[mm]\gdw c=k_2\cdot m+d[/mm]
Wir versuchen jetzt die Multiplikationsregel deduktiv herzuleiten, indem wir sie einfach aufschreiben und so umformen, dass wir am Ende einen sofort ersichtlich korrekten Term haben:
[mm]ac-bd[/mm]
[mm]=a(k_2\cdot m+d)-(a-k_1\cdot m)d[/mm]
[mm]=a\cdot k_2\cdot m+ad-ad+d\cdot k_1\cdot m[/mm]
[mm]=m(a\cdot k_2+d\cdot k_1)[/mm]
Damit ist bewiesen, dass [mm]ac\equiv bd \pmod{m}[/mm]
Nun zum Satz
[mm]ca\equiv cb \pmod{m}[/mm]
Wenn ggt(c,m)=1 dann
[mm]a\equiv b \pmod{m}[/mm]
Beweis:
[mm]ca-cb=k\cdot m[/mm]
[mm]c(a-b)=k\cdot m[/mm]
Da durch die Multiplikation auf der linken Seite die Teiler des Produktes der rechten Seite entstehen müssen, in dem auch alle Teiler von m enthalten sind, jedoch c keinen Teiler mit m gemein hat, muss a-b ein Vielfaches von m sein.
[mm]\Rightarrow a-b=k_2\cdot m[/mm]
[mm]\Rightarrow a\equiv b \pmod{m}[/mm]
Weitere Beweise können folgen :)
Gruß,
Hanno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:48 So 25.07.2004 | | Autor: | Stefan |
Ich will jetzt mal ein paar Beispiele dafür geben, wo man die Kongruenzrechnung in Wettbewerbsaufgaben sinnvoll einsetzen kann.
Zunächst einmal sind sie sehr wichtig beim Auffinden ganzzahliger Lösungen von Gleichungen. Ganz einfach deshalb, weil man diese ja auch modulo geeigneter ganzer Zahl betrachten kann. Dadurch schafft man notwendige Bedingungen an die Lösung, von denen man eventuell leichter als vorher zeigen kann, wann diese nicht gelten. Bevor ich hier noch mehr unverständliches Zeugs labere, schauen wir uns mal ein paar Beispiele an:
Beispiel 1
Zeige, dass die Gleichung [mm] $15x^2 [/mm] - [mm] 7y^2 [/mm] =9$ kein ganzzahliges Lösungspaar besitzt.
Lösung
Da $9$ und [mm] $15x^2$ [/mm] durch $3$ teilbar sind, muss auch [mm] $7y^2$ [/mm] durch $3$ teilbar sein, also wegen $ggT(3,7)=1$ auch [mm] $y^2$. [/mm] Da $3$ eine Primzahl ist, muss dann auch $y$ durch $3$ teilbar sein. Wir schreiben also [mm] $y=3y_1$ [/mm] mit einer ganzen Zahl [mm] $y_1$ [/mm] und erhalten:
[mm] $15x^2 [/mm] - [mm] 63y_1^2 [/mm] = 9$.
Teilt man diese Gleichung durch $3$, so folgt:
[mm] $5x^2 [/mm] - [mm] 21y_1^2 [/mm] = 3$.
Nun das gleiche Spiel wie eben: Da $3$ und [mm] $21y_1^2$ [/mm] durch $3$ teilbar sind, muss auch [mm] $5x^2$ [/mm] durch $3$ teilbar sein. Wegen $ggT(5,3)=1$ muss dann auch [mm] $x^2$ [/mm] durch $3$ teilbar sein (und damit, da $3$ prim ist) auch $x$. Wir schreiben [mm] $x=3x_1$ [/mm] mit einer ganzen Zahl [mm] $x_1$ [/mm] und erhalten durch Einsetzen:
[mm] $45x_1^2 [/mm] - [mm] 21y_1^2 [/mm] = 3$,
also:
[mm] $15x_1^2 [/mm] - [mm] 7y_1^2 [/mm] = 1$.
Nun betrachten wir diese Gleichung modulo $3$:
[mm] $-y_1^2 \equiv [/mm] 1 [mm] \pmod{3}$,
[/mm]
also:
[mm] $y_1^2 \equiv [/mm] -1 [mm] \equiv [/mm] 2 [mm] \pmod{3}$.
[/mm]
Aber: Es gilt immer (setze [mm] $y_1=0$, $y_1=1$ [/mm] und [mm] $y_1=2$ [/mm] ein):
[mm] $y_1^2 \equiv [/mm] 0 [mm] \pmod{3}$ [/mm] oder [mm] $y_1^2 \equiv [/mm] 1 [mm] \pmod{3}$.
[/mm]
Also erhält man unter der Annahme, es gäbe ein ganzzahliges Lösungspaar, einen Widerspruch.
Beispiel 2
Man zeige: Die Gleichung
[mm] $x^2 [/mm] + [mm] y^2 [/mm] + [mm] z^2 [/mm] = 2xyz$
hat außer $x=y=z=0$ keine ganzzahligen Lösungen.
Lösung
Es sei $(x,y,z) [mm] \ne [/mm] (0,0,0)$ eine ganzzahlige Lösung der obigen Gleichung. Es sei $k$ die größte natürliche Zahl, so dass $x$, $y$ und $z$ durch [mm] $2^k$ [/mm] teilbar ist. Dann können wir schreiben:
[mm] $x=2^k x_1$,
[/mm]
[mm] $y=2^k y_1$,
[/mm]
[mm] $z=2^kz_1$
[/mm]
mit ganzen Zahlen [mm] $x_1$, $y_1$ [/mm] und [mm] $z_1$.
[/mm]
Durch Einsetzen erhalten wir:
[mm] $2^{2k}x_1^2 [/mm] + [mm] 2^{2k}y_1^2 [/mm] + [mm] 2^{2k}z_1^2 [/mm] = [mm] 2^{3k+1}x_1y_1z_1$,
[/mm]
oder -wenn man durch [mm] $2^{2k}$ [/mm] teilt-
[mm] $x_1^2 [/mm] + [mm] y_1^2 [/mm] + [mm] z_1^2 [/mm] = [mm] 2^{k+1}x_1 y_1 z_1$.
[/mm]
Die rechte Seite ist gerade. Also muss auch die linke Seite gerade sein. Es kann aber nicht sein, dass alle drei Summanden der linken Seite gerade sind, sonst hätte man $k$ falsch gewählt (denn dann wäre ja auch [mm] $2^{k+1}$ [/mm] ein gemeinsamer Teiler von $x$, $y$ und $z$ gewesen).
Es kann aber auch nicht sein, dass genau zwei Summanden gerade sind oder alle Summanden ungerade sind (denn dann wäre die Summe ungerade). Also muss genau einer der Summanden gerade sein. ObdA (ohne Beschränkung der Allgemeinheit) sei dies [mm] $x_1^2$. [/mm] Dann ist auch [mm] $x_1$ [/mm] gerade und wir schreiben:
[mm] $x_1 [/mm] = [mm] 2x_2$ [/mm]
mit einer ganzen Zahl [mm] $x_2$.
[/mm]
Einsetzen liefert:
$4 [mm] x_2^2 [/mm] + [mm] y_1^2 [/mm] + [mm] z_1^2 =2^{k+2}x_2y_1z_1$.
[/mm]
Nun betrachten wir diese Gleichung modulo $4$:
(*) [mm] $y_1^2 [/mm] + [mm] z_1^2 \equiv [/mm] 0 [mm] \pmod{4}$.
[/mm]
Dies möchten wir zu einem Widerspruch führen. Wir wissen, da [mm] $y_1$ [/mm] und [mm] $z_1$ [/mm] ungerade sind, dass nur eine der vier folgenden Möglichkeiten in Frage kommt:
1) [mm] $y_1 \equiv [/mm] 1 [mm] \pmod{4}$, $z_1 \equiv [/mm] 1 [mm] \pmod{4}$,
[/mm]
2) [mm] $y_1 \equiv [/mm] 1 [mm] \pmod{4}$, $z_1 \equiv [/mm] 3 [mm] \pmod{4}$,
[/mm]
3) [mm] $y_1 \equiv [/mm] 3 [mm] \pmod{4}$, $z_1 \equiv [/mm] 1 [mm] \pmod{4}$,
[/mm]
4) [mm] $y_1 \equiv [/mm] 3 [mm] \pmod{4}$, $z_1 \equiv [/mm] 3 [mm] \pmod{4}$.
[/mm]
In allen vier Fällen gilt aber:
[mm] $y_1^2 [/mm] + [mm] z_1^2 \equiv [/mm] 2 [mm] \pmod{4}$,
[/mm]
im Widerspruch zu (*).
Auch die Frage, ob es Polynome mit ganzzahligen Koeffizienten und zusätzlichen Eigenschaften gibt, kann auf diese Weise schön untersucht werden:
Beispiel 3:
Zeige; Es gibt kein Polynom $f(x)$ mit ganzzahligen Koeffizienten, so dass $f(7)=11$ und $f(11)=13$.
Lösung
Es gilt:
$7 [mm] \equiv [/mm] 11 [mm] \pmod{4}$.
[/mm]
Also müsste (siehe "Lehrtext" ) auch
$f(7) [mm] \equiv [/mm] f(11) [mm] \pmod{4}$
[/mm]
gelten.
Es gilt aber:
$11 [mm] \not\equiv [/mm] 13 [mm] \pmod{4}$.
[/mm]
So, jetzt bekommt ihr Wettbewerbsaufgaben zum Thema Kongruenzrechnung. Demnächst. Denn ich gehe jetzt gleich erst einmal (trotz des Wetters) grillen. 
Liebe Grüße
Stefan
|
|
|
|
