Der kleiner Satz von Fermat. Sei m ∈ N und φ(m) = ∣ {a ∈ N ∣ 1 ≤ a ≤ m und ggT (a, m) = 1 } ∣.

Question

Sei \( m \in \mathbb{N} \) und \( \varphi(m)=\mid\{a \in \mathbb{N} \mid 1 \leq a \leq m \) und \( \operatorname{ggT}(a, m)=1\} \mid \).

(1) Zeigen Sie: Für jedes \( a \in \mathbb{Z} \) mit \( \operatorname{ggT}(a, m)=1 \) gilt \( a^{\varphi(m)} \equiv_{m} 1 \).

(2) Leiten Sie den kleinen Satz von FeRMAT ab: Für \( p \in \mathbb{P} \) und \( a \in \mathbb{Z} \) gilt \( a^{p} \equiv_{p} a \).

(3) Bestimmen Sie \( 2^{2014} \) modulo 2017 (als Element von \( \left.\{0,1, \ldots, 2016\}\right) \).

Hinweis. Betrachten Sie die Einheitengruppe von \( \mathbb{Z} / m \mathbb{Z} \) und benutzen Sie, was Sie in den Aufgaben 10.1, \( 10.2 \) und \( 10.3 \) gelernt haben.

Comments

Für (2) schau dir mal an, was Phi(p) mit p prim ist, also wieviele teilerfremde Zahlen es zu einer Primzahl zwischen 1 und p gibt.

---

Ist das der zu 2)?

"Für jede Primzahl p und alle a ∈ ℤ, die nicht Vielfaches von p sind, gilt: a^p-1 ≡ 1 mod p."

Answer 1

Da $$|(\mathbb Z/m \mathbb Z)^* | =\varphi (m)$$ folgt die a) aus 10.2.3. und 10.3.3 deines Übungsblattes: http://reh.math.uni-duesseldorf.de/~internet/LAI_WS1314/blatt10.pdf b) folgt aus a) mit $$\varphi(p)=p-1$$ für eine Primzahl p und da die Aussage für 0 gilt. c) siehe hier:https://www.mathelounge.de/78650/bestimmen-sie-2-2014-mod-2017