M^c kongruent zu m mod n

Aufrufe: 75     Aktiv: 13.06.2021 um 19:14

0
Seien p,q zwei verschiedene Primzahlen mit n=pq und r=(p-1)(q-1). Sei weiterhin c aus den ganzen Zahlen mit c kongruent zu 1 mod r. Zeigen Sie, dass dann für jedes m aus den ganzen Zahlen gilt:

m^c kongruent zu m mod n
Diese Frage melden
gefragt

Punkte: 20

 
Kommentar schreiben
1 Antwort
0
Moin,
freut mich, dass jemand mal etwas zur Zahlentheorie ins Forum bringt. Ich würde bei dieser Aufgabe mit der zu zeigenden Kondition anfangen: \(m^c \equiv m \text{(mod n)} \). Von da aus kann man die Definition der Kongruenz anwenden: \(n|m^c-m\). Jetzt kann man auf der rechten Seite ein m ausklammern und in zwei Fälle unterscheiden: entweder n|m oder \(n|m^{c-1}-1\). Es gilt also: solange m kein vielfaches von m ist, bzw der ggT von n und m 1 ist, gilt der zweite Fall. Für den zweiten Fall kann man nun erneut die Definition der Kongruenz anwenden um \(m^{c-1}\equiv 1 \)(mod n) zu erhalten. Dabei fällt einem auf, dass diese Bedingung immer gilt, wenn sie dem Satz von Euler entspricht mit. \(a^{\phi(n)}\equiv1\) (mod n), mit ggT(a,n)=1. Es fällt auf, dass der Fall für ggT(m,n) \(\neq\) 1 bereits durch den ersten Fall mit n|m abgedeckt ist. Jetzt muss nur noch gelten: \(c-1=\phi(n)\) Durch anwenden der Rechenregeln mit der Eulerschen Phi-Funktion ergibt sich: \(c-1=\phi(p)\phi(q) = (p-1)(q-1)\). Jetzt muss nur noch gezeigt werden, dass c-1=(p-1)(q-1). Dafür können wir die gegebene Bedingung \(c \equiv 1\) (mod r) verwenden, oder \(rc-1\). Über die Definition von r kommt man relativ simpel zum gesuchten Ergebnis. 
Ich wüsste außerdem gerne, woher du die Aufgabe genommen hast, da es relativ schwierig ist an gute Zahlentheorie Aufgaben heranzukommen.
LG
Fix
Diese Antwort melden
geantwortet

Schüler, Punkte: 800

 

Hey fix,
Danke für deine Antwort. Die Aufgabe habe ich von der Uni. Könntest du mir vielleicht nochmal erklären wie genau du zeigst das c -1 = (p-1)(q-1)?
Gruß
  ─   user4e3d2f 13.06.2021 um 15:28

Ja klar, ich habe mich oben auch verschrieben, wie ich gerade merke. gegeben ist \(c\equiv1\)(mod r). Über die Definition des Modulo (\(\text{wenn } a\equiv b \text{ (mod m), dann gilt }m|a-b\)) folgt \(r|c-1\) und durch einsetzen von r \(\Rightarrow (p-1)(q-1)|c-1\). Das kann man umschreiben zu \(c-1=k(p-1)(q-1)\), sodass der Beweis abgeschlossen ist. Ich hoffe, dass nun alle Unklarheiten behoben sind.
LG
  ─   fix 13.06.2021 um 15:38

Ja, jetzt ist alles klar. Vielen Dank   ─   user4e3d2f 13.06.2021 um 19:14

Kommentar schreiben