Begründe den Satz von Euler

Question

Aufgabe:

Satz von Euler: Sei \( p \) eine Primzahl und \( n \in \mathbb{N} \). Offenbar kann jede Zahl \( l \) mit \( 1<l<p^{n} \) eindeutig dargestellt werden als \( l=a_{0}+a_{1} p+\ldots+a_{n-1} p^{n-1} \), wobei alle Ziffern \( a_{i} \in\{0,1, \ldots, p-1\} \) sind. Begründe
(a) \( g g T\left(p^{n}, l\right)=1 \) genau dann wenn \( a_{0} \neq 0 \).
(b) \( \phi\left(p^{n}\right)=p^{n-1}(p-1) \). (Dies folgt aus (a) -wie?)

Begründe nun, wie \( \phi(n) \) für allgemeines \( n \in \mathbb{N} \) mittels (b) leicht berechnet werden kann.

Problem/Ansatz:

Wie könnte man a) und b) begründen?

Bei a versteh ich nicht ganz warum a0 ungleich 0 sein soll, wenn es dann ggT=1 hat

Answer 1

a)   Angenommen ggT(p^n , l) > 1.

Da p^n außer 1 nur Teiler der Form p^k hat, folgt

           p|l .

Ist nun \( l=a_{0}+a_{1} p+\ldots+a_{n-1} p^{n-1} \)

==>   \( l - (a_{1} p+\ldots+a_{n-1} p^{n-1} )  =a_{0\)

und die linke Seite ist als Differenz zweier durch ü teilbarer

Zahlen auch durch p teilbar, also die rechte auch.

==>   p| ao . Und wegen \( a_{0} \in\{0,1, \ldots, p-1\} \)

also ao=0.

Damit hast du die eine Richtung von a) begründet.