matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenAlgebraLineare Kongruenzen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Philosophie • Religion • Kunst • Musik • Sport • Pädagogik
Forum "Algebra" - Lineare Kongruenzen
Lineare Kongruenzen < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Algebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Lineare Kongruenzen: Erklärung
Status: (Frage) beantwortet Status 
Datum: 21:21 Sa 03.01.2015
Autor: zahlenfreund

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


        
Bezug
Lineare Kongruenzen: Antwort
Status: (Antwort) fertig Status 
Datum: 22:25 Sa 03.01.2015
Autor: Schadowmaster

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. :)


Bezug
                
Bezug
Lineare Kongruenzen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 23:01 Sa 03.01.2015
Autor: zahlenfreund

Vielen Dank für deine ausführliche und gute Erklärung. Dank dir hab ich das jetzt alles verstanden.

beste Grüße zahlenfreund


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Algebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]