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