Lineare Kongruenzen < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Hallo zusammen
Ich versuche gerade folgendes aus unserem Skript zu verstehen.
Zu ganzen Zahlen a, b ∈ Z und einer natürlichen Zahl n ≥ 1 möchten wir die Lösbarkeit der Kongruenz a · x ≡ b mod n (I.3) untersuchen.
Wenn a ≡ 0 mod n, dann muss auch b ≡ 0 mod n gelten, damit (I.3) lösbar ist. In diesem Fall wird (I.3) durch alle ganzen Zahlen gelöst.
Wenn a nicht ≡ 0 mod n, dann sind wir versucht, nach x aufzulösen, d.h. durch a zu dividieren.
Das ist aber nicht immer möglich!(Warum ???). Nehmen wir zuerst an, dass n = p eine Primzahl
ist. Wenn a nicht ≡ 0 mod p bedeutet dass p ∤ a. Da p eine Primzahl ist, ist
dies äquivalent zu ggT(a, p) = 1. Daher existieren y,z ∈ Z mit y · a + z · p = 1.
Damit folgt x ≡ y · a · x ≡ y · b mod p. (Diese Folgerung ist für mich ebenfalls Unverständlich)
mit freundlichen Grüßen zahlenfreund
|
|
| |
|
moin,
ok, nehmen wir das mal auseinander:
> Hallo zusammen
>
> Ich versuche gerade folgendes aus unserem Skript zu
> verstehen.
>
> Zu ganzen Zahlen a, b ∈ Z und einer natürlichen Zahl n
> ≥ 1 möchten wir die Lösbarkeit der Kongruenz a · x ≡
> b mod n (I.3) untersuchen.
> Wenn a ≡ 0 mod n, dann muss auch b ≡ 0 mod n gelten,
> damit (I.3) lösbar ist. In diesem Fall wird (I.3) durch
> alle ganzen Zahlen gelöst.
Der Teil klar?
> Wenn a nicht ≡ 0 mod n, dann sind wir versucht, nach x
> aufzulösen, d.h. durch a zu dividieren.
> Das ist aber nicht immer möglich!(Warum ???).
Weil wir mod $n$ rechnen. Nehmen wir als Beispiel $a=2,b=3,n=4$.
Dann wäre, wenn wir durch $2$ teilen, unsere Lösung
$x [mm] \equiv \frac{3}{2} \mod [/mm] n$. Aber was ist [mm] $\frac{3}{2}$? [/mm] Wie du sicher weißt, kann man jedes Element mod $4$ in eine der Restklassen $0,1,2,3$ einordnen, jenachdem welchen Rest die Zahl mod $4$ lässt. Aber [mm] $\frac{3}{2}$ [/mm] ist erstmal keine ganze Zahl, also geht das nicht, es ist einfach nicht definiert, was [mm] $\frac{3}{2} \mod [/mm] 4$ sein soll.
Bevor du auf irgendwelche Ideen kommst noch ein anderes Beispiel:
$a=b=2,n=4$. Hier könnte man sagen: hey, [mm] $\frac{b}{a} [/mm] = [mm] \frac{2}{2} [/mm] = 1$, also eine ganze Zahl, nicht wie im letzten Beispiel [mm] $\frac{3}{2}$, [/mm] also klappt das in diesem Fall. Durch Einsetzen wirst du aber feststellen, dass wir hier in diesem zweiten Beispiel zwei Lösungen haben, nämlich $x = 1$ UND $x = 3$, wir verlieren also Lösungen.
Wenn dir das noch nicht klar ist guck nochmal genau nach, wie das Rechnen modulo einer Zahl definiert ist, mit was für Elementen man da arbeitet und frag ggf. nach.
Solltest du jetzt eingesehen haben, warum man nicht so einfach durch irgendwas teilen kann, wenden wir uns nun der Frage zu wann man es kann. Dafür müssen wir uns erstmal klar machen, was wir machen dürfen: wir haben bereits gesehen, dass es nicht gut ist durch $a$ zu teilen. Wir können aber die Gleichung mit einer ganzen Zahl (bzw. der zugehörigen Restklasse) auf beiden Seiten multiplizieren. Wenn wir solche Multiplikationen durchführen, die wir wieder rückgängig machen können, haben wir eine Äquivalenzumformung, behalten also die gleiche Lösungsmenge. Als Beispiel können wir mod $4$ etwa mit $3$ multiplizieren:
$ax [mm] \equiv [/mm] b [mm] \mod [/mm] 4 [mm] \gdw [/mm] 3ax [mm] \equiv [/mm] 3b [mm] \mod [/mm] 4$. Und warum ist das eine Äquivalenzumforumung? Weil wir es wieder rückgängig machen können, indem wir noch einmal mit $3$ multiplizieren, denn es ist [mm] $3\cdot [/mm] 3 = 9 [mm] \equiv [/mm] 1 [mm] \mod [/mm] 4$.
Wir stellen also fest: wir dürfen mit invertierbaren Elementen multiplizieren, also mit solchen $c [mm] \in \IZ$, [/mm] sodass ein $d [mm] \in \IZ$ [/mm] existiert mit $cd [mm] \equiv [/mm] 1 [mm] \mod [/mm] n$, denn dann können wir diese Multiplikation rückgängig machen und damit ist es eine Äquivalenzumformung, ändert also nicht die Lösungen unserer Kongruenz.
Langer Rede kurzer Sinn: wir wollen durch $a$ teilen. Wir haben oben gesehen, dass das im Allgemeinen nicht so einfach geht. Das heißt uns interessieren besonders die Fälle, wo $a$ invertierbar (manchmal sagt man auch "eine Einheit") [mm] $\mod [/mm] n$ ist.
Also wir möchten gerne wissen, wann zu gegebenem $a$ und $n$ beide ganze Zahlen ein $c [mm] \in \IZ$ [/mm] existiert mit $ac [mm] \equiv [/mm] 1 [mm] \mod [/mm] n$.
So, das war erstmal sehr viel, ich weiß. Es ist allerdings sehr wichtig, dass du verstehst warum wir uns für solche invertierbare $a$ interessieren und warum wir nicht einfach durch $a$ teilen dürfen; wir sind nicht in den ganzen Zahlen und erst recht nicht in den rationalen!
Wenn es bis hierhin noch Fragen gibt frag nach, wenn nicht gucken wir mal weiter:
> Nehmen wir
> zuerst an, dass n = p eine Primzahl
> ist. Wenn a nicht ≡ 0 mod p bedeutet dass p ∤ a. Da p
> eine Primzahl ist, ist
> dies äquivalent zu ggT(a, p) = 1. Daher existieren y,z
> ∈ Z mit y · a + z · p = 1.
Stimmt. Ist dir das bereits bekannt? Das ist die sogenannte Bezout-Identität (mit ein paar Akzenten auf dem Namen des Mathematikers^^), die man mit Hilfe des Euklidischen Algorithmus ausrechnen kann.
> Damit folgt x ≡ y · a · x ≡ y · b mod p. (Diese
> Folgerung ist für mich ebenfalls Unverständlich)
Dann machen wir es mal kleinschrittiger. Wir wissen, dass
$y [mm] \cdot [/mm] a + z [mm] \cdot [/mm] p = 1$. Das heißt wir haben
$x = (ya +zp)x = yax + zpx$.
Bis hierhin sind das wirklich Gleichungen in [mm] $\IZ$, [/mm] noch kein modulo rechnen. Gucken wir uns das jetzt modulo $p$ an, so ist der hintere Teil durch $p$ teilbar, ist also gleich $0 [mm] \mod [/mm] p$. Damit erhalten wir
$x [mm] \equiv [/mm] yax + 0 = yax [mm] \equiv [/mm] yb [mm] \mod [/mm] p$.
Hier vielleicht noch als Anmerkung: Setzen wir insbesondere $b=1$, so haben wir auf diese Art also die Gleichung $ax [mm] \equiv [/mm] 1 [mm] \mod [/mm] p$ nach $x$ gelöst, haben also das oben erwähnte Inverse von $a$ gefunden.
> mit freundlichen Grüßen zahlenfreund
>
lg
Schadow
PS: Versuch mal die Vorlagen für mathematische Formeln unter dem Eingabefenster zu verwenden. Einfach ein Dollarzeichen, dann die Formel, am Ende ein weiteres Dollarzeichen; hübscher und auf dauer einfacher als die Sachen bei google oder wo auch immer aus einer Zeichentabelle zu suchen. Und falls du Mathematik oder ein verwandtes Fach studierst, wirst du diese Art mathematische Zeichen zu schreiben spätestens in der Bachelorarbeit brauchen. :)
|
|
|
| |
|
Vielen Dank für deine ausführliche und gute Erklärung. Dank dir hab ich das jetzt alles verstanden.
beste Grüße zahlenfreund
|
|
|
|
