Warum gilt bei der Modulorechung folgendes?

Erste Frage Aufrufe: 561     Aktiv: 26.10.2020 um 01:16
0

Gemäss kleiner Satz von Fermat gilt, wenn a und die Primzahl (im Beispiel 5) teilerfremd sind:

\(a^4 \equiv 1 \pmod{5}\)

Nun ist mir aufgefallen es gilt auch:

\(a^{25*4} \equiv 1 \pmod{25*5}\)

Wie lässt sich dies allgemein beweisen?

Vielen Dank für Ihre Hilfe.

Diese Frage melden
gefragt

Punkte: 10

 
Kannst Du bitte konkretisieren, was genau du "allgemein" beweisen willst?
Frag nur, weil z.B. \(a^{26*4}\equiv1(mod 26*5)\) ja nicht gilt.
Welche Forderungen stellst Du also an den Faktor?   ─   3des 25.10.2020 um 13:20
a teilerfremd 5 (bzw. i.A. teilerfremd p)   ─   jojoliese 25.10.2020 um 13:22
Dachte dabei an die 25, nicht an a oder p, für a und p ergibt sich das ja schon aus dem kleinen Fermat :)
Soll 25 allgemein für \(p^2\) stehen?
Oder soll das nur speziell für den Faktor 25 bewiesen werden?   ─   3des 25.10.2020 um 13:23
Allgemein ausgedrückt:
p ist eine Primzahl
a und p sind teilerfremd
\( a^{(p^k)*(p-1)}\equiv 1 \pmod{p^k*p}\)   ─   paulvogt1 25.10.2020 um 13:25
Du solltest dir Mal was zu Primitivwurzeln durchlesen, das könnte dich weiterbringen   ─   jojoliese 25.10.2020 um 13:28
Danke für deinen Tipp, werde ich anschauen. Ich habe mir noch folgendes überlegt:
\( a^4 mod 5 = 1\). Dies wissen wir ja aufgrund von Fermat.
\( (a*a*a*a) mod 5 = 1\)
Dann muss ja auch wenn dieses 4a "Paket" hoch 25 gerechnet wird:
\( (a*a*a*a)^{25} mod 5 = 1\)
Dann sollte dies ja auch ergeben:
\( (a*a*a*a)^{25} (mod 25*5) = 1\)
Für mich erscheint es logisch, jedoch finde ich keinen allgemeinen Beweis.   ─   paulvogt1 25.10.2020 um 13:34
So einfach ist das leider nicht.
Weil \((a∗a∗a∗a)\mod5=1\) gilt, und für \(1^{25}=1\) gilt, gilt auch \((a∗a∗a∗a)^{25}\mod5=1\), der Schritt zu \((a∗a∗a∗a)^{25}\mod(25*5)=1\) ist aber ungleich schwieriger...   ─   3des 25.10.2020 um 13:38
Hab mal ein bisschen damit rum gespielt und bin noch zu keinem brauchbaren Ergebnis gekommen, würde aber mittlerweile behaupten, daß sich das sogar noch weiter verallgemeinern läßt zu:
\(a^{p_1p_2...p_n(p-1)}\equiv1(\mod(p_1p_2...p_np))\) solange a teilerfremd zu allen \(p_x\) ist und alle \(p_x\) prim sind   ─   3des 25.10.2020 um 23:37
Kommentar schreiben
1 Antwort
1

Ich beziehe mich hier mal auf die beiden Vermutungen, die in den Kommentaren geäußert wurden.

 

Die erste Vermutung ist korrekt. Nach dem Satz von Euler gilt

\( a^{p^k(p-1)} \equiv a^{\varphi (p^k \cdot p)} \equiv 1 \ \ (mod \ \ p^k \cdot p) \)

für \( ggT(a,p)=1 \).

 

Die zweite Vermutung gilt im Allgemeinen leider nicht. Beispielsweise ist

\( 5^{3 \cdot (2-1)} \equiv 5 \not \equiv 1 \ \ (mod \ \ 3 \cdot 2) \)

obwohl \(2,3 \in \mathbb{P}\) und \( ggT(5,3)=ggT(5,2)=1 \) gilt.

Oder auch

\( 3^{5 \cdot (7-1)} \equiv 29 \not \equiv 1 \ \ (mod \ \ 5 \cdot 7) \)

obwohl \(5,7 \in \mathbb{P} \) und \( ggT(3,5)=ggT(3,7)=1 \) gilt.

Diese Antwort melden
geantwortet

Student, Punkte: 7.02K

 

Kommentar schreiben