Chinesischer Restsatz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:06 Sa 27.04.2013 | | Autor: | DieNase |
| Aufgabe 1 | Ubung 65. Berechne (ohne Taschenrechner) in Z60
[mm] 14^{2^{32}}
[/mm]
Hinweis: Der Satz von Euler-Fermat ist nicht sofort anwendbar (warum?). Man kann
aber wie folgt vorgehen: Zerlege 60 = 22 ·3 ·5. Bestimme [mm] 14^{2^{32}} [/mm] mod 4, [mm] 14^{2^{32}} [/mm] mod 3,
[mm] 14^{2^{32}} [/mm] mod 5, und verwende den chinesischen Restsatz, um daraus 14(232) mod 60 zu
bestimmen. |
| Aufgabe 2 | ¨Ubung 60. L¨ose die Gleichung:
[mm] 4x^{2} [/mm] + 5x + 3 = 0 mod 69.
Hinweis: Zerlege 69 = 3 · 23 und l¨ose zuerst die Gleichung in Z3 und Z23. Bestimme dann
mit dem Chinesischen Restsatz die L¨osungen in Z69.
(4P.) |
Zu 1:
es gilt das der ggt(14,60) != 1 somit ist doch euler fermat nicht anwendbar.
jedoch ist doch auch bei ggt(14,4) das ding nicht anwendbar da der ggT() != 1 ist. Wieso ist 14,4 moeglich aber 14,60 nicht?
bzw welche bedingung muss noch gelten?
zu 2:
Wie loese ich eine Gleichung mit quadrat in einer modular Rechnung?
fuer anregungen waere ich sehr dankbar.
mfg
Christoph
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo Christoph, ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
Das sind nicht die leichtesten Aufgaben, wenn es sich noch um die Einführung in die Zahlentheorie dreht. Aber sie sind machbar.
> Ubung 65. Berechne (ohne Taschenrechner) in Z60
> [mm]14^{2^{32}}[/mm]
> Hinweis: Der Satz von Euler-Fermat ist nicht sofort
> anwendbar (warum?). Man kann
> aber wie folgt vorgehen: Zerlege 60 = 22 ·3 ·5.
Benutze doch bitte die Formeldarstellung.
[mm] 60=2^2*3*5
[/mm]
Allerdings zerschießt der Formeleditor im Moment vor allem zitierte Formeln des öfteren. Das ist in Arbeit.
Bestimme
> [mm]14^{2^{32}}[/mm] mod 4, [mm]14^{2^{32}}[/mm] mod 3,
> [mm]14^{2^{32}}[/mm] mod 5, und verwende den chinesischen Restsatz,
> um daraus 14(232) mod 60 zu
> bestimmen.
> ¨Ubung 60. L¨ose die Gleichung:
> [mm]4x^{2}[/mm] + 5x + 3 = 0 mod 69.
> Hinweis: Zerlege 69 = 3 · 23 und l¨ose zuerst die
> Gleichung in Z3 und Z23. Bestimme dann
> mit dem Chinesischen Restsatz die L¨osungen in Z69.
> (4P.)
>
> Zu 1:
> es gilt das der ggt(14,60) != 1 somit ist doch euler
> fermat nicht anwendbar.
Das ist wohl ein [mm] \not=.[/mm] \not= oder \neq.
> jedoch ist doch auch bei ggt(14,4) das ding nicht anwendbar
> da der ggT() != 1 ist. Wieso ist 14,4 moeglich aber 14,60
> nicht?
Für Zweierpotenzen gelten ein paar Besonderheiten. Schau das mal im Skript nach. Die brauchst Du hier aber eigentlich nicht. 14=2*7; was passiert also [mm] \mod{4}, [/mm] wenn Du überhaupt nur einmal quadrierst?
> bzw welche bedingung muss noch gelten?
>
> zu 2:
> Wie loese ich eine Gleichung mit quadrat in einer modular
> Rechnung?
Gute Frage. Wenn es dazu eine allgemeine Vorgehensweise gäbe, wäre Dein Handy und Dein Internet nicht mehr sicher. Wenn man das wüsste, könnte man große Zahlen faktorisieren.
Hier sollst Du also wohl "zu Fuß" vorgehen, sprich: ausprobieren. Für den Modul 23 ist das schon ungemütlich. Glücklicherweise gibt es da nur eine Lösung.
Anders allerdings [mm] \mod{3}...
[/mm]
Was heißt das für den chin.Restsatz?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:23 Sa 27.04.2013 | | Autor: | DieNase |
also bsp. 2 mit modulo hab ich jetzt mal angefangen:
und umgeschrieben fuer modulo 3 wiefolgt
[mm] x^{2} [/mm] +2x + 0 = 0 mod 3
demfzufolge ist
x*x = -2x
x*x = 1*x
0 waere jetzt moeglich sowie 1 als ergebnis. Sehe ich das richtig? nachdem 0 die trivial loesung ist lass ich sie weg und habe 1.
fuer mod 23 hab ich gleich umgeformt und bin bei der Gleichung
4x*x = -5x - 3
4x*x = 18x +20 (mit der inverse von 4 das waere 6 multipliziert)
x*x = 16x + 5
und jetzt muesste ich fuer x ausprobieren.
Ergebnis ist 8.
waere das richtig so?
ich dachte wenn ich bis hierher komme waere alles ganz einfach. Leider nicht. Ich haenge wieder. Ich habe alle informationen aber weis jetzt nix damit anzufangen.
|
|
|
| |
|
Hallo nochmal,
> also bsp. 2 mit modulo hab ich jetzt mal angefangen:
>
> und umgeschrieben fuer modulo 3 wiefolgt
> [mm]x^{2}[/mm] +2x + 0 = 0 mod 3
Das kann man doch schön faktorisieren: [mm] x(x+2)\equiv 0\mod{3}
[/mm]
> demfzufolge ist
> x*x = -2x
> x*x = 1*x
>
> 0 waere jetzt moeglich sowie 1 als ergebnis. Sehe ich das
> richtig?
Das ist richtig.
> nachdem 0 die trivial loesung ist lass ich sie weg
> und habe 1.
Nein, hier gibt es nichts Triviales. Die quadratische Gleichung hat in [mm] \IZ_3 [/mm] eben zwei Lösungen.
> fuer mod 23 hab ich gleich umgeformt und bin bei der
> Gleichung
> 4x*x = -5x - 3
> 4x*x = 18x +20 (mit der inverse von 4 das waere 6
> multipliziert)
> x*x = 16x + 5
>
> und jetzt muesste ich fuer x ausprobieren.
> Ergebnis ist 8.
Stimmt.
> waere das richtig so?
Hinterher wird immer behauptet, das hätte man leicht sehen können. Und hinterher sieht mans auch leicht. Nachdem Du mit dem Inversen von 4 multipliziert hast, könntest Du auch schreiben:
[mm] x^2-16x-5\equiv x^2-16x+64=(x-8)^2\equiv 0\mod{23}
[/mm]
Dann ist auch klar, dass [8] die einzige Lösung ist.
> ich dachte wenn ich bis hierher komme waere alles ganz
> einfach. Leider nicht. Ich haenge wieder. Ich habe alle
> informationen aber weis jetzt nix damit anzufangen.
Na, Du brauchst jetzt alle Zahlen [mm] \mod{69}, [/mm] die entweder [mm] 0\mod{3} [/mm] und [mm] 8\mod{23} [/mm] oder aber [mm] 1\mod{3} [/mm] und [mm] 8\mod{23} [/mm] sind.
Wie sollt Ihr denn Lösungen nach dem chin.Restsatz bestimmen? Über den erweiterten euklidischen Algorithmus? Oder "einfach so" - also z.B. über (gezieltes) Probieren? Das ginge hier ja einfach. Die Lösungen sind [31] und [54].
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:33 Sa 27.04.2013 | | Autor: | DieNase |
also dake fuer deine antwort.
Zu dem satz hinterher sieht man es :)
Ach leck mich mathe  So verdammt typisch ich rechne 23 werte durch schoen mit dem Holzhammer durch die Wand. Aufgarkeinen fall die eingebaute Tuere nuetzen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:59 Sa 27.04.2013 | | Autor: | reverend |
Hallo Christoph,
> Zu dem satz hinterher sieht man es :)
Schonmal vorab: ich habs vorher auch nicht gesehen.
> Ach leck mich mathe So verdammt typisch ich rechne 23
> werte durch schoen mit dem Holzhammer durch die Wand.
> Aufgarkeinen fall die eingebaute Tuere nuetzen.
Manche Türen bedeuten erhebliche Umwege...
Und wenn man schon hinrennt, dann ist bestimmt gerade geschlossen oder so.
Ich hab ehrlich gesagt einfach meine Tabellenkalkulation angeschmissen.
Hätt ich von Hand oder im Kopf rechnen müssen, hätte ich ehrlich gesagt [mm] x^2-5 [/mm] ausgerechnet und dann überlegt, ob das zufällig [mm] =\pm7x [/mm] ist. Das hätte ich dann ja maximal für [mm] 0\le x\le11 [/mm] ausprobieren müssen.
Sobald ich eine Lösung hätte (vor allem, wenn sie klein ist), hätte ich faktorisiert - so wie sonst auch bei Polynomen.
Das ist aber wieder so ein Thema mit Tür und Umweg. Wenn ich - wie hier - erst bei x=8 fündig geworden wär, hätte ich doch lieber noch die letzten drei Möglichkeiten gerechnet, statt zu faktorisieren.
In Übungsaufgaben, die man ohne Technik lösen soll, empfiehlt sich bei solchen quadratischen Aufgaben aber oft, die quadratische Ergänzung zu versuchen. Oft sind die nämlich so gestellt, dass es nur eine Lösung gibt.
Grüße
reverend
|
|
|
|
