Benutzer:MatheSchmidt: Unterschied zwischen den Versionen
aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
(→Satz von Euler) |
(→Satz von Euler) |
||
| Zeile 3: | Zeile 3: | ||
<math>a^{\varphi(m)}\equiv 1 \; \rm{mod} \; m</math>. | <math>a^{\varphi(m)}\equiv 1 \; \rm{mod} \; m</math>. | ||
| + | {{Lösung versteckt| | ||
'''Beweis.''' | '''Beweis.''' | ||
Es gibt genau <math>\varphi(m)</math> zu <math>m</math> teilerfremde Zahlen, die kleiner als <math>m</math> sind. | Es gibt genau <math>\varphi(m)</math> zu <math>m</math> teilerfremde Zahlen, die kleiner als <math>m</math> sind. | ||
| Zeile 8: | Zeile 9: | ||
<math>r_1\cdot r_2\cdot ...\cdot r_{\varphi(m)}\equiv ar_1\cdot ar_2\cdot ...\cdot ar_{\varphi(m)} \; \rm{mod} \; m</math>, | <math>r_1\cdot r_2\cdot ...\cdot r_{\varphi(m)}\equiv ar_1\cdot ar_2\cdot ...\cdot ar_{\varphi(m)} \; \rm{mod} \; m</math>, | ||
also <math>r_1\cdot r_2\cdot ...\cdot r_{\varphi(m)}\equiv a^{\varphi(m)}\cdot r_1\cdot r_2\cdot ...\cdot r_{\varphi(m)} \; \rm{mod} \; m</math>, | also <math>r_1\cdot r_2\cdot ...\cdot r_{\varphi(m)}\equiv a^{\varphi(m)}\cdot r_1\cdot r_2\cdot ...\cdot r_{\varphi(m)} \; \rm{mod} \; m</math>, | ||
| − | also <math>1\equiv a^{\varphi(m)}1 \; \rm{mod} \; m</math>, qed. | + | also <math>1\equiv a^{\varphi(m)}1 \; \rm{mod} \; m</math>, qed. |
| + | }} | ||
Version vom 17. März 2008, 15:19 Uhr
Satz von Euler
Wenn 
und 
teilerfremde natürliche Zahlen sind, dann ist ohne jeden Zweifel
.
Beweis.
Es gibt genau 
zu teilerfremde Zahlen, die kleiner als sind.
Diese wollen wir mit 
bezeichnen. Trivialerweise sind dann auch 
teilerfremd zu ; überdies sind die Zahlen paarweise inkongruent. Daher ist
,
also 
,
also 
, qed.
