…sehr schmerzhaft
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
F2005 - III-4: Wurzelbehandlung
Wie geht denn das? Damit ich mehr Antworten kriege, habe ich die Angabe abgeschrieben:
Die Gleichung X^2=1 hat in Z221 wegen n=221=13(<-!!!)*17 und der Primheit der Faktoren 13 und 17 genau vier Lösungen. Dabei sind 1 und 220=-1 offensichtliche, also “tirviale” Lösungen.
- Bestimmen Sie mittels modularer Arithmetik die beiden anderen, also die “nicht-trivialen” Lösungen.
- Zeigen Sie, wie die Kenntnis (von einer) dieser beiden “nichttrivialen” Lösungen zur Faktorisierung von n=221 verwendet werden kann, falls man die (oben gegebene) Faktorisierung nicht kennt.
- Zeigen Sie, wie die Kenntnis von Phi(221)=192 ebenfalls zur Faktorisierung von n=221 benutzt werden kann.
-
X^2 ≡ 1 mod 221
dann ist (X ≡ 1 mod 13 && X ≡ 1 mod 17) oder
(X ≡ 1 mod 13 && X ≡ -1 mod 17) oder
(X ≡ -1 mod 13 && X ≡ 1 mod 17) oder
(X ≡ -1 mod 13 && X ≡ -1 mod 17) oder
naja, 2 der loesungen kennst du ja, nun rate mal was hier nun die trivialen sind. der rest ist dann einfach eggt rechnen und spass haben
-
versteh ich auch nich. werd mir das aber noch irgendwo anlesen
-
Tipp: nimm die multiplikativitaet von Phi her. Der knackpunkt: ausmultiplizieren ohne Zahlen einzusetzen. Dann hast du ne quadratische Gleichung da stehen. wenn du dann noch sorgfaelltig aufloesst, solltest du drauf kommen-
ad 2):
x^2 ≡ 1 mod 221 <=>
x^2 -1 ≡ 0 mod 221 <=>
(x-1)(x+1) ≡ 0 mod 221 <=>
(x-1)(x+1) = n* 221 für ein n∈N
Wie man daraus jetzt die Faktorisierung bekommt, sollte klar sein.
Falls es doch nicht so klar ist, hier ein kleiner Tipp:
ggT(x+1, n)*ggT(x-1,n) = n
Beim Beweis hilft es zuerst den Fall zu betrachten, dass x gerade ist.
Könntest du das mit dem eggT genauer erklären (Zahlenbeispiel?), damit ich auch Spaß habe? Danke im Voraus!
er meint erweiterter euklid …
also sowas wie:
221 1 0 |
120 0 1 |1
101 1 -1 |1
19 -1 2
.
.
.
mach mal chin. reste satz mit
X ≡ 1 mod 13
X ≡ -1 mod 17
und
X ≡ -1 mod 13
X ≡ 1 mod 17
@MatthiasM:
Wenn du jetzt noch nicht weisst was der eggT ist, dann solltest du dich bis nächsten Freitag derb reinstressen…
musser net … sowas wie eggT bzw. egdc ist glaub auch nur ne erfindung, weils nahe liegt es so zu nennen … aber diese begriffe gibts in wirklichkeit nicht … solange einem erweiteter euklid was sagt ist alles in butter …
ok, wenn ihm der was sagt und er ihn anwenden kann…
Aber wenn ihm das auch nix sagt, dann is jetzt echt Stress angesagt beim lernen - bei meinem ersten mal war ich nämlich auch ca 2 Wochen vorher dabei den erw. Euklid zu lernen, und das war dann ein Griff ins Klo (die Klausur)
Edit: is 'n bissl offtopic hier - vielleicht sollte ich mein Moral-Apostel-Gen mal wieder 'n bissl mehr kontrollieren 
How how - immer langsam mit den jungen Pferden!!!
Ich weiß sehr wohl, was der eggT ist, habe ihn auch schon beim Erstversuch (4 Punkte haben gefehlt 
) erfolgreich angewendet. Leider verstehe ich nicht, wie ich hier die Lösungen des eggT kombinieren soll. Wie das bei Multiplikation und Determinantenberechnung geht, weiß ja jeder (haben wir in den Übungen gemacht), aber wie kombiniere ich die Lösungen bei der Wurzelberechnung? Was sagt denn hier der Chinesische Restesatz aus und was nutzt mir das?
Dann ist ja alles gut :cheesy:
Der chinesische Restesatz besagt, dass das eine eindeutige Loesung hat mod 221.
Auf die kommst du, indem du sagst:
a * 13 + b * 17 = 1
a und b bestimmst du mit dem eeA.
Dann baust du dir:
-1 * a * 13 + 1 * b * 17 = gesuchte Loesung.
a * 13 war 1 mod 17 und b * 17 war 1 mod 13.
Und das, was du da nun kriegst ist also jetzt -1 mod 17 und 1 mod 13.