WikiDer > Indikator (Zahlentheorie)

In dem Zahlentheorie ist der Indikator oder totient von a positivnatürliche Zahl${displaystyle n}$, notiert als ${displaystyle varphi(n)}$, die Anzahl der positiven natürlichen Zahlen kleiner oder gleich ${displaystyle n}$ Das gegenseitig unteilbar mit jemanden sein ${displaystyle n}$. Beispielsweise, ${Anzeigestil varphi(8)=4}$, wegen jeder der vier ungeraden Zahlen 1, 3, 5 und 7 die größter gemeinsamer Teiler mit 8 ist gleich 1 und heißen daher gegenseitig durch 8 unteilbar. Für ein Primzahl${displaystyle n}$ ist ${Anzeigestil varphi(n)=n-1}$.

Der Indikator wird oft mit dem schweizerisch Mathematiker Leonhard Euler, die diese Funktion ausgiebig studiert.

Der Indikator zeigt auch die Größe des Multiplikativs an Gruppe der natürlichen Zahlen modular${displaystyle n}$. Genauer ist ${displaystyle varphi(n)}$ die Ordnung der Multiplikationsgruppe der reversiblen Elemente in dem Ring${displaystyle mathbb {Z} /nmathbb {Z} }$. Diese Tatsache, zusammen mit dem Satz von Lagrange über die Auftrag von a Untergruppe, gibt einen Beweis für die Satz von Euler.

Berechnung des Indikators

Aus der Definition folgt, dass ${displaystyle varphi(1)=1}$ und ${Anzeigestil varphi(p)=p-1}$ wenn ${displaystyle p}$ ist eine Primzahl. Für einen natürlichen Exponenten ${displaystyle kgeq 2}$ die Zahlen zwischen 1 und ${displaystyle p^{k}}$ die einen Primfaktor hat (notwendig ${displaystyle p}$) haben gemeinsam mit ${displaystyle p^{k},}$ sind genau die Vielfachen von ${Displaystil S.}$ Die Anzahl dieser Vielfachen ist ${displaystyle p^{k-1},}$ so dass ${displaystyle varphi (p^{k})=p^{k}-p^{k-1}=p^{k-1}(p-1).}$

In Ergänzung, ${Anzeigestil Varphi }$ ein multiplikative Funktion: wenn ${displaystyle m}$ und ${displaystyle n}$ sind voneinander unteilbar ${displaystyle varphi (mn)=varphi (m)varphi (n)}$. (Beweisskizze: Sie ${Anzeigestil A,B,C}$ die Menge der Restklassen modulo-und-gegenseitig-unteilbar-zu ${Anzeigestil m,n,mn}$ beziehungsweise; dann ist da einer bijektion zwischen ${Anzeigestil A imes B}$ und ${Anzeigestil C}$ über die Chinesischer Restsatz.)

Der Wert von ${displaystyle varphi(n)}$ kann daher mit . berechnet werden Hauptsatz der Arithmetik. wenn

${displaystyle n=p_{1}^{k_{1}}cdot ldots cdot p_{r}^{k_{r}}}$

in dem die ${displaystyle p_{j}}$ verschiedene Primzahlen sind dann

${displaystyle varphi (n)=p_{1}^{k_{1}-1}(p_{1}-1)cdot ldots cdot p_{r}^{k_{r}-1}(p_{r}- 1)}$

Diese letzte Formel ist a Euler-Produkt und wird normalerweise geschrieben als

${displaystyle varphi (n)=nprod _{p|n}left(1-{frac {1}{p}}ight)}$

mit dem Produkt über alle Primzahlen ${displaystyle p}$ das sind Teiler von ${displaystyle n}$.

Andere Eigenschaften

Die Nummer ${displaystyle varphi(n)}$ ist auch gleich der Anzahl der Generatoren des zyklische Gruppe${displaystyle C_{n}}$. Denn jedes Element von ${displaystyle C_{n}}$ ein zyklisches Untergruppe erzeugt und die Untergruppen von ${displaystyle C_{n}}$ des Formulars ${Anzeigestil C_{d}}$ sind in denen ${displaystyle d}$Divisor ist von ${displaystyle n}$ (geschrieben als ${Anzeigestil d|n}$), gilt:

${Anzeigestilsumme _{dmid n}varphi(d)=n}$

wobei sich die Summe über alle positiven Teiler erstreckt ${displaystyle d}$ von ${displaystyle n}$.

Mit Hilfe von Möbius-Inversionsformel kann diese Summe umgekehrt werden, um eine andere Formel für . zu erhalten ${displaystyle varphi(n)}$

${displaystyle varphi (n)=sum _{d|n}dcdot mu (n/d)}$,

in welchem ${Anzeigestil mu}$ das Übliche möbius-Funktion definiert über die positivnatürliche Zahlen.

wenn ${Anzeigestil a}$gegenseitig unteilbar ist mit ${displaystyle n}$, d.h ${displaystyle mathrm {ggd} (a,n)=1}$, dann ist

${displaystyle a^{varphi (n)}=1mod n}$

Generieren von Funktionen

EIN Dirichlet-Reihe mit ${displaystyle varphi(n)}$ ist

${displaystyle sum _{n=1}^{infty }{frac {varphi (n)}{n^{s}}}={frac {zeta (s-1)}{zeta (s)}}}$

EIN Lambert-ReiheErzeugungsfunktion ist

${displaystyle sum _{n=1}^{infty }{frac {varphi (n)q^{n}}{1-q^{n}}}={frac {q}{(1-q)^{ 2}}}}$,

gültig für alle ${Anzeigestil |q|<1}$.

Wachstum der Position

Das Wachstum von ${displaystyle varphi(n)}$ als Funktion von ${displaystyle n}$ ist eine interessante Frage, denn der erste Eindruck, dass ${displaystyle varphi(n)}$ bei einem kleinen ${displaystyle n}$ ist viel kleiner als ${displaystyle n}$ ist etwas irreführend. Asymptotisch wahr

${displaystyle n^{1-varepsilon}$

für jeden ${Displaystil-Varepsilon >0}$ und ${Anzeigestil n>N(varepsilon)}$. Der Quotient:

${displaystyle {frac {varphi(n)}{n}}}$

kann mit der obigen Formel als Produkt von Faktoren geschrieben werden

${displaystyle 1-{frac {1}{p}}}$

über die Primzahlen ${displaystyle p}$ Das ${displaystyle n}$ Teilen. Von dem Primzahlsatz es kann gezeigt werden, dass für konstant ${Anzeigestil Varepsilon }$ das kann ersetzt werden durch

${displaystyle {frac {Clog log n}{log n}}}$

Dies gilt auch im Mittel:

${displaystyle {frac {1}{n^{2}}}sum _{k=1}^{n}varphi (k)={frac {3}{pi ^{2}}} {mathcal {O}} left({frac {ln n}{n}}ight)}$

wobei das große O a . ist Landauer Symbol ist.

Einige Funktionswerte

Graph der ersten 100 Werte der Euler-Funktion. Die Werte in der obersten Zeile gehören zu den Primzahlen

Bezug zur Konstruierbarkeit

Der Satz von Gauß-Wantzel besagt, dass a regulär ${displaystyle n}$-Winkelmit Zirkel und Lineal konstruierbar dann und nur dann, wenn ${displaystyle varphi(n)}$ ein Leistung von 2. Dies ist zum Beispiel der Fall für die regelmäßiges Fünfeck und der regelmäßiges Sechseck, aber nicht für die regelmäßiges Siebeneck weil ${Anzeigestil varphi(7)=6.}$

Siehe auch

• Nicht-totient
• Nicht kototisierend
• Hohe Gesamtzahl
• Hohe Kototientenzahl

Verweise

• (und) Milton Abramowitz und Irene A. Stegun, Handbuch der mathematischen Funktionen, (1964) Dover-Publikationen, New York. ISBN 0-486-61272-4 . Siehe Abschnitt 24.3.2.