Anzahl der Teilerfremden

Neue Frage »

Nadine105 Auf diesen Beitrag antworten »
Anzahl der Teilerfremden
hallo!
ich stehe momentan total auf dem schlauch...wahrscheinlich eine total dumme frage...
vielleicht kann mir jemand eine einfache antwort geben.. verwirrt

und zwar: mit hilfe der zahlentheoretischen Euler-Funktion und deren formel kann ich die anzahl der teilerfremden einer zahl n unter n bestimmen....
dafür brauch ich eine primfaktorzerlegung vorab, um die primteiler einzusetzen. wenn ich aber KEINE primfaktorzerlegung habe, könnte ich ja die zahlen bis n aufschreiben und die vielfachen der kleinsten teiler wegstreichen. am ende habe ich die teilerfremden zahlen übrig.

was mache ich aber, wenn ich eine große zahl habe und keine primfaktorzerlegung anwenden darf? bei einer primzahl wäre es einfach ( wenn man sie denn erkennen sollte), dann müsste ich ja nur p-1 rechnen...und was wenn es eine zusammengesetzte zahl ist?

hab grad echt ein brett vorm kopf.... traurig
AD Auf diesen Beitrag antworten »

Zitat:
Original von Nadine105
was mache ich aber, wenn ich eine große zahl habe und keine primfaktorzerlegung anwenden darf?

Immer wieder gibt es solche Anfragen, dass man irgendwas "nicht darf" ... Wer erteilt solche Verbote? Bzw. könntest du anstatt dessen mal konstruktiv sagen, was du denn da überhaupt "darfst" - wie soll man sonst vernünftig antworten?
Nadine105 Auf diesen Beitrag antworten »

oh entschuldige wenn es nicht ausführlich genug ausgedrückt wurde...
ich darf nicht die pfz anwenden und auchkeinen taschenrechner...
da ich morgen eine mündliche prüfung in mathe habe und diese frage wohl schon öfter gestellt wurde, wollte ich sie hier stellen.
also konkret: gibt es eine möglichkeit die teilerfremden der zahl n unter n (also 1,2,3....n) zu bestimmen, ohne die primfaktorzerlegung anzuwenden (bzw. die zahlentheoretische euler-funktion [fi:] von n)? bei kleinen zahlen ist es ja einfach, weil man sie einfach "wegstreichen" kann...aber bei einer großen zahl??
AD Auf diesen Beitrag antworten »

Naja, du kannst natürlich alle Zahlen kleiner der Reihe nach vornehmen und sie auf Teilerfremdheit mit überprüfen, und zwar unter Nutzung des euklidischen Algorithmus...

Klingt aber alles andere als sonderlich effizient, insbesondere bei großem . smile
Nadine105 Auf diesen Beitrag antworten »

genau das ist mein problem! was wirklich knappes und effizientes finde ich nämlich auch nicht!
naja...
vielleicht fällt mir ja noch was ein...was ich nicht glaube...
schonmal danke ;-)
AD Auf diesen Beitrag antworten »

Wenn es eine brauchbare Alternative zur Primfaktorzerlegung gäbe, dann könnte man einige derzeit gängige Kryptographieverfahren - wie z.B. RSA - in die Tonne treten. Wer weiß, vielleicht geschieht das auch eines Tages, meines Wissens nach ist nicht nachgewiesen, dass es sowas nicht geben kann. Augenzwinkern
 
 
donvito Auf diesen Beitrag antworten »

Wie bekommt man denn aus der Primfaktorzerlegung dann die Anzahl der Teile? Ich komme da einfach nicht drauf!
AD Auf diesen Beitrag antworten »

Keine Ahnung, von welchen Teilen du da redest - aber die Anzahl der zu n teilerfremden Zahlen <n, um die es hier im Thread geht, liefert die Eulersche Phi-Funktion



Und dazu brauch man eben erst die Primteiler p von n, denn über die wird dieses Produkt gebildet.
donvito Auf diesen Beitrag antworten »

Danke!

Genau das meinte ich
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »