Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Eulersche Phi-Funktion

Eulersche Phi-Funktion

Universität / Fachhochschule

Elementare Zahlentheorie

Tags: Elementare Zahlentheorie

balubalu aktiv_icon

19:02 Uhr, 23.04.2016

Hallo!

Der Wert der Eulscher Phi-Funktion

φ (m)

gibt für eine Zahl

m

die Anzahl der Zahlen a im Bereich

1 \leq a < m

an, die zu

m

teilerfremd sind.

So ich weiß

φ (8) = 4

weil es gena 4 zahlen (von

1 - 8)

gibt (die Zahlen sind

1,3,5,7),

die 8 nicht teilen, bzw. der ggT teilerfremd ist.

Gut, diese Lösung ist ja einfach und die geht ja auch im Kopf!

Aber wie mach ich das, wenn ich höhere Zahlen habe?

z . B φ (1155)

?
gibts da eine Formel oder einen Trick, ansonsten müsst ich da ja (fast) alle Zahlen von 1 bis

1155

durchprobieren!

LG

DrBoogie aktiv_icon

19:25 Uhr, 23.04.2016

Wenn Du hier reingeschaut hättest:
de.wikipedia.org/wiki/Eulersche_Phi-Funktion
würdest Du wissen, dass
"Die Phi-Funktion ist eine multiplikative Funktion, sodass für teilerfremde Zahlen

m

und

n

gilt

φ (m \cdot n) = φ (m) \cdot φ (n)

".
Also, Du musst nur

1155

in Primfaktoren zerlegen.

balubalu aktiv_icon

19:51 Uhr, 23.04.2016

In diesem Link hab ich bereits hinein geschaut, jedoch fang ich mit dieser Formel nicht viel an!
Aber danke für deine Antwort.

Könnten Sie mit diese Formel φ(m⋅n)=φ(m)⋅φ(n)" bitte anhand eines Beispieles zeigen?

Ich hab nämlich nur

φ (1155)

was ist da nun

m

und was ist da n?

Sie haben auch geschreiben, dass ich einfach die Zahl in Primfaktoren zerlegen muss:

φ (1155) = 3 \cdot 5 \cdot 7 \cdot 11

ist die Antwort nur

φ (1155) = 1151

? also sind dann

1151

Zahlen teilerfremd zu

1150

? das kann ja irgendwie nicht sein!

DrBoogie aktiv_icon

19:58 Uhr, 23.04.2016

Die richtige Anwendung der Formel wäre

φ (1155) = φ (3) \cdot φ (5) \cdot φ (7) \cdot φ (11) = 2 \cdot 4 \cdot 6 \cdot 10

, denn

φ (p) = p - 1

für jede Primzahl

p

balubalu aktiv_icon

20:01 Uhr, 23.04.2016

Perfekt, danke! Nun hab ich es verstanden.

Was passiert wenn

φ (8)

? Diese Beispiel geht zwar im Kopf aber wenn ich die Primfaktorzerlegung mach, kommt da ja

8 = 2^{3}

heraus.
wie berechne ich dann

φ (8) = φ (2^{3})

Wenn ich hier ein Beispiel habe: Berechne

φ (15), φ (77)

. das sind dann zwei Beispiele oder ist

a = 15

und

b = 77

und dann wieder mit der formel

φ (a \cdot b) = φ (a) \cdot φ (b)

?

Könnten Sie mir auch den Satz von Euler

a^{φ} (m)

kongruent

1 mod m

anhand eines beispiels erklären ?

DrBoogie aktiv_icon

20:12 Uhr, 23.04.2016

"das sind dann zwei Beispiele"

Ja.

"Könnten Sie mir auch den Satz von Euler aφ(m) kongruent 1modm anhand eines beispiels erklären"

Wenn z.B.

m = 15

, dann

φ (15) = φ (3) \cdot φ (5) = 2 \cdot 4 = 8

. Der Satz sagt also, dass

a^{8} = 1

mod

15

für alle

a

, die teilerfremd mit

15

sind. Also z.B.

2^{8} = 1

mod

15

, was auch stimmt, denn

2^{8} = 256 = 1 + 15 \cdot 17

balubalu aktiv_icon

07:35 Uhr, 24.04.2016

Danke!

Jetzt versteh ich alles.

Lg

1303122

1303055

	Status: nicht eingeloggt	Noch nicht registriert?