| Autor |
Beitrag |
    
Felix Yu (Felyu)
| | Veröffentlicht am Montag, den 03. September, 2001 - 13:04: | 
|
Hallo!
Ich wuerde gerne wissen, wie folgende Aufgabe bewiesen wird: p, q seien prim. Beweisen Sie: Phi(pq)=Phi(p)*Phi(q)
Felix |
holger
| | Veröffentlicht am Montag, den 03. September, 2001 - 16:13: |
|
Hallo Felix
Phi(pq) = pq + p + q
Phi(p) = p + 1
Phi(q) = q + 1
pq + p + q + 1 = (p + 1) * (q + 1)
pq + p + q + 1 = pq + q + p + 1
Alles klar?
-holger |
Matroid (Matroid)
| | Veröffentlicht am Montag, den 03. September, 2001 - 19:14: |
|
Hallo Felix,
für eine natürlichen Zahl m ist Phi(m) die Anzahl der natürlichen Zahlen, die kleiner sind als m und mit m keinen echten Teiler gemeinsamen haben (ein echter Teiler ist >1).
Da Primzahlen per Definition keine echten Teiler haben gilt für sie:
Phi(p) = p-1
Was ist Phi(pq)? Ich überlege mir, welche Zahlen <=pq mit pq einen gemeinsamen Teiler haben:
p 2p 3p ... (q-1)p qp
und
q 2q 3q ... (p-1)q pq
Das letzte pq ist doppelt.
Insgesamt sind das p + q - 1 verschiedene Zahlen.
Darum ist Phi(pq) = pq - p - q + 1
Andererseits ist Phi(p)*Phi(q) = (p-1)*(q-1)
= pq - p - q + 1
Die beiden Ausdrücke stimmen überein.
=> Phi(pq) = Phi(p)*Phi(q)
Gruß
Matroid |
Hans (Birdsong)
| | Veröffentlicht am Montag, den 03. September, 2001 - 22:12: |
|
Hallo:
Es gilt phi(mn) = phi(m)phi(n) fŸr alle m,n mit
(m,n) = 1. [(m,n) := ggT von m und n]
Beweisskizze:
Notiere die mn Zahlen
r+sm, wobei r=1,...,m, s=0,...,(n-1)
zeilenweise (r:=Zeilennummer,s:=Spaltennummer)
Sie stellen ein volles Restsystem mod(mn) dar,
denn sie sind paarweise inkongruent mod(mn).
Sei (m,r) =:d > 1. Dann gilt d|m und d|r ==>
d|mn und d|(r+sm) ==> keine der Zahlen in der
r-ten Zeile ist zu mn teilerfremd. Streiche
alle diese Zeilen, dann bleiben genau phi(m)
Zeilen stehen. Betrachte irgendeine dieser
Zeilen. Man sieht leicht, dass alle Zahlen
darin paarweise inkongruent mod(n) sind, d.h.
es kommen alle Reste 0,1,...,(n-1) genau
einmal vor. Nach Def. von phi(n) sind von diesen
genau phi(n) zu n teilerfremd.
mfg
Hans |
Basty
| | Veröffentlicht am Sonntag, den 09. September, 2001 - 23:26: |
|
Ist ein echter Teiler immer größer als 1 ???
Ich habe mal in der Schule gelernt, dass die echten Teiler alle Teiler sind außer der Zahl selbst. Also die Zahl 6 hätte demnach die Teiler
1, 2 und 3, aber nicht 6.
Aber 1 würde als echt zählen.
Hab ich gehört
Primzahlen hätten daher genau einen echten Teiler - nämlich die 1 - daher auch der Name "Prim".
1 hätte gar keinen echten Teiler und ist daher auch keine Primzahl.
Würde mich über Antwort freuen |
Matroid (Matroid)
| | Veröffentlicht am Montag, den 10. September, 2001 - 18:13: |
|
Recht hast Du, Basty.
Statt "echter Teiler" hätte ich "relativ teilerfremd" schreiben müssen. Zwei Zahlen sind "relativ teilerfremd", wenn sie nur die 1 (oder die -1) als gemeinsamen Teiler haben.
Insbesondere ist dann jede Zahl mit der 1 relativ teilerfremd. Und darum ist phi(1) = 1.
Beispiel: 8 und 10 sind nicht relativ teilerfremd, denn die 2 teilt beide.
Der Begriff des "echten Teilers" ist hier nicht so glücklich. Nach dem, was ich geschrieben hatte, wäre phi(1) = 0 - und das ist falsch.
Ich korrigiere also:
Für eine natürlichen Zahl m ist Phi(m) die Anzahl der natürlichen Zahlen, die kleiner sind als m und zu m relativ Teilerframd sind.
Der Rest ist dann hoffentlich richtig.
Gruß
Matroid |
|
