0 Daumen
1k Aufrufe

Wie kann man mit Hilfe des kleinen Fermat und den Defintionen der Kongruenzen zeigen, dass

ap ≡ a (mod p) ist mit a ∈ ℤ und p ∈ P

Dabei soll nicht die Phi- Funktion genutzt werden.

Ich würde mich über eure Antworten sehr freuen, da ich damit so gar nichts anfangen kann.. Ich habe große Probleme mit dem kleinen Satz des Fermat und allgemein dem Rechnen mit Kongruenzen :(

Avatar von

Das was da steht ist der "kleine Fermat", deine Frage ist also nicht sehr sinnvoll. Schau lieber nochmal drüber.

Aber der kleine Fermat ist doch

ap-1≡ 1 (mod p) ?!

ap ≡ a (mod p) ist mit a ∈ ℤ und p ∈ P

ap -a ≡ 0 (mod p) ist mit a ∈ ℤ und p ∈ P

a(ap-1 -1) ≡ 0 (mod p) ist mit a ∈ ℤ und p ∈ P

Hilft das ?

ap-1≡ 1 (mod p) ?!

ap-1 - 1 ≡ 0 (mod p) 

1 Antwort

0 Daumen

ja das ist eigentlich nur eine andere Variante, wobei du die Einschränkungen für \(a\) nicht aufgeschrieben hast. Wenn es echt darum geht nur auf die andere Variante zu kommen dann mach eine Fallunterscheidung:

Fall 1: \(a\) wird durch \(p\) geteilt.

Fall 2: \(a\) wird nicht durch \(p\) geteilt.

Beim zweiten Fall kannst du dir die bekannte Variante verwenden und durch multiplizieren beider Seiten mit \(a\) erhältst du die Aussage. Fall 1 sollte klar sein.

Gruß

Avatar von 23 k

Kann ich folgendermaßen vorgehen?:

Ich nutze den kleinen Satz von Fermat, um zu zeigen, dass gilt : ap≡ a (mod p) für a ∈ℤ und p∈ℙ :

Der kleine Satz von Fermat besagt, dass gilt eine Zahl a ∈ℤ hoch einer Primzahl p-1 hat den selben Rest wie die Zahl 1, wenn wir beide Seiten durch p teilen. Also

ap -1≡1 (mod p) , wenn gilt p teilt nicht a

Dann ist ap-1 nach den Potenzgesetzen ap * a-1

Also folgt daraus: a* a-1 ≡ 1 mod p.

Ich darf bei Kongruenzen beide Seiten mit einer Zahl multiplizieren, also multipliziere ich beide Seiten mit a und erhalte

a* a-1 ≡ 1 mod p. I *a

a≡ a (mod p)

und somit ist die Aussage gezeigt.

Stimmt das so???

Ja das ist in Ordnung allerdings musst du die Aussage für alle ganzen Zahlen \(a\) zeigen, also auch den von mir genannten 1. Fall.

Heißt das, dass ich zeigen muss das das sowohl gilt, wenn meine Primzahl grade als auch ungrade ist?Oder muss ich zeigen dass (a+1)p≡ ap +1 ≡ a+ 1 mod p ist?Sorry aber ich komme jetzt absolut nicht drauf, wie ich da vorgehe :/

Nein ich versteh auch nicht woher diese Verwirrung kommt weil

1. Ich dir ausführlich hin geschrieben habe welche Fälle du unterscheiden musst

2. Du bereits den Fall 2 gezeigt hast, und dort selbst angemerkt hast für welche \(a\) es nun gilt. Welche \(a\) bleiben also übrig? Diese Frage lässt sich ohne Nachdenken nur durch lesen beantworten.

Ich verstehe noch nicht so ganz wie man das genau für den 1. Fall zeigt.

Wenn die Zahl teilbar ist dann sollte kein Rest mehr da sein oder?

Dann ist der Rest 0, aber ändert das denn die Aussage? Ich habe das Rechnen mit Kongruenzen so verstanden, dass man untersucht, ob ap und a bei Divison durch p denselben Rest lassen. Ist a nun durch p teilbar, dann ist der Rest ja 0. Aber dann muss doch auch ap geteilt durch p den Rest 0 ergeben und somit wäre doch  ap≡ a (mod p) auch wenn beide den Rest 0 haben? Oder gilt dann der Modulo nicht?

Ja genau das meinte ich, es ist zwar klar, dass in diesem Fall auf beiden Seiten 0 steht allerdings war es wie du siehst auch notwendig dies mal ausführlich aufzuschreiben.. Du hast also gezeigt dass die Behauptung für alle ganzen Zahlen \(a\) gilt und bist damit nun fertig :).

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
1 Antwort
0 Daumen
1 Antwort

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community