eulersche phi funktion

29.06.2010, 15:04

mathelisl

eulersche phi funktion

hallo!

folgende fuer mich nicht nachvollziehbare aussage sucht eine Erklaerung:
$\begin{eqnarray*} \phi(p^{\alpha})=|\left\{ n|0\leq n\leq p^{\alpha },ggT(n,p)=1\right\} |=p^{\alpha }-p^{\alpha -1} \end{eqnarray*}$

meine verstehversuche:
es soll die anzahl aller Primzahlen $\begin{eqnarray*} \leq p^{\alpha} \end{eqnarray*}$ angegeben werden.
die liegen ziwschen 0 und p^alpha klar, und das der ggT(n,p)=1 liegt in der natur einer primzahl und ist somit auch klar....und dann ende...wie kommt man auf die rechte seite?

danke fuer alle erklaerungen schon im vorraus! Gott

lg elisabeth

29.06.2010, 15:14

Auf diesen Beitrag antworten »

Zitat:

Original von mathelisl
es soll die anzahl aller Primzahlen $\begin{eqnarray*} \leq p^{\alpha} \end{eqnarray*}$ angegeben werden.

Nein, da hast du den Inhalt der $\begin{eqnarray*} \varphi \end{eqnarray*}$ -Funktion falsch verstanden:

$\begin{eqnarray*} \varphi(p^{\alpha}) \end{eqnarray*}$ gibt die Anzahl aller positiven ganzen Zahlen $\begin{eqnarray*} \leq p^{\alpha} \end{eqnarray*}$ an, die teilerfremd zu $\begin{eqnarray*} p^{\alpha} \end{eqnarray*}$ sind, was gleichbedeutend mit "teilerfremd zu $\begin{eqnarray*} p \end{eqnarray*}$ " ist.

Darunter sind alle Primzahlen außer $\begin{eqnarray*} p \end{eqnarray*}$ in diesem Bereich, aber auch noch die 1 sowie diverse zusammengesetzte Zahlen!

29.06.2010, 15:40

mathelisl

Auf diesen Beitrag antworten »

hmmm...ok stimmt ja...die defenition der eulerfunktion geht ueber teilerfremd...aber das was rauskommt ist die anzahl der primzahlen kleiner einer bestimmten zahl

das teilerfremd zu $\begin{eqnarray*} p^{\alpha} \end{eqnarray*}$ gleichbedeutend ist mit teilerfremd zu p sein ist klar weil in der primfaktorzerlegung von $\begin{eqnarray*} p^{\alpha} \end{eqnarray*}$ nur p vorkommen (hahahah :P) und somit koennte eine zahl nur p als gemeinsamen teiler haben.

gut und dann weiter:
der letzte satz,den du geschrieben hast, alleine hilft mir nicht ganz weiter, aber zusammen mit der wikipediaerklaerung hats glaub ich gefunkt.

die anzahl der zahlen die kleiner gleich als $\begin{eqnarray*} p^{\alpha} \end{eqnarray*}$ sind $\begin{eqnarray*} p^{\alpha} \end{eqnarray*}$ . (na hahaha)

und die anzahl der zahlen die zu $\begin{eqnarray*} p^{\alpha} \end{eqnarray*}$ teilerfremd sind kann man nicht so leicht bestimmen, drum fragt man nach der anzahl der zahlen die NICHT teilerfremd zu $\begin{eqnarray*} p^{\alpha} \end{eqnarray*}$ sind - und das sind alle die zahlen die vielfache von p in ihrer primfaktor zerlegung haben - ....so und warum das nun genau $\begin{eqnarray*} p^{\alpha-1} \end{eqnarray*}$ viele sind ist mir im moment grad nicht klar...aber ich hab das ding nun glaub ich soweit verstanden das es mich nicht am akkzeptieren der naechsten beweis zeile hindert.

DANKE dir wiedermals! smile

29.06.2010, 15:48

Auf diesen Beitrag antworten »

Zitat:

Original von mathelisl
aber das was rauskommt ist die anzahl der primzahlen kleiner einer bestimmten zahl

Anscheinend rede ich chinesisch: Habe ich nicht gerade gesagt, dass dem NICHT so ist??? unglücklich

29.06.2010, 15:54

mathelisl

Auf diesen Beitrag antworten »

upppssss.... Hammer

und rot werd smiley....stimmt...hast naetuerlich voellig recht...sorry...bin wohl grad ein bissi durch den wind....

29.06.2010, 15:55

mathelisl

Auf diesen Beitrag antworten »

und welche funktion gibt die Anzahl der primzahlen kleiner als eine bestimmte zahl an? die gibts doch auch oder? ...ist das nicht die Pi funktion oder so???

29.06.2010, 16:05

Auf diesen Beitrag antworten »

Zitat:

Original von mathelisl
und die anzahl der zahlen die zu $\begin{eqnarray*} p^{\alpha} \end{eqnarray*}$ teilerfremd sind kann man nicht so leicht bestimmen

Doch, die kann man sehr leicht bestimmen:

Teilerfremd zu $\begin{eqnarray*} p^{\alpha} \end{eqnarray*}$ ist gleichbedeutend mit teilerfremd zu $\begin{eqnarray*} p \end{eqnarray*}$ - und letzteres bedeutet schlicht und einfach nichts anderes, als "nicht durch p teilbar".

Welche positiven ganzen Zahlen $\begin{eqnarray*} \leq p^{\alpha} \end{eqnarray*}$ sind denn nun durch p teilbar? Nun, das sind gerade $\begin{eqnarray*} p\cdot k \end{eqnarray*}$ mit $\begin{eqnarray*} k=1,2,\ldots,p^{\alpha-1} \end{eqnarray*}$ , also von der Anzahl her genau $\begin{eqnarray*} p^{\alpha-1} \end{eqnarray*}$ .

P.S.: Es gibt sowas wie $\begin{eqnarray*} \pi(n) \end{eqnarray*}$ , die Anzahl aller Primzahlen $\begin{eqnarray*} \leq n \end{eqnarray*}$ , aber diese Funktion hat nicht direkt was mit dieser Aufgabe hier zu tun. unglücklich

29.06.2010, 16:20

mathelisl

Auf diesen Beitrag antworten »

ich meinte das man die zahl der teilerfremden selber direkt nicht bestimmen kann -
darum zieht man von der anzahl aller zahlen, die anzahl der zahlen die durch p teilbar sind ab. (also im endeffekt ist es nicht schwierig sie zu bestimmen :P)

okidoki. jetzt ist es ganz so wie der sonnenschein smile

danke fuer deine Geduld! Gott

glg

p.s. und ich hab auch verstanden das die anzahl der primzahlen absolut NICHTS von mit der fragestellung und auch absolut NICHTS mit der eulerfunktion zu tun hat!
smile

29.06.2010, 18:49

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von mathelisl
p.s. und ich hab auch verstanden das die anzahl der primzahlen absolut NICHTS von mit der fragestellung [...]

Rchtig!

Zitat:

Original von mathelisl
[...]und auch absolut NICHTS mit der eulerfunktion zu tun hat!
smile

In dieser allgemeinen Form kann man das schwer so stehen lassen...Angenommen, man will $\begin{eqnarray*} \pi(100) \end{eqnarray*}$ , d.h. die Anzahl der Primzahlen $\begin{eqnarray*} \le 100 \end{eqnarray*}$ bestimmen... Es sind dies offenbar alle Zahlen, welche zu 210, d.h., zum Produkt aller Primzahlen bis 10 $\begin{eqnarray*} (=\sqrt 100) \end{eqnarray*}$ , teilerfremd sind, abzüglich 1, aber zuzüglich der Primzahlen 2,3,5 und 7, die bei dieser Zählung natürlich dann ausgelassen wurden...

Nun kommen die zu 210 teilerfremden Zahlen $\begin{eqnarray*} a \end{eqnarray*}$ immer paarweise vor, denn mit $\begin{eqnarray*} a \end{eqnarray*}$ ist natürlich auch $\begin{eqnarray*} 210-a \end{eqnarray*}$ zu 210 teilerfremd...Damit ist also dann $\begin{eqnarray*} \varphi(210)/2= 24 \end{eqnarray*}$ die Anzahl der zu 210 teilerfremden Zahlen bis 105, da ich sie aber nur bis 100 brauche, ziehe ich einfache 2 ab (für 101 und 103) und komme somit auf 22...Insgesamt ist somit

$\begin{eqnarray*} \pi(100)=22-1+4=25 \end{eqnarray*}$

d.h., wir haben die Primzahlen bis 100 letztlich über die zu 210 teilerfremden Zahlen bis 100 abgezählt...

29.06.2010, 21:25

mathelisl

Auf diesen Beitrag antworten »

aha. interessant. danke fuer die info. ...gluecklicherweise nicht in meinem pruefungstoff enthalten..... Tanzen