kleiner Satz von Fermat < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Lösen Sie das folgende lineare Kongruenzsystem
[mm] x\equiv [/mm] -1 mod 7
[mm] x\equiv [/mm] 2 mod 10
[mm] x\equiv [/mm] 17 mod 9
mit Hilfe des "kleiner Satz von Fermat"-Ansatzes |
hallo alle zusammen!
leider stehe ich gerade völlig aufm schlauch bei der aufgabe...
beginnt man vielleicht so:
ggT(x,7)=1, ggT(x,10)=1, ggT(x,9)=1 => kleiner Fermat anwendbar:
[mm] x^{\varphi(7)}\equiv [/mm] 1 mod 7
[mm] x^{\varphi(10)}\equiv [/mm] 1 mod 10
[mm] x^{\varphi(9)}\equiv [/mm] 1 mod 9 ?
und wie gehts dann weiter?
vielen lieben dank schonmal für eure hilfe! =)
lg sunny
|
|
| |
|
Hallo sunny,
> Lösen Sie das folgende lineare Kongruenzsystem
> [mm]x\equiv[/mm] -1 mod 7
> [mm]x\equiv[/mm] 2 mod 10
> [mm]x\equiv[/mm] 17 mod 9
>
> mit Hilfe des "kleiner Satz von Fermat"-Ansatzes
Komische Aufgabe. Vielleicht auch nur, weil man solche Systeme ja normalerweise mit Euklid löst. Die Lösung lautet jedenfalls [mm] x\equiv 62\mod{630}. [/mm] Soviel vorab und zur Kontrolle.
> hallo alle zusammen!
>
> leider stehe ich gerade völlig aufm schlauch bei der
> aufgabe...
>
> beginnt man vielleicht so:
>
> ggT(x,7)=1, ggT(x,10)=1, ggT(x,9)=1 => kleiner Fermat
> anwendbar:
[mm] \ggT(x,10)=\blue{2}\quad [/mm] !!
> [mm]x^{\varphi(7)}\equiv[/mm] 1 mod 7
>
> [mm]x^{\varphi(10)}\equiv[/mm] 1 mod 10
>
> [mm]x^{\varphi(9)}\equiv[/mm] 1 mod 9 ?
>
> und wie gehts dann weiter?
Gute Frage. Die mittlere Äquivalenz stimmt nicht. Es gilt [mm] x^{\varphi(\blue{5})}\equiv 1\mod{\blue{5}}.
[/mm]
Um nun zu einer Aussage zu kommen, kann man wohl folgern [mm] x^{12}\equiv 1\mod{315}, [/mm] oder noch besser [mm] x^{6}\equiv 1\mod{63}\ \wedge\ x^4\equiv 1\mod{5}.
[/mm]
Wie man von da zur Lösung kommt, erschließt sich mir allerdings nicht. Habt Ihr die Methode mal an einem anderen Beispiel probiert/vorgeführt bekommen/berechnet?
Dann würde mich das Beispiel interessieren.
> vielen lieben dank schonmal für eure hilfe! =)
Ich lasse die Frage halboffen. Vielleicht weiß jemand mehr - ich hätte da gewisse Verdächtige im Kopf... 
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:38 So 10.07.2011 | | Autor: | felixf |
Moin,
> > Lösen Sie das folgende lineare Kongruenzsystem
> > [mm]x\equiv[/mm] -1 mod 7
> > [mm]x\equiv[/mm] 2 mod 10
> > [mm]x\equiv[/mm] 17 mod 9
> >
> > mit Hilfe des "kleiner Satz von Fermat"-Ansatzes
>
> Komische Aufgabe. Vielleicht auch nur, weil man solche
> Systeme ja normalerweise mit Euklid löst.
Ja, bzw. meistens redet man dann vom chinesischen Restsatz  Dessen konstruktiver Beweis, der Euklid verwendet, liefert dann die Loesung.
> Die Lösung
> lautet jedenfalls [mm]x\equiv 62\mod{630}.[/mm] Soviel vorab und zur
> Kontrolle.
>
> > hallo alle zusammen!
> >
> > leider stehe ich gerade völlig aufm schlauch bei der
> > aufgabe...
> >
> > beginnt man vielleicht so:
> >
> > ggT(x,7)=1, ggT(x,10)=1, ggT(x,9)=1 => kleiner Fermat
> > anwendbar:
>
> [mm]\ggT(x,10)=\blue{2}\quad[/mm] !!
>
> > [mm]x^{\varphi(7)}\equiv[/mm] 1 mod 7
> >
> > [mm]x^{\varphi(10)}\equiv[/mm] 1 mod 10
> >
> > [mm]x^{\varphi(9)}\equiv[/mm] 1 mod 9 ?
> >
> > und wie gehts dann weiter?
>
> Gute Frage. Die mittlere Äquivalenz stimmt nicht. Es gilt
> [mm]x^{\varphi(\blue{5})}\equiv 1\mod{\blue{5}}.[/mm]
... und $x [mm] \equiv [/mm] 0 [mm] \pmod{2}$.
[/mm]
> Um nun zu einer Aussage zu kommen, kann man wohl folgern
> [mm]x^{12}\equiv 1\mod{315},[/mm] oder noch besser [mm]x^{6}\equiv 1\mod{63}\ \wedge\ x^4\equiv 1\mod{5}.[/mm]
>
> Wie man von da zur Lösung kommt, erschließt sich mir
> allerdings nicht. Habt Ihr die Methode mal an einem anderen
> Beispiel probiert/vorgeführt bekommen/berechnet?
> Dann würde mich das Beispiel interessieren.
Mich wuerde das auch interessieren. Das ganze macht naemlich so fuer mich auch keinen Sinn...
Was man hoechstens machen koennte ist mit diskreten Logarithmen zu arbeiten, also eine Primitivwurzel [mm] $\alpha$ [/mm] modulo $kgV(7, 5, 9)$ zu nehmen, und einen Exponent $m$ finden so dass [mm] $\alpha^m$ [/mm] die (veraenderten) Kongruenzen loest. Aber dann muss man Euklid im Exponenten anwenden und das ganze ist mehrmals so kompliziert als wenn man Euklid einfach direkt verwendet.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:58 So 10.07.2011 | | Autor: | reverend |
Moinsen,
> > Komische Aufgabe. Vielleicht auch nur, weil man solche
> > Systeme ja normalerweise mit Euklid löst.
>
> Ja, bzw. meistens redet man dann vom chinesischen Restsatz
> Dessen konstruktiver Beweis, der Euklid verwendet,
> liefert dann die Loesung.
Letztlich war entweder Euklid doch ein Chinese, oder die chinesische Mathematik nur eine der Ausformungen der griechischen. Trotzdem haben die Chinesen offenbar keine Schulden. Da scheint manches doch inkongruent.
> > [mm]\ggT(x,10)=\blue{2}\quad[/mm] !!
Woraus folgt:
> ... und [mm]x \equiv 0 \pmod{2}[/mm].
Das hätte ich vielleicht erwähnen sollen.
> > Um nun zu einer Aussage zu kommen, kann man wohl folgern
> > [mm]x^{12}\equiv 1\mod{315},[/mm] oder noch besser [mm]x^{6}\equiv 1\mod{63}\ \wedge\ x^4\equiv 1\mod{5}.[/mm]
Nebenbei: die letzte Aussage ist identisch mit [mm] \ggT(x,5)=1.
[/mm]
> > Wie man von da zur Lösung kommt, erschließt sich mir
> > allerdings nicht. Habt Ihr die Methode mal an einem anderen
> > Beispiel probiert/vorgeführt bekommen/berechnet?
> > Dann würde mich das Beispiel interessieren.
>
> Mich wuerde das auch interessieren. Das ganze macht
> naemlich so fuer mich auch keinen Sinn...
Wir könnten einen Club bilden. Oder sogar einen Verein nach belgischem Recht. Da braucht man nur drei Gründungsmitglieder. Fehlt noch eins, wenn ich richtig gezählt habe. Letzteres ist ja in der Zahlentheorie verpönt. Man kommt ganz aus der Übung.
> Was man hoechstens machen koennte ist mit diskreten
> Logarithmen zu arbeiten, also eine Primitivwurzel [mm]\alpha[/mm]
> modulo [mm]kgV(7, 5, 9)[/mm] zu nehmen, und einen Exponent [mm]m[/mm] finden
> so dass [mm]\alpha^m[/mm] die (veraenderten) Kongruenzen loest. Aber
> dann muss man Euklid im Exponenten anwenden und das ganze
> ist mehrmals so kompliziert als wenn man Euklid einfach
> direkt verwendet.
Diskrete Logarithmen sind ein schönes Forschungsgebiet. Ob man darauf in einer Einführung in die Zahlentheorie schon viel Wert legen sollte, würde ich bezweifeln. Verzweifeln könnte ich allerdings gerade an der einfachen Aufgabe des Wurzelziehens. Was ist wohl [mm] \wurzel{1}\mod{n}, [/mm] wenn n nicht prim aber die Zerlegung unbekannt ist, und man andere Lösungen sucht als die trivialen +1, -1? Ich dachte, ich hätte da einen schönen Lösungsweg. Dieser Satz gehört allerdings zum Grundbestand der Zahlentheorie, wenn nicht aller Mathematik: Ich dachte, ich hätte... Ich halte das für den Fundamentalsatz der Beweislehre (auch wenn er selbst noch unbewiesen ist).
Übrigens ist 62 eine schlechte Antwort. Sie müsste doch ![[]](/images/popup.gif) 42 heißen, um allgemeingültig und damit hilfreich zu sein.
Sodale, (auch sodele)
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:15 Di 12.07.2011 | | Autor: | felixf |
Moinsen auch! :)
> Diskrete Logarithmen sind ein schönes Forschungsgebiet. Ob
> man darauf in einer Einführung in die Zahlentheorie schon
> viel Wert legen sollte, würde ich bezweifeln. Verzweifeln
> könnte ich allerdings gerade an der einfachen Aufgabe
> des Wurzelziehens. Was ist wohl [mm]\wurzel{1}\mod{n},[/mm] wenn n
> nicht prim aber die Zerlegung unbekannt ist, und man andere
> Lösungen sucht als die trivialen +1, -1? Ich dachte, ich
Nun, eine andere Loesung zu finden ist aequivalent dazu, einen echten Faktor von $n$ zu kennen.
Genauer: alle Loesungen von [mm] $\sqrt{1} \mod{n}$ [/mm] zu finden ist aequivalent dazu, $n$ in Primfaktoren zu zerlegen.
(Aequivalent heisst hier: es gibt einen deterministischen Algorithmus mit polynomieller Komplexitaet in Bezug auf die Groesse der Eingabe.)
So, und nun muss ich weiterarbeiten...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:27 Di 12.07.2011 | | Autor: | reverend |
Wieder so spät. Mein Zeitmanagement macht gerade Urlaub.
Hallo Felix,
> > Verzweifeln
> > könnte ich allerdings gerade an der einfachen Aufgabe
> > des Wurzelziehens. Was ist wohl [mm]\wurzel{1}\mod{n},[/mm] wenn n
> > nicht prim aber die Zerlegung unbekannt ist, und man andere
> > Lösungen sucht als die trivialen +1, -1? Ich dachte, ich
>
> Nun, eine andere Loesung zu finden ist aequivalent dazu,
> einen echten Faktor von [mm]n[/mm] zu kennen.
>
> Genauer: alle Loesungen von [mm]\sqrt{1} \mod{n}[/mm] zu finden ist
> aequivalent dazu, [mm]n[/mm] in Primfaktoren zu zerlegen.
Mist, erwischt... ![[pfeif]](/images/smileys/pfeif.gif "[pfeif]")
Ich hätte da eine Fassung, in der in einer Äquivalenzaussage modulo n ein Ausdruck in Gaußklammern vorkommt. Keine gute Idee, wenn man vereinfachen will.
Grüße
reverend
|
|
|
| |
|
> Lösen Sie das folgende lineare Kongruenzsystem
> [mm]x\equiv[/mm] -1 mod 7
> [mm]x\equiv[/mm] 2 mod 10
> [mm]x\equiv[/mm] 17 mod 9
>
> mit Hilfe des "kleiner Satz von Fermat"-Ansatzes
> hallo alle zusammen!
>
> leider stehe ich gerade völlig aufm schlauch bei der
> aufgabe...
>
> beginnt man vielleicht so:
>
> ggT(x,7)=1, ggT(x,10)=1, ggT(x,9)=1 => kleiner Fermat
> anwendbar:
>
> [mm]x^{\varphi(7)}\equiv[/mm] 1 mod 7
>
> [mm]x^{\varphi(10)}\equiv[/mm] 1 mod 10
>
> [mm]x^{\varphi(9)}\equiv[/mm] 1 mod 9 ?
>
> und wie gehts dann weiter?
>
> vielen lieben dank schonmal für eure hilfe! =)
>
> lg sunny
Hallo sunny,
ganz ohne die Anweisung zu befolgen, wie man da
vorgehen soll:
die dritte Bedingung kann man vereinfachen zu
[mm]x\equiv[/mm] -1 mod 9
Weil nach der ersten Bedingung auch
[mm]x\equiv[/mm] -1 mod 7
gelten soll und 7 und 9 teilerfremd sind, kann man
folgern, dass
[mm]x\equiv[/mm] -1 mod 63 (63=7*9)
Da alle 3 Moduli 7, 9 und 10 teilerfremd sind, muss die
allgemeine Lösung modulo 630 formuliert werden (630=7*9*10).
Lösungen der ersten zwei Bedingungen sind zum Beispiel
die Zahlen -1 und 63-1=62 - und siehe da: 62 hat
modulo 10 den gewünschten Rest 2. Also ist 62 eine Lösung,
und zwar die einzige wesentliche (modulo 630).
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:03 Mo 11.07.2011 | | Autor: | reverend |
*räusper*
> Da alle 3 Moduli 7, 9 und 10 teilerfremd sind, muss die
> allgemeine Lösung modulo 630 formuliert werden
> (630=7*9*10).
>
> Lösungen der ersten zwei Bedingungen sind zum Beispiel
> die Zahlen -1 und 63-1=62 - und siehe da: 62 hat
> modulo 10 den gewünschten Rest 2. Also ist 62 eine
> Lösung,
> und zwar die einzige wesentliche (modulo 630).
Verräter. Jetzt weiß sunny auch noch den Weg.
Sollen denn alle Geheimnisse der Mathematik öffentlich werden? Dann könnten wir sie ja gleich ins Internet stellen.
Übrigens, Al - was heißt eigentlich "die einzige wesentliche"? Alle Lösungen müssen doch in die gleiche Restklasse fallen. Vielleicht verstehe ich nur die Ausdrucksweise nicht?
Herzliche Grüße
reverend
|
|
|
| |
|
> *räusper*
*khmkhmm*
> > Da alle 3 Moduli 7, 9 und 10 teilerfremd sind, muss die
> > allgemeine Lösung modulo 630 formuliert werden
> > (630=7*9*10).
> >
> > Lösungen der ersten zwei Bedingungen sind zum Beispiel
> > die Zahlen -1 und 63-1=62 - und siehe da: 62 hat
> > modulo 10 den gewünschten Rest 2. Also ist 62 eine
> > Lösung,
> > und zwar die einzige wesentliche (modulo 630).
>
> Verräter. Jetzt weiß sunny auch noch den Weg.
Tut mir furchtbar leid. Ich hoffe sehr, dass sunny keinen
bleibenden Schaden wegen meiner Unvorsichtigkeit
davontragen wird ...
> Sollen denn alle Geheimnisse der Mathematik öffentlich
> werden? Dann könnten wir sie ja gleich ins Internet
> stellen.
Ich zweifle noch etwas daran, dass wir das könnten -
aber ich weiß ja noch nicht so genau, was du noch alles
kannst. Orientiere mich bitte rechtzeitig, bevor du das
RSA-Verfahren mittels deiner neuen Ideen killst !
> Übrigens, Al - was heißt eigentlich "die einzige
> wesentliche"? Alle Lösungen müssen doch in die gleiche
> Restklasse fallen. Vielleicht verstehe ich nur die
> Ausdrucksweise nicht?
Das war wohl eine Art von Dupleonasmus (for dummies).
LG Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:22 Mo 11.07.2011 | | Autor: | reverend |
Hallo Al,
mein Lieblings-Mousepad trägt die Aufschrift "der frühe Vogel kann mich mal". Soviel vorab. *chchmpch(-)*
> > Verräter. Jetzt weiß sunny auch noch den Weg.
>
> Tut mir furchtbar leid. Ich hoffe sehr, dass sunny keinen
> bleibenden Schaden wegen meiner Unvorsichtigkeit
> davontragen wird ...
Ja, hoffen wir das.
> > Sollen denn alle Geheimnisse der Mathematik öffentlich
> > werden? Dann könnten wir sie ja gleich ins Internet
> > stellen.
>
> Ich zweifle noch etwas daran, dass wir das könnten -
> aber ich weiß ja noch nicht so genau, was du noch alles
> kannst. Orientiere mich bitte rechtzeitig, bevor du das
> RSA-Verfahren mittels deiner neuen Ideen killst !
Das war doch eine rhetorische Frage. Zumindestens Birch-Swinnerton-Dyer kann ich heute nicht mehr lösen. Falls Du allerdings eine Lösung parat hast, sollten wir Vorsicht walten lassen.
RSA ist Geschichte. Die haben schon vorgestern all meine Aktien gekauft, wenn ich meine Bank recht verstehe. Ich hatte meinen gesamten Barbestand in RSA investiert. Da dieser leider gerade negativ war, gehöre ich denen jetzt ganz. Die CIA und die Münchener Rück haben mich ironischerweise dazu beglückwünscht. S**bande. (Die Sarabande war übrigens historisch oft und eng mit der Gigue verbunden.)
> > Übrigens, Al - was heißt eigentlich "die einzige
> > wesentliche"? Alle Lösungen müssen doch in die gleiche
> > Restklasse fallen. Vielleicht verstehe ich nur die
> > Ausdrucksweise nicht?
>
> Das war wohl eine Art von Dupleonasmus (for dummies).
Du bist mit dem Pleonasmus per Du und vollkommen vertraut? Das ist erheblich, wenn nicht gar erklecklich und somit ekstatisch im eigentlichen Wortsinn. Oder sitze ich nur gerade Deinem Inventionismus gebundener Morphemkombinate auf?
Dennoch pax bonae noctis (aut idem)
reverend
|
|
|
| |
|
Also was rauskommt, wusste ich, weil wir im aufgabenteil vorher die kongruenzen mit dem chinesischen restsatz lösen sollten. hätte ich vl sagen sollen ;)
wir haben lösungshinweise bekommen, aber bis zum ende bin ich damit nicht gekommen:
[mm] x=c_{1}*M_{1}^{\varphi(m_{1})}+...+c_{k}*M_{k}^{\varphi(m_{k})} [/mm] mit
[mm] M_{i}=\bruch{m}{m_{i}} [/mm] für i=1,2,...,k
m=7*10*9=630 und [mm] m_{1}=7, m_{2}=10, m_{3}=9
[/mm]
Also folgt: [mm] (-1)*(\bruch{630}{7})^{\varphi(7)}+2*(\bruch{630}{10})^{\varphi(10)}-1*(\bruch{630}{9})^{\varphi(9)}
[/mm]
so und jetzt komme ich nicht weiter. jetzt soll man es ausrechnen und reduzieren. folgt nicht aus den brüchen hoch das phi überall 1 durch den kleinen fermat? dann würde man doch aber nicht auf das gewünschte ergebnis kommen....
und nein Al und reverend, ich habe natürlich keinen schaden davon getragen!!!
aber eure antworten haben mir leider nicht so wirklich weitergeholfen! :(
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:40 Di 12.07.2011 | | Autor: | felixf |
Moin!
> Also was rauskommt, wusste ich, weil wir im aufgabenteil
> vorher die kongruenzen mit dem chinesischen restsatz lösen
> sollten. hätte ich vl sagen sollen ;)
>
> wir haben lösungshinweise bekommen, aber bis zum ende bin
> ich damit nicht gekommen:
>
> [mm]x=c_{1}*M_{1}^{\varphi(m_{1})}+...+c_{k}*M_{k}^{\varphi(m_{k})}[/mm]
> mit
>
> [mm]M_{i}=\bruch{m}{m_{i}}[/mm] für i=1,2,...,k
>
> m=7*10*9=630 und [mm]m_{1}=7, m_{2}=10, m_{3}=9[/mm]
>
> Also folgt:
> [mm](-1)*(\bruch{630}{7})^{\varphi(7)}+2*(\bruch{630}{10})^{\varphi(10)}-1*(\bruch{630}{9})^{\varphi(9)}[/mm]
Aaaaah, jetzt weiss ich was gemeint ist. So geht das natuerlich schon, ist nur unpraktisch es auszurechnen
> so und jetzt komme ich nicht weiter. jetzt soll man es
> ausrechnen und reduzieren. folgt nicht aus den brüchen
> hoch das phi überall 1 durch den kleinen fermat? dann
Nein. Zum Beispiel ist $a := [mm] \frac{630}{7}$ [/mm] kongruent zu 0 modulo 10 und 9, und kongruent zu einer Einheit modulo 7. Also gilt [mm] $a^{\varphi(7)} \equiv [/mm] 1 [mm] \pmod{7}$, [/mm] jedoch [mm] $a^{\varphi(7)} \equiv [/mm] 0 [mm] \pmod{10}$ [/mm] und [mm] $\pmod{9}$.
[/mm]
> würde man doch aber nicht auf das gewünschte ergebnis
> kommen....
Nun: ausrechnen. Jeweils modulo 630. Die Potenzen kannst du z.B. mit binaerer Exponentiation gut ausrechnen.
LG Felix
|
|
|
| |
|
tut mir leid, aber irgendwie hab ichs immer noch nicht kapiert :( habe wohl grad n brett vorm kopf...:(
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:20 So 17.07.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
