Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Für welches m gilt a^phi(m)+1 ≡ a mod m ?

Für welches m gilt a^phi(m)+1 ≡ a mod m ?

Universität / Fachhochschule

Elementare Zahlentheorie

Tags: Elementare Zahlentheorie, Euler-Funktion, Kongruenz, Kongruenzrelation, quadratfrei, restklassen, Satz von Euler-Fermat

Euler1000 aktiv_icon

19:13 Uhr, 29.11.2020

Hallo zusammen, ich muss für mein Mathestudium den Beweis (siehe Bild) erklären können. Leider kann ich manche Schritte nicht genau nachvollziehen.

Sei

φ

die Eulerfunktion.
Für welche m∈ℕ gilt

a^{φ (m) + 1}

≡

a mod m

für alle a∈ℤ ?

Der Fall

m = 1

ist logisch, denn die einzige Restklasse von 1 ist

[0]

. Dementsprechend müssen also

a^{φ (m) + 1}

und

a

in derselben Restklassen liegen.
Beim 2. Fall

(m

ist Quadratfrei), verstehe ich leider den Zusammenhang nicht.
Wenn ich das richtig sehe, dann wurde erstmal die Definition der Kongruenz angewendet. Denn

a^{φ} (m) + 1

und a sind genau dann kongruent, wenn

m | (a^{φ (m) + 1} - a)

und das kann man als Bruch schreiben so wie auf dem Bild. Und dann wurde ein Potenzgesetz verwendet, a ausgeklammert und das das

k

hinzugefügt (das würde sich beim ausmultiplizieren ja wieder wegkürzen).
Doch wofür wird das gemacht ? Warum muss ich zeigen, dass dies ein Produkt aus ganze Zahlen ist ?
Durch den Satz von Euler-Fermat kann ich

a^{φ (\frac{m}{k})}

durch 1 ersetzten, da a und

\frac{m}{k}

teilerfremd sind. Kann ich dann sagen, dass dies auch für

φ (m)

gilt, da

φ (m)

ein Vielfaches von

φ (\frac{m}{k})

ist ? Aber wenn ich dann

φ (m)

durch 1 ersetzte, dann würde im Zähler

1 - 1

stehen und das wäre null. Dann wäre aber das ganze Produkt null. Das würde keinen Sinn machen. Für was wird dann der Satz von Euler-Fermat genau verwendet ?
Den letzten Teil wiederum verstehe ich denke ich. Da wird per Widerspruchbeweis gezeigt, dass

m

quadratfrei sein muss, da sonst die Kongruenz nicht erfüllt ist.
Vielleicht kann mir jemand helfen. Ich wäre sehr dankbar für eine schnelle Antwort :-)

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Dreiecke und Kongruenz

HAL9000

19:47 Uhr, 29.11.2020

Sind

u, v

positive ganze Zahlen mit

u ∣ v

, und

a

eine beliebige ganze Zahl, dann ist

(a^{u} - 1) ∣ (a^{v} - 1)

.

Das wird hier genutzt für

u = φ (\frac{m}{k})

und

v = φ (m)

.

> Aber wenn ich dann

φ (m)

durch 1 ersetzte, dann würde im Zähler 1-1 stehen und das wäre null.

Warum solltest du so eine "Ersetzung" vornehmen wollen? Ich verstehe den Sinn dieses Gedankenspiels nicht, sowas ist doch kein Bestandteil des Beweises. :(

Euler1000 aktiv_icon

21:13 Uhr, 29.11.2020

Danke das habe ich jetzt verstanden. Ich habe mir noch andere Gedanken gemacht. Da der ggt(a,

\frac{m}{k}) = 1

ist folgt nach dem Satz von Euler-Fermat, dass

a^{v}

≡

1 mod \frac{m}{k}

ist. Das heißt,

\frac{m}{k}

ist ein Teiler von

a^{v} - 1

. Ich verstehe nur leider nicht warum ich zeigen muss das

\frac{a^{v} - 1}{\frac{m}{k}}

eine ganze Zahl ist , was bringt mir das hier für den Beweis ?

HAL9000

21:19 Uhr, 29.11.2020

Na das steht doch ausführlich im Scan - denk doch drüber nach: Es ist

\frac{a^{φ (m) + 1} - a}{m} = \frac{a}{k} \cdot \frac{a^{φ (m)} - 1}{m / k}

,

und wenn es wie dort beschrieben im Fall eines quadratfreien

m

gelingt zu zeigen, dass beide Faktoren rechts ganzzahlig sind, dann folgt daraus auch, dass die linke Seite ganzzahlig ist, was nichts weiter als

a^{φ (m) + 1} \equiv a mod m

bedeutet, also die Behauptung.

Und die gewünschte Ganzzahligkeit von

\frac{a^{φ (m)} - 1}{m / k}

folgt eben aus jener von

\frac{a^{φ (m / k)} - 1}{m / k}

, siehe oben.

Euler1000 aktiv_icon

21:36 Uhr, 29.11.2020

Stimmt danke ! Also muss ich erstmal zeigen, dass

a^{φ (m) + 1}

≡

a mod m

existiert, bevor ich beweise das es für

m

quadratfrei gilt ?

HAL9000

21:42 Uhr, 29.11.2020

Ich weiß nicht, warum du jetzt logisch wieder alles durcheinanderwirfst - nochmal:

Wenn

m

quadratfrei ist, DANN folgt

a^{φ (m) + 1} \equiv a mod m

für alle

a

, das wird doch da ausführtlichst gezeigt!!!!

Ganz zuletzt im Scan wird dann auch die Umkehrung gezeigt, d.h., dass es im Falle von nicht quadratfreien

m

zumindest ein

a

gibt, für das die Kongruenz nicht erfüllt ist: Nämlich durch Wahl von

a = p

, wobei jenes

p

eben quadratisch in Modul

m

enthalten sein soll.

Euler1000 aktiv_icon

13:45 Uhr, 03.12.2020

Mir war nicht klar, dass es sich um ein Äquivalenzbeweis handelt, aber das macht einiges deutlicher. Eine letzte Frage hätte ich noch: wenn

p^{φ (m)}

durch

p

teilbar ist. Warum folgt daraus dann, dass

p^{φ (m) + 1} - p

nicht durch

p^{2}

teilbar ist ? Ich habe versucht es mir anhand eines Beispiels zu verdeutlichen und da verstehe ich es auch:

z . B

für

p = 2, m = 12

. Dann ist

φ (12) = 4,

also

p^{φ (m) + 1} - p = 2^{5} - 2 = 30

und

p^{2} = 4

und 4 teilt nicht

30

. Ich kann mir nur nicht erklären warum.

HAL9000

14:47 Uhr, 03.12.2020

Distributivgesetz (ausklammern):

p^{φ (m) + 1} - p = p \cdot (p^{φ (m)} - 1) (*)

p^{φ (m)}

wegen

φ (m) \geq 1

durch

p

teilbar ist, die 1 aber nicht, so ist auch

(p^{φ (m)} - 1)

nicht durch

p

teilbar, folglich das gesamte Produkt (*) nicht durch

p^{2}

teilbar.

Euler1000 aktiv_icon

14:55 Uhr, 03.12.2020

Danke

!!

1521092

1520409

	Status: nicht eingeloggt	Noch nicht registriert?