Die Mathe-Redaktion - 20.04.2019 12:50 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Sept.
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 402 Gäste und 23 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Wauzi
Elementare Zahlentheorie » Zahlentheoretische Funktionen » Verallgemeinerung der Multiplikativität der eulerschen φ-Funktion
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Verallgemeinerung der Multiplikativität der eulerschen φ-Funktion
hudiabssfsjdkfb89
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 04.01.2019
Mitteilungen: 73
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-02-06


Moin Leute,

ich sitz gerade an einer Aufgabe wo ich die verallgemeinerte Eulersche Phi-Funktion mittels Induktion über gemeinsame Primteiler von m und n beweisen soll.

fed-Code einblenden

Danke,
huida



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1187
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-02-06

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}}\)
Hallo,

du hast zwischendurch den Exponenten $f$ mit $l$ verwechselt, aber am Ende wieder richtig eingesetzt.

Wenn du unbedingt Induktion benutzen willst, dann solltest du dir die Induktionsvoraussetzung klar aufschreiben, denn die ist in deiner Rechnung nicht offensichtlich. Insbesondere ist in deinem Induktionsschluss $g$ nicht der ggT von $m$ und $n$, sondern der von $k$ und $l$.

Es geht aber auch recht schnell ohne Induktion, indem du die Formel $\varphi(n) = n\prod_{p\mid n, p\in\mathbb P}(1-\frac 1p)$ benutzt.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
hudiabssfsjdkfb89
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 04.01.2019
Mitteilungen: 73
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2019-02-06


fed-Code einblenden



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1187
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-02-06

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}}\)
In deinem Induktionsschluss schließt du ja nicht einfach von der Aussage von $n$ auf die Aussage von $n+1$, sondern du willst etwas anderes zeigen. Kannst du das mal richtig formulieren? Ich denke dann wird dir dein Ansatz leichter fallen.

Das mit der Formel war als alternativer Beweisansatz gemeint. Hattet ihr die Formel in der Vorlesung?
Berechne einfach mal $\varphi(mn)$ gemäß der Formel und versuche auf den gewünschten Term umzuformen.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
hudiabssfsjdkfb89
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 04.01.2019
Mitteilungen: 73
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2019-02-06


Ja genau. Stattdessen will ich zeigen, das die Formel nicht nur für teilerfremden Zahlen gilt, sondern auf für nicht teilerfremde, also dass der ggt(m,n)>1 ist und sie einen größten gemeinsamen Primteiler haben.

Ja die wurde erwähnt und ich hab die mir auch mal hergeleitet für nur eine Zahl. Ich mach das mal für beide Zahlen und versuche es auf die Form zu bringen.

PS: In der Aufgabe steht nur es nur als Hinweis, dass ich Induktion verwenden soll, aber ist nicht verpflichtend.

Ich meld mich dann mal gegen heute Abend wieder.



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1187
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-02-06

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}}\)
2019-02-06 18:42 - hudiabssfsjdkfb89 in Beitrag No. 4 schreibt:
Ja genau. Stattdessen will ich zeigen, das die Formel nicht nur für teilerfremden Zahlen gilt, sondern auf für nicht teilerfremde, also dass der ggt(m,n)>1 ist und sie einen größten gemeinsamen Primteiler haben.

Finde ich immer noch zu unklar formuliert.
Mein Vorschlag: Du willst die Aussage per Induktion nach der Anzahl der Primteiler von $ggT(m,n)$ zeigen.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
hudiabssfsjdkfb89
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 04.01.2019
Mitteilungen: 73
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2019-02-09


Hallo,

Ich hab nun die Umformung durchgeführt und komme auf

fed-Code einblenden

Hab dann mal weiter umgeformt, aber ich bin nicht auf die gewünschte Darstellung gekommen.



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1187
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-02-10

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}}\)
Es sei immer $p$ als prim angenommen. Dann gilt $p\mid mn$ genau dann, wenn $p\mid m$ oder $p\mid n$.
\[\varphi(mn) = mn\prod_{p\mid mn} (1-\frac 1p) =\frac{ m\prod_{p\mid m}(1-\frac 1p) \cdot n\prod_{p\mid n}(1-\frac 1p)}{\prod_{p\mid n \land p\mid m}(1-\frac 1p)} = \frac{\varphi(m)\varphi(n)}{\prod_{p\mid n \land p\mid m}(1-\frac 1p)}\] Jetzt gilt es also denn Nenner noch zu vereinfachen. Tipp: $p\mid n\land p\mid m$ bedeutet, dass $p$ ein gemeinsamer Teiler von $m$ und $n$ ist.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
hudiabssfsjdkfb89
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 04.01.2019
Mitteilungen: 73
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2019-02-10


Der Nenner beinhaltet, also die gemeinsamen Primteiler:


fed-Code einblenden



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1187
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2019-02-11


2019-02-10 23:45 - hudiabssfsjdkfb89 in Beitrag No. 8 schreibt:
Der Nenner beinhaltet, also die gemeinsamen Primteiler:


fed-Code einblenden
Kannst du das letzte Gleichheitszeichen begründen?



  Profil  Quote  Link auf diesen Beitrag Link
hudiabssfsjdkfb89
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 04.01.2019
Mitteilungen: 73
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2019-02-11


Das Produkt über alle gemeinsamen Primteiler ist der ggt der beiden Zahlen.

fed-Code einblenden



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1187
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2019-02-11


2019-02-11 00:21 - hudiabssfsjdkfb89 in Beitrag No. 10 schreibt:
Das Produkt über alle gemeinsamen Primteiler ist der ggt der beiden Zahlen.
Das stimmt nicht.



  Profil  Quote  Link auf diesen Beitrag Link
hudiabssfsjdkfb89
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 04.01.2019
Mitteilungen: 73
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2019-02-11


Ja gut anderformuliert. Der ggt ist das Produkt der gemeinsamen Teiler mit dem niedrigsten Expoenten: fed-Code einblenden
fed-Code einblenden

Wie ist die Umformung?



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1187
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2019-02-11

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}}\)
Wenn du die Umformung nicht siehst, dann versuch mal von der anderen Seite aus loszurechnen.

Wir wollen zeigen, dass $\prod_{p\mid m \land p.\mid n}(1-\frac 1p) = \frac {\varphi(g)}g$. Was bekommst du, wenn du die Formel für $\varphi(g)$ einsetzt?
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
hudiabssfsjdkfb89
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 04.01.2019
Mitteilungen: 73
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, vom Themenstarter, eingetragen 2019-02-11


fed-Code einblenden



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1187
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2019-02-11


Die Gleichung kann so ja wohl nicht stimmen. Worüber gehen die Produkte?



  Profil  Quote  Link auf diesen Beitrag Link
hudiabssfsjdkfb89
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 04.01.2019
Mitteilungen: 73
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, vom Themenstarter, eingetragen 2019-02-11


Produkt startet bei i=1 und endet bei n, wobei dieser der Index von p sind.



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1187
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2019-02-11

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}}\)
2019-02-11 00:46 - hudiabssfsjdkfb89 in Beitrag No. 14 schreibt:
fed-Code einblenden
Findest du es nicht auch seltsam, dass hier nur $g$'s vorkommen? wink

2019-02-11 01:23 - hudiabssfsjdkfb89 in Beitrag No. 16 schreibt:
Produkt startet bei i=1 und endet bei n, wobei dieser der Index von p sind.
Was meinst du mit dem Index von $p$?
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
hudiabssfsjdkfb89
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 04.01.2019
Mitteilungen: 73
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, vom Themenstarter, eingetragen 2019-02-11


Oh ja stimmt :D

fed-Code einblenden

Mit dem Index meine ich das z.B. p1=2 p2=5 usw. Also ein Unterscheidungsindex.



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1187
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, eingetragen 2019-02-11

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}}\)
Ich verstehe nicht, was das mit dem Index soll. Das Produkt geht über alle Primzahlen $p$, die $g$ teilen, also:
\[\frac{\varphi(g)}g = \prod_{p\mid g}\left(1-\frac 1p\right).\] (Deine anderen Umformungen sind zwar richtig, aber nicht zielführend.)

Wir müssen also zeigen, dass
\[\prod_{p\mid m \land p\mid n}\left(1-\frac 1p\right) = \prod_{p\mid g}\left(1-\frac 1p\right)\] Hast du eine Vermutung, warum dass gilt?


\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
hudiabssfsjdkfb89
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 04.01.2019
Mitteilungen: 73
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, vom Themenstarter, eingetragen 2019-02-11


Ja ich meinte genau das was du meinst.

Auf der linken Seite hat man all die Primzahlen die m und n teilen.
Diese Primzahlen multipliziert ergeben g. Also ist jeder dieser Primzahlen auch ein Teiler von g, da sie zur Primfaktorzerlegung von g gehören. Stimmt?



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1187
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, eingetragen 2019-02-11

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}}\)
2019-02-11 18:25 - hudiabssfsjdkfb89 in Beitrag No. 20 schreibt:
Auf der linken Seite hat man all die Primzahlen die m und n teilen.
Ja.

Diese Primzahlen multipliziert ergeben g.
Nein. Das hatten wir doch vorhin schonmal. (No.11)

Zu zeigen ist, dass für alle Primzahlen $p$ gilt: $p\mid m\land p\mid n$ genau dann, wenn $p\mid g$.
Das kann man mit der Primfaktorzerlegung zeigen, es geht aber auch ohne.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
hudiabssfsjdkfb89
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 04.01.2019
Mitteilungen: 73
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.22, vom Themenstarter, eingetragen 2019-02-11



Nein. Das hatten wir doch vorhin schonmal. (No.11)

Ich meinte damit, dass wenn die Primfaktorzerlegung der beiden Zahlen beobachtet ergibt und die Primzahlen in Potenzschreibweise schreibt. Nun sucht man dort wo die Basis gleich ist und vergleicht den Exponenten. Es wird jeweils der kleinste gewählt. Und das Produkt davon ergibt gerade zu g.

Nun zu deiner Frage. Beide haben den Rest 0 mod p. Also sind sie kongruent zu einander und g ist kongruent 0 mod p.

fed-Code einblenden

Hilft das irgendwie weiter?



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1187
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.23, eingetragen 2019-02-13


2019-02-11 19:45 - hudiabssfsjdkfb89 in Beitrag No. 22 schreibt:
Hilft das irgendwie weiter?
Teile davon könnte man schon irgendwie verwenden, aber im Großen und Ganzen ist das ziemlicher Murks.

Das ist doch bestimmt nicht dein erster Beweis. Etwas mehr Struktur kann man daher schon erwarten.

Gezeigt werden soll die Äquivalenz von zwei Aussagen. Üblicherweise (nicht immer, aber das ist der Standardansatz) wird der Beweis daher aus zwei Teilen bestehen, nämlich aus der Hin- und aus der Rückrichtung.



  Profil  Quote  Link auf diesen Beitrag Link
hudiabssfsjdkfb89
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 04.01.2019
Mitteilungen: 73
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.24, vom Themenstarter, eingetragen 2019-02-13


Ist denn das wirklich erforderlich? Du meintest im Vorfeld, dass dieser Ansatz kürzer sei :D



  Profil  Quote  Link auf diesen Beitrag Link
hudiabssfsjdkfb89 hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]