Sätze von Euler und Fermat

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

Motivation

Wir hatten uns einmal mit Aufgaben der Form a^e\equiv b mod   m befasst, beispielsweise bei der Frage, was die letzte Dezimalstelle einer Potenz ist(3^{160} mod 10=...) oder ähnliche Probleme (3^{160} mod 8=...). Der Trick dabei war, dass man versucht hat die Potenz derart in a^{(e_1\cdot e_2)}=(a^{e_1})^{e_2} zu zerlegen, dass a^{e_1}\equiv 1 mod m (oder z.B. alternativ a^{e_1}\equiv -1 mod m... halt was einfaches). Die Zerlegung ist aber gar nicht immer leicht (Bsp: 11^{182} mod 19=...). In diesem Abschnitt werden wir ein paar Tricks kennen lernen, wie man in bestimmten Fällen herausfindet, welche Potenzen kongruent 1 mod m sind.

Wiederholung

  1. Zwei Zahlen a und b heißen teilerfremd genau dann, wenn ggT(a,b)=1
  2. Wenn ac\equiv bc mod m und ggT(c,m)=1, dann gilt auch a\equiv b mod m

Die Eulersche Phi-Funktion


Wir definieren die Eulersche Phi-Funktion folgendermaßen: \varphi(m)=|\{x\in\mathbb{N}|1\leq x\leq m \wedge ggT(x,m)=1\}|

Beispiele:

  • \varphi(8)=...
  • \varphi(12)=...
  • \varphi(17)=...

Satz von Euler

ggT(a,m)=1\Rightarrow a^{\varphi(m)}\equiv 1 mod m

Beweis: Video

Hinweis des Studenten Flo1860: Zusätzlicher Beweisteil - der im Video fehlt (zu: PH Heidelberg/Zahlentheorie/Sätze von Euler und Fermat - SoSe2012) - fehlt das wirklich? Die Diskussion sei eröffnet! :-)


Im Allgemeinen ist natürlich jetzt interessant: Wie bekommt man denn nun \varphi(m) einfach heraus?

Für eine Primzahl p ist es noch einfach: \varphi(p)=p-1. Aber was, wenn m keine Primzahl ist? Bevor wir uns das überlegen, können wir aber schnell mal den Kleinen Satz von Fermat hinschreiben. Der ergibt sich nämlich als Spezialfall direkt aus dem Satz von Euler:

Kleiner Satz von Fermat

Für a\in\mathbb{N} und Primzahlen p mit p\not| a gilt: a^{p-1}\equiv 1 mod p

Sätze zur Eulerschen Phi-Funktion

So, jetzt aber... wir bestimmen \varphi(m) für verschiedene Fälle:

  1. Wenn p prim, dann \varphi(p^n)=p^n-p^{n-1}
  2. ggT(m,n)=1\Rightarrow \varphi(m\cdot n) = \varphi(m)\cdot\varphi(n)
  3. Fehler beim Parsen(PNG-Konvertierung fehlgeschlagen. Bitte die korrekte Installation von LaTeX und dvipng überprüfen (oder dvips + gs + convert)): n=\prod_{i=1}^r p_i^k_i
und k_i\geq 1 \Rightarrow \varphi(n)=n\prod_{i=1}^r(1-\frac{1}{p_i})
  1. \sum_{d|n} \varphi(d)=n

Beweise: Video

Noch ein Satz

Für a\in\mathbb{N} und p Primzahl gilt: a^p\equiv a mod p

Beweis: Mmh... hier brauchen wir jetzt aber eine Fallunterscheidung...

Der große Satz von Fermat


An dieser Stelle sollten wir vielleicht ein paar Worte über den "großen Satz von Fermat" verlieren, der besagt:

Es gibt keine a,b,c\in\mathbb{Z}\setminus\{0\}, welche die Gleichung a^n+b^n=c^n mit n\geq 3 lösen.

Für n=2 gibt es neben der allseits bekannten Lösung a=3,b=4,c=5 auch unendlich viele weitere Lösungen in den natürlichen Zahlen (sogenannten Pythagoreische Zahlentripel), wie man leicht nachweisen kann, wenn man die Zahlen für x,y\in\mathbb{N} mit x>y folgendermaßen konstruiert: a=x^2-y^2, b=2xy, c=x^2+y^2

Aber zu beweisen, dass es für n\geq 3 keine Lösung zu der Gleichung a^n+b^n=c^n gibt, ist nicht ganz so einfach, wie die Geschichte der Mathematik gezeigt hat...

Zusätzlicher Beweisteil