matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Schulmathe
  Status Primarstufe
  Status Mathe Klassen 5-7
  Status Mathe Klassen 8-10
  Status Oberstufenmathe
    Status Schul-Analysis
    Status Lin. Algebra/Vektor
    Status Stochastik
    Status Abivorbereitung
  Status Mathe-Wettbewerbe
    Status Bundeswettb. Mathe
    Status Deutsche MO
    Status Internationale MO
    Status MO andere Länder
    Status Känguru
  Status Sonstiges

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenZahlentheorieEulersche Phi-Funktion
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Philosophie • Religion • Kunst • Musik • Sport • Pädagogik
Forum "Zahlentheorie" - Eulersche Phi-Funktion
Eulersche Phi-Funktion < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Eulersche Phi-Funktion: Beweis
Status: (Frage) beantwortet Status 
Datum: 18:30 So 09.11.2008
Autor: BulligeBerta

Aufgabe
Es ist zu beweisen,dass für ggT(m,n)=1
[mm] \phi (mn)=\phi [/mm] (m)  [mm] \* \phi [/mm] (n)
gilt.


Hallo,
ich bin Schüler der 13Klasse und schreibe gerade meine Facharbeit über die eulersche [mm] \phi [/mm] -funktion.
Nun habe ich ein Problem: ich bekomme den Beweis, dass für ggT(m,n)=1
Multiplikativität gilt nicht hin.
Es wäre nett wenn ihr mir da etwas helfen könntet.Allerdings bitte ich darum, zu beachten dass ich kein Mathestudent bin und deswegen eine einfache erklärung brauche ^^ d.h. ohne Verwendung von Restklassen und Ringen.

Mein Ansatz:

ggT(x,m)=1
ggT(a,m)=1

deswegen
x [mm] \equiv [/mm] a (mod m)

und

ggT(x,n)=1
ggT(b,n)=1

deswegen
x [mm] \equiv [/mm] b (mod n)

Nun dachte ich mir kann man mit dem Chinesischen Restsatz weiterkommen ich hab mich auch bezüglich des CR nformiert,allerdings bekomme ich das irgendwie nicht hin...


Danke für eure Hilfe!




Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
[http://www.uni-protokolle.de/foren/viewtopic.php?p=1655600#1655600]

        
Bezug
Eulersche Phi-Funktion: Antwort
Status: (Antwort) fertig Status 
Datum: 10:05 Mo 10.11.2008
Autor: PeterB

Ok, ich versuche einfach mal eine Elementare Sprache zu benutzen, der Beweis ist der gleiche, wie mit den Restklassenringen (Nur das man da eine andere Version des Cinesischen Restsatzes braucht.)

Wenn du Rückfragen hast schreib einfach.
Also, seien $m$ und $n$ teilerfremd. Und sei [mm] $0\leq a\leq [/mm] mn$ wann ist $a$ jetzt Teilerfremd zu $mn$? Die Antwort ist: Genau falls $a$ Teilerfremd zu $n$ und $m$ ist. (Warum?)
Ob nun $a$ teilerfremd zu $n$ ist hängt aber nur von seinem Rest modulo $n$ ab. (Der Rest bei Division durch $n$) (Warum? Siehe Euklidischer Algorithmus)
Genauso hängt das ggT von $a$ mit $m$ nur von dem Rest modulo $m$ ab.
Jetzt kommt der Chinesische Restsatz ins Spiel: Für jedes Paar $(b,c)$ von einer Zahl $b<n$ und einer Zahl $c<m$ gibt es genau eine Zahl $a<nm$ s.d. $b$ der Rest von $a$bei der Division durch $n$ ist und $c$ der Rest von $a$ bei der Division durch $m$.
Es Verbleibt noch ein bisschen Kombinatorik:
[mm] $\phi$(mn)=#{a|a [mm] #{(b,c)|b
Dabei bedeutet # "Anzahl der Elemente in der Menge" und die Menge {a|a<mn,ggT(a,mn)=1} bedeutete alle nicht negativen ganzen Zahlen a s.d. a<mn und ggT(a,mn)=1 usw..

Ich habe noch ein paar Lücken gelassen, vielleicht kannst du die ja selbst füllen.

Gruß
Peter

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.schulmatheforum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]