Beweisen Sie (Satz von Euler)

Question

Aufgabe:

Seien a, n ∈ Z, n ≥ 2 mit ggT(a,n) = 1. Weiter seien r₁. r₁ ∈ N₀ mit r₁≡ r₂ (mod φ(n)) gegeben. Beweisen Sie, dass dann a^r1 mod n = a^r2 mod n gilt

Answer 1

Sei \(r_1\equiv r_2\) mod \(\varphi(n)\). Dann gibt es \(k\in\mathbb{Z}\)

mit \(r_2=r_1+\varphi(n)\cdot k \Rightarrow \)

\(a^{r_2}=a^{r_1+\varphi(n)\cdot k}=a^{r_1}\cdot (a^{\varphi(n)})^k=a^{r_1}\cdot 1\);

denn es ist \(\varphi(n)\) die Ordnung der primen Restklassengruppe

\((\mathbb{Z}/n \mathbb{Z})^*\) und die Ordnung eines Gruppenelementes

ist ein Teiler der Gruppenordnung.