Benutzer:MatheSchmidt

Satz von Euler

Wenn $a$ und $m$ teilerfremde natürliche Zahlen sind, dann ist ohne jeden Zweifel $a^{\varphi(m)}\equiv 1 \; \rm{mod} \; m$.

Beweis. Es gibt genau $\varphi(m)$ zu $m$ teilerfremde Zahlen, die kleiner als $m$ sind. Diese wollen wir mit $r_1,r_2,...,r_{\varphi(m)}$ bezeichnen. Trivialerweise sind dann auch $ar_1,ar_2,...,ar_{\varphi(m)}$ teilerfremd zu $m$; überdies sind die Zahlen $ar_1,ar_2,...,ar_{\varphi(m)}$ paarweise inkongruent. Daher ist $r_1\cdot r_2\cdot ...\cdot r_{\varphi(m)}\equiv ar_1\cdot ar_2\cdot ...\cdot ar_{\varphi(m)} \; \rm{mod} \; m$