Größter gemeinsammer Teiler von (24^(39) + 1) und 371

Question

Aufgabe:

Ich möchte den ggT(24^39+1;371) ermitteln.

Problem/Ansatz:

Gibt es eine Umformung, oder vergleichbares. Bitte keine Antworten nach dem Motto, gib das bei WolframAlpha ein, das Ziel sollte sein, sowas möglichst ohne technische Hilfe zu bewerkstrelligen...

Comments

371 = 7·53

Wie kannst du jetzt prüfen ob 24^39 + 1 durch 7 oder durch 53 oder gar durch beide Zahlen teilbar ist.

Gibt es da nicht etwas mit Modulo ?

---

Ich würde versuchen die Potenz irgendwie umzuschreiben, aber diese +1 verwirrt mich...

---

Angenommen 24^39 + 1 geht durch 7 zu teilen. Was müsste dann für ein Rest bleiben, wenn du 24^39 durch 7 teilst?

Kannst du dir das nicht irgendwie zunutze machen?

---

Da bin ich gerade etwas hilflos...

---

Angenommen 13 + 1 geht durch 7 zu teilen. Was müsste dann für ein Rest bleiben, wenn du 13 durch 7 teilst?

Angenommen 20 + 1 geht durch 7 zu teilen. Was müsste dann für ein Rest bleiben, wenn du 20 durch 7 teilst?

Kannst du das eventuell verallgemeinern?

Angenommen 7n + 6 + 1 geht durch 7 zu teilen. Was müsste dann für ein Rest bleiben, wenn du 7n + 6 durch 7 teilst?

Answer 1

Ein möglicher Weg ist der pow-mod-Algorithmus, wo man ohne große Zwischenergebnisse mit wenigen Schritten den Modulo-Wert von Potenzen bestimmen kann:

 24*1 mod 7 =3 ; 24² mod 7=2
3*2  mod 7 =6 ; 2²  mod 7=4
6*4  mod 7 =3 : 4²  mod 7=2
3*2  mod 7 =6

Der Iterationsrechner unter http://www.gerdlamprecht.de/Roemisch_JAVA.htm

rechnet das online vor:

Kleine Offsets beim Argument der Modulo-Funktion vergrößern auch das Ergebnis um diesen Offset:

5 mod 7 =5

(5+1) mod 7 =6

usw.

Wenn 24^39 mod 7 =6 ist, ist der Nachfolger (Offset 1) zunächst 7, aber 7 mod 7 ist 0 -> also kein Rest also durch 7 teilbar!

Mit 53 geht das nicht -> also bleibt 7 der einzige gemeinsame Teiler -> & das Endergebnis.