Kongruenz |
26.07.2006, 12:24 | landy | Auf diesen Beitrag antworten » | ||||
Kongruenz ich möchte hier gerne eine kleine konguzenzrechnung lösen aber ich weis nicht mehr weiter gegeben: beweise mithilfe der konguzenzrechnung, dass 2^512-1 durch 4147 teilbar ist ich habs mal mit modulo angeschrieben: so nun hab ich 2^512 umgeschrieben auf (2^2)^9 und die primfaktoren von 4147=11*13*29 nun komme ich nicht weiter (bin grad dabei mir die kongurenztheorie beizubringen aber das beispiel versteh ich nicht ganz) wär toll wenn mir da wer helven könnte |
||||||
26.07.2006, 12:59 | AD | Auf diesen Beitrag antworten » | ||||
Blöd nur, dass es nicht stimmt. Es ist nämlich . |
||||||
26.07.2006, 14:32 | klarsoweit | Auf diesen Beitrag antworten » | ||||
RE: kongurenz
Du meintest vermutlich: 2^(2^9) Helfen tut die Folge: a_1 = 2, |
||||||
26.07.2006, 15:09 | mYthos | Auf diesen Beitrag antworten » | ||||
BTW: Es heisst Kongruenz, nicht Kongurenz! Gr mYthos edit 20: und deshalb Titel geändert. |
||||||
27.07.2006, 08:42 | landy | Auf diesen Beitrag antworten » | ||||
@mYthos: danke! ich habs wohl immer flasch gelesen @Arthur Dent+klarsoweit: kannst du mir deinen rechenweg erklären ? Ich hab das Beispiel aus dem Buch: "Zahlentheorie für Einsteiger" und die Aufgabenstellung lautete in etwa "Zeige dass 2^512-1 ohne rest durch 4147 teilbar ist". Aber da ich kein studierter Mathematiker bin versteh ich einiges noch nicht ganz. Ich finde es aber hochintressant wie man so mit riesigen Zahlen sehr einfach herumhantieren kann. mod rules |
||||||
27.07.2006, 08:57 | AD | Auf diesen Beitrag antworten » | ||||
Steht doch alles da:
Dieses Verfahren liefert . Du brauchst , führst also die Iteration genau 9-mal aus. |
||||||
Anzeige | ||||||
|
||||||
27.07.2006, 09:34 | landy | Auf diesen Beitrag antworten » | ||||
@Atrtur Dent: Was bedeutet Iteration ? und gibt es nicht einen einfacheren weg um den Rest zu berechnen ? Mit dieser Methode entstehen ja doch wieder große Zahlen! |
||||||
27.07.2006, 09:42 | klarsoweit | Auf diesen Beitrag antworten » | ||||
Nein, wieso? Du fängst mit a_1 = 2 an und bildest den Rest bei Division durch 4147. Das ist natürlich 2. Dann quadrierst du das Ergebnis und bildest wieder den Rest, usw. Das machst du 9-mal und bist beim Rest für angekommen. |
||||||
27.07.2006, 10:11 | Lazarus | Auf diesen Beitrag antworten » | ||||
Denn dann bist du beim Rest für angekommen, nicht bei und auch noch nicht bei . Dazu musst dus nochmal machen. |
||||||
27.07.2006, 11:07 | klarsoweit | Auf diesen Beitrag antworten » | ||||
Lazarus: möglicherweise hast du mich mißverstanden. Man fängt mit a_1 an und macht den Rekursionsschritt einmal, dann ist man bei a_2 angekommen. Macht man den Rekursionsschritt 9-mal, dann ist man logischerweise bei a_10 angekommen. Und das ist eben der Rest von . |
||||||
27.07.2006, 13:41 | landy | Auf diesen Beitrag antworten » | ||||
@klarsoweit danke ich hab das kapietel jetzt nocheinmal durchgearbeitet und habs jez kapiert! ich habs mal in excel ausprobiert und als bild eingefügt edit: -1 hab ich vergessen ! |
||||||
27.07.2006, 13:52 | AD | Auf diesen Beitrag antworten » | ||||
Richtig. Und falls der Exponent mal keine Zweierpotenz ist, kann man das Verfahren modifiziert dennoch nutzen, siehe hier. |
||||||
27.07.2006, 13:59 | landy | Auf diesen Beitrag antworten » | ||||
ich wollte nochmal abschliesend allen danken die geholfen haben das problem zu lösen ! Big THX @all |
||||||
27.07.2006, 14:17 | Lazarus | Auf diesen Beitrag antworten » | ||||
Ja da hab ich dich missverstanden. Tut mir leid, alles klar. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|