Vollständige Induktion < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Chinesischer Restsatz: Suchen Sie eine Zahl mit folgenden Eigenschaften:
x = 1 (mod 3)
x = 2 (mod 7)
x = 5 (mod 11)
Ist es erlaubt, in diesem Fall den chinesischen Restsatz anzuwenden? |
Hallo,
ich komme bei dem Chinesischen Restsatz nicht mehr weiter. Wie komme ich auf die Zahlen (fett makiert) vom Professor? Wie hat er das ausgerechnet?
1. Schritt:
m1 = 3 und p1 = 1
m2 = 7 und p2 = 2
m3 = 11 und p3 = 5
2. Schritt:
m = m1 * m2 * m3 = 3 * 7 * 11 = 231
3. Schritt: Produkte der Module berechnen
M1 = m2 * m3 = 7 * 11 = 77
M2 = m3 * m1 = 11 * 3 = 33
M3 = m1 * m2 = 3 * 7 = 21
4. Schritt: Multiplikative Inverse bilden
[mm] M_{1} [/mm] * [mm] M_{1}^{−1} [/mm] = 1 (mod 3) d.h. 77 * [mm] M_{1}^{−1} [/mm] = 1 (mod 3) ODER 2 * [mm] M_{1}^{−1} [/mm] = 1 (mod 3)
[mm] M_{2} [/mm] * [mm] M_{2}^{−1} [/mm] = 1 (mod 7) d.h. 33 * [mm] M_{2}^{−1} [/mm] = 1 (mod 7) oder 5 * [mm] M_{2}^{−1} [/mm] = 1 (mod 7)
[mm] M_{3} [/mm] * [mm] M_{3}^{−1} [/mm] = 1 (mod 11) d.h. 21 * [mm] M_{3}^{−1} [/mm] = 1 (mod 11) oder 10 * [mm] M_{3}^{−1} [/mm] = 1 (mod 11)
5. Schritt: Repräsentanten aus der jeweiligen Klasse verwenden
[mm] M_{1}^{−1} [/mm] = 2
[mm] M_{2}^{−1} [/mm] = 3
[mm] M_{3}^{−1} [/mm] = 10
Bemerkungen: Die hochgestellte 1 bei [mm] M_{1}^{−1} [/mm] etc. ist eine -1. Irgendwie wird es hier falsch dargestellt...
Würde mich über eine schnelle Antwort sehr freuen. :D
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo BlueMoon,
verwende hier einfach die [mm] $\LaTeX$-Schreibweise, [/mm] dann wird auch alles korrekt dargestellt, z.B. a^{-1} für [mm] a^{-1}. [/mm] Die geschweiften Klammern sind immer dann nötig, wenn der Exponent (oder z.B. ein Index) mehr als ein Zeichen umfasst.
Zur Frage:
> Chinesischer Restsatz: Suchen Sie eine Zahl mit folgenden
> Eigenschaften:
> x = 1 (mod 3)
> x = 2 (mod 7)
> x = 5 (mod 11)
> Ist es erlaubt, in diesem Fall den chinesischen Restsatz
> anzuwenden?
> Hallo,
> ich komme bei dem Chinesischen Restsatz nicht mehr weiter.
> Wie komme ich auf die Zahlen (fett makiert) vom Professor?
> Wie hat er das ausgerechnet?
Vorab: gar nicht. Das ist noch Teil des Ansatzes!
> 1. Schritt:
> m1 = 3 und p1 = 1
> m2 = 7 und p2 = 2
> m3 = 11 und p3 = 5
Auch hier mathematische Schreibweise... [mm] m_3=11 [/mm] und [mm] p_3=5 [/mm] etc.
Verwende den Formeleditor (dazu in Deinem Profil Betatests aktivieren) oder sonst die Eingabehilfen unter dem Eingabefenster.
> 2. Schritt:
> m = m1 * m2 * m3 = 3 * 7 * 11 = 231
>
> 3. Schritt: Produkte der Module berechnen
> M1 = m2 * m3 = 7 * 11 = 77
> M2 = m3 * m1 = 11 * 3 = 33
> M3 = m1 * m2 = 3 * 7 = 21
>
>
> 4. Schritt: Multiplikative Inverse bilden
> [mm]M_{1}[/mm] * [mm]M_{1}^{−1}[/mm] = 1 (mod 3) d.h. 77 * [mm]M_{1}^{−1}[/mm] =
> 1 (mod 3) ODER 2 * [mm]M_{1}^{−1}[/mm] = 1 (mod 3)
> [mm]M_{2}[/mm] * [mm]M_{2}^{−1}[/mm] = 1 (mod 7) d.h. 33 * [mm]M_{2}^{−1}[/mm] =
> 1 (mod 7) oder 5 * [mm]M_{2}^{−1}[/mm] = 1 (mod 7)
> [mm]M_{3}[/mm] * [mm]M_{3}^{−1}[/mm] = 1 (mod 11) d.h. 21 * [mm]M_{3}^{−1}[/mm] =
> 1 (mod 11) oder 10 * [mm]M_{3}^{−1}[/mm] = 1 (mod 11)
Die fetten Einsen gehören zum Ansatz. So werden halt multiplikative Inverse definiert, also [mm] M_x^{-1}. [/mm] Berechnet sind die hier ja nicht, nur die Modulrechnung wurde zur Vereinfachung der Äquivalenzen benutzt.
> 5. Schritt: Repräsentanten aus der jeweiligen Klasse
> verwenden
> [mm]M_{1}^{−1}[/mm] = 2
> [mm]M_{2}^{−1}[/mm] = 3
> [mm]M_{3}^{−1}[/mm] = 10
Bei so kleinen Modulen haben die Inversen irgendwie immer die Eigenschaft, dass sie einfach vom Himmel fallen. Oder der Prof hat sie irgendwo in der Tasche.
Ein lautes Abrakadabra hilft. Oder nachdenken. Oder ausprobieren.
> Bemerkungen: Die hochgestellte 1 bei [mm]M_{1}^{−1}[/mm] etc. ist
> eine -1. Irgendwie wird es hier falsch dargestellt...
Jaja, siehe oben.
> Würde mich über eine schnelle Antwort sehr freuen. :D
Hilft Dir das schon weiter?
Grüße
reverend
|
|
|
| |
|
Also es ist nun so...
Ich habe mal versucht das ganze selber auszurechnen, aber ich weiß nicht, warum der Professor auf einmal von 2 (mod 7) auf 1 (mod 7) kommt. Darf ich da jedes mal einfach eine 1 nehmen oder wie?
4. Schritt: Multiplikative Inverse bilden
[mm]M_{1}[/mm] * [mm]M_{1}^{−1}[/mm] = 1 (mod 3) d.h. 77 * [mm]M_{1}^{−1}[/mm] = 1 (mod 3) ODER 2 * [mm]M_{1}^{−1}[/mm] = 1 (mod 3)
[mm]M_{2}[/mm] * [mm]M_{2}^{−1}[/mm] = 1 (mod 7) d.h. 33 * [mm]M_{2}^{−1}[/mm] = 1 (mod 7) oder 5 * [mm]M_{2}^{−1}[/mm] = 1 (mod 7)
[mm]M_{3}[/mm] * [mm]M_{3}^{−1}[/mm] = 1 (mod 11) d.h. 21 * [mm]M_{3}^{−1}[/mm] = 1 (mod 11) oder 10 * [mm]M_{3}^{−1}[/mm] = 1 (mod 11)
Ich habe jetzt geschafft von 77 auf die Zahl 2, von 33 auf die Zahl 5 und von 21 auf die Zahl 10 zu kommen.Aber wie berechne ich dann dazu die [mm] M_{1}^{−1} [/mm] etc.? Ich habe auch die geschweiften Klammern genutzt, aber trotzdem wird es nicht richtig dargestellt..
|
|
|
| |
|
Hallo nochmal,
> Also es ist nun so...
>
> Ich habe mal versucht das ganze selber auszurechnen, aber
> ich weiß nicht, warum der Professor auf einmal von 2 (mod
> 7) auf 1 (mod 7) kommt.
Ich sehe gar nicht, wo er das tut. ??
> Darf ich da jedes mal einfach eine
> 1 nehmen oder wie?
Nein, im allgemeinen ist [mm] 2\not\equiv 1\bmod{n}, [/mm] außer für n=1. 
> 4. Schritt: Multiplikative Inverse bilden
> [mm]M_{1}[/mm] * [mm]M_{1}^{−1}[/mm] = 1 (mod 3) d.h. 77 * [mm]M_{1}^{−1}[/mm] =
> 1 (mod 3) ODER 2 * [mm]M_{1}^{−1}[/mm] = 1 (mod 3)
> [mm]M_{2}[/mm] * [mm]M_{2}^{−1}[/mm] = 1 (mod 7) d.h. 33 * [mm]M_{2}^{−1}[/mm] =
> 1 (mod 7) oder 5 * [mm]M_{2}^{−1}[/mm] = 1 (mod 7)
> [mm]M_{3}[/mm] * [mm]M_{3}^{−1}[/mm] = 1 (mod 11) d.h. 21 * [mm]M_{3}^{−1}[/mm] =
> 1 (mod 11) oder 10 * [mm]M_{3}^{−1}[/mm] = 1 (mod 11)
>
> Ich habe jetzt geschafft von 77 auf die Zahl 2, von 33 auf
> die Zahl 5 und von 21 auf die Zahl 10 zu kommen.Aber wie
> berechne ich dann dazu die [mm]M_{1}^{−1}[/mm] etc.?
Ich glaube, das ist bei Euch noch gar nicht dran. Für größere Module hilft Herumprobieren natürlich nicht, aber bei so kleinen Modulen geht das ja noch. Gesucht sind
[mm] M_1^{-1} [/mm] mit [mm] 2*M_1^{-1}\equiv 1\bmod{3}
[/mm]
[mm] M_2^{-1} [/mm] mit [mm] 5*M_2^{-1}\equiv 1\bmod{7} [/mm] und
[mm] M_3^{-1} [/mm] mit [mm] 10*M_3^{-1}\equiv 1\bmod{11}
[/mm]
Die erste und dritte Äquivalenz sind sehr einfach zu finden, da [mm] 2\equiv -1\bmod{3} [/mm] und [mm] 10\equiv -1\bmod{11} [/mm] gilt. Zu lösen ist also [mm] -1*x\equiv 1\bmod{n}, [/mm] einmal mit n=3 und einmal mit n=11. Das Ergebnis ist offensichtlich beide Male -1 bzw. eben [mm] 2\bmod{3} [/mm] und [mm] 10\bmod{11}.
[/mm]
Bei der zweiten Äquivalenz kann man die 3 durch Ausprobieren finden, oder z.B. folgendes überlegen:
[mm] 2*2^{-1}\equiv 1\equiv 7+1\bmod{7}, [/mm] also [mm] 2^{-1}\equiv\bruch{7+1}{2}\equiv 4\bmod{7}
[/mm]
Damit kennen wir schonmal das Inverse der 2, das ist eigentlich immer sehr leicht auf obigem Weg zu bestimmen.
Und hier sind wir zufällig auch schon fertig, weil ja gilt [mm] 5\equiv -2\bmod{7}.
[/mm]
Also ist [mm] 5^{-1}\equiv((-5)*(-1))^{-1}\equiv 2^{-1}*(-1)^{-1})\equiv 4*(-1)\equiv 3\bmod{7}.
[/mm]
> Ich habe auch
> die geschweiften Klammern genutzt, aber trotzdem wird es
> nicht richtig dargestellt..
Du hast aber kein Minuszeichen verwendet, sondern einen längeren Strich (Halbgeviertstrich?), wahrscheinlich beim Kopieren aus einem anderen Programm. Mit dem normalen Minuszeichen der Tastatur klappts, siehe meine Darstellungen oben.
Grüße
reverend
|
|
|
| |
|
Kann man auch auf diese Lösungen ohne "herumprobieren" kommen? Ich habe immer nur Schwierigkeiten damit, die [mm] M_1^{-1}, M_2^{-1} [/mm] und [mm] M_3^{-1} [/mm] zu bestimmen.
|
|
|
| |
|
Hallo nochmal,
> Kann man auch auf diese Lösungen ohne "herumprobieren"
> kommen? Ich habe immer nur Schwierigkeiten damit, die
> [mm]M_1^{-1}, M_2^{-1}[/mm] und [mm]M_3^{-1}[/mm] zu bestimmen.
Ja, natürlich.
Es gibt zwei Möglichkeiten, einmal über den erweiterten euklidischen Algorithmus; alternativ durch die Anwendung von Euler-Fermat. Zu beidem schau mal ![[]](/images/popup.gif) hier und komm wieder, wenn Du Fragen dazu hast.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:55 Mo 27.01.2014 | | Autor: | BlueMoon92 |
Vielen Dank. Ich glaube, dass ich die Mathe-Prüfung heute bestanden habe. :D
|
|
|
|
