Gleichung - Euler < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich habe gerade ein Problem folgendes nachzuvollziehen:
Man hat zwei Primzahlen p und q und das Produkt n = p * q
Nun gilt für jede Zahl m < n für jedes beliebige k die Gleichung
[mm] m^{k(p-1)(q-1)+1} [/mm] mod n = m
Ich frage mich nun, wie man darauf kommt.
Also wie man auf (p-1)(q-1) kommt, das wird wohl wegen
[mm] \phi(n) [/mm] = (p-1)(q-1) sein, richtig?
Sozusagen wäre es
[mm] m^{k*\phi(n) +1} [/mm] mod n = m
Ich weiß auch, dass für jedes natürliche k und für jede Primzahl p
[mm] k^{(p-1)} [/mm] = 1 mod p
ist.
Hm,..aber weiter fehlt mir wohl gerade Grundlagenwissen (oder ein zu großes Brett vor dem Kopf), um o.g. nachvollziehen zu können.
Würde mich über Hilfe sehr freuen!
Danke
Anna
|
|
| |
|
Hallo,
> Hallo,
>
> ich habe gerade ein Problem folgendes nachzuvollziehen:
> Man hat zwei Primzahlen p und q und das Produkt n = p * q
> Nun gilt für jede Zahl m < n für jedes beliebige k die
> Gleichung
> [mm]m^{k(p-1)(q-1)+1}[/mm] mod n = m
>
> Ich frage mich nun, wie man darauf kommt.
Das kommt wie so oft darauf an, was man zur Verfügung hat.
> Also wie man auf (p-1)(q-1) kommt, das wird wohl wegen
> [mm]\phi(n)[/mm] = (p-1)(q-1) sein, richtig?
> Sozusagen wäre es
> [mm]m^{k*\phi(n) +1}[/mm] mod n = m
Der Satz von Euler-Fermat
https://de.wikipedia.org/wiki/Satz_von_Euler
besagt, dass für zu n teilerfremde m gilt:
[mm] $m^{\varphi(n)}=1 \mod [/mm] n$.
Damit ist auch:
[mm] $m^{k\varphi(n)}=1^k=1 \mod [/mm] n$ für alle natürlichen Zahlen k.
Multiplikation mit m liefert dann das Gewünschte.
Der Satz von Euler-Fermat wiederrum ist ein Spezialfall des Satzes von Lagrange aus der Gruppentheorie.
> Ich weiß auch, dass für jedes natürliche k und für jede
> Primzahl p
> [mm]k^{(p-1)}[/mm] = 1 mod p
> ist.
Das gilt so nur für natürliche Zahlen k die zu p teilerfremd sind.
z.B. ist [mm] $p^{p-1} \equiv [/mm] 0 [mm] \mod [/mm] p$
> Hm,..aber weiter fehlt mir wohl gerade Grundlagenwissen
> (oder ein zu großes Brett vor dem Kopf), um o.g.
> nachvollziehen zu können.
>
> Würde mich über Hilfe sehr freuen!
>
> Danke
> Anna
>
>
|
|
|
| |
|
Hallo MaslanyFanclub,
vielen Dank für Deine Antwort!
> Der Satz von Euler-Fermat
> https://de.wikipedia.org/wiki/Satz_von_Euler
Ja, so war auch meine Denkrichtung also dann nicht so falsch (siehe Betreff), aber dazu noch eine Frage:
> besagt, dass für zu n teilerfremde m gilt:
> [mm]m^{\varphi(n)}=1 \mod n[/mm].
Du hast hier = geschrieben und nicht kongruent, aber der Satz besagt doch Kongruenz. Darf ich also einfach so wie Du es gemacht hast das [mm] \equiv [/mm] durch = ersetzen?
Und noch eine Frage: Der Satz hat ja zur Bedingung, dass ggT(m,n) = 1 ist, also m und n teilerfremd sind, ist das hier der Fall nur durch die Bedingung m < n?
Danke,
Anna
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:56 So 23.02.2014 | | Autor: | hippias |
> Hallo MaslanyFanclub,
>
> vielen Dank für Deine Antwort!
>
> > Der Satz von Euler-Fermat
> > https://de.wikipedia.org/wiki/Satz_von_Euler
>
> Ja, so war auch meine Denkrichtung also dann nicht so
> falsch (siehe Betreff), aber dazu noch eine Frage:
>
> > besagt, dass für zu n teilerfremde m gilt:
> > [mm]m^{\varphi(n)}=1 \mod n[/mm].
>
> Du hast hier = geschrieben und nicht kongruent, aber der
> Satz besagt doch Kongruenz. Darf ich also einfach so wie Du
> es gemacht hast das [mm]\equiv[/mm] durch = ersetzen?
Durch den Zusatz [mm] $\mod [/mm] n$ duerften Missverstaendnisse ausgeschlossen sein. Aber mit [mm] $\equiv$ [/mm] liegst Du auf jeden Fall richtig.
>
> Und noch eine Frage: Der Satz hat ja zur Bedingung, dass
> ggT(m,n) = 1 ist, also m und n teilerfremd sind, ist das
> hier der Fall nur durch die Bedingung m < n?
Natuerlich nicht. Dein Satz gilt so auch nicht: es muesste naemlich [mm] $p\neq [/mm] q$ vorausgesetzt werden; dann aber ist Deine urspruengliche Behauptung auch ohne $ggt(m,n)=1$ richtig.
>
> Danke,
> Anna
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:23 So 23.02.2014 | | Autor: | Anna-Lyse |
Hallo hippias,
vielen Dank für Deine Antwort!
Gruß
Anna
|
|
|
|
