Wie kann ich das x in x^11 mod 67 = 1 einfach ausrechnen?


24.01.2021, 18:50

Edit: Möchte noch hinzufügen, dass eine Beispiellösung 2^6 bzw 64 ist.

3 Antworten

Separate Antwort: Natürlich kannst du auch alle Lösungen ausrechnen. Das geht folgendermaßen.

Stelle erstmal fest, dass du jede Zahl x eindeutig in der Form (a + 67*b) schreiben kannst, mit a und b aus N0, a<67. Dann stellst du fest, dass

x^11 = (a + 67*b)^11 = (a + 67*b) * (a + 67*b)^10 = a * (a + 67*b)^10 + 67*b*(a + 67*b)^10

ist. Also gilt:

x^11 (mod 67) = a * (a + 67*b)^10 (mod 67),

da der zweite Summand ein Vielfaches von 67 ist und daher verschwindet (mod 67).

Das kannst du jetzt mehrfach ausnutzen und stellst fest:

x^11 = a^11 (mod 67).

Du musst also nur noch Zahlen a = 0, 1, ..., 66 ausprobieren.

Wenn du das durch sukzessives Multiplizieren und Rechnung modulo 67 machst, bekommst du nie "unhandliche Zahlen". Du wirst jeden Rest einmal bekommen, d.h. jede der Zahlen 0...66 kommt genau einmal als Rest vor. Wie oft kommt nun der Rest 1 vor? Sicherlich für a=1, aber auch für a=64, a=9 oder a=14 - sonst noch Zahlen?

Damit sind alle Zahlen, die deine Gleichung oben erfüllen, x = a + 67*b mit einem beliebigen b\in N0 und a\in {1, 9, 14, (deine eigenen Berechnungen), 64}.

Woher ich das weiß:Studium / Ausbildung – Studium und Promotion in Angewandter Mathematik

Korrektur: Nicht jeder Rest kommt einmal vor. Der Rest 1 kommt mehrfach vor.

0

Ehrlich? Ich finde, x=1 ist eine tolle Lösung, da 1^11 = 1.

Woher ich das weiß:Studium / Ausbildung – Studium und Promotion in Angewandter Mathematik

Ich wage mal zu behaupten, dass es keine einfache Möglichkeit gibt, weil das unendlich viele Lösungen hat.

Interessant

1

Was möchtest Du wissen?