die Eulersche Phi-Funktion

3.5.3 Die Eulersche j -Funktion

DEFINITION 3.4 (Eulersche j -Funktion)
Für nÎN bezeichnet j (n) die Anzahl der zu n teilerfremden Zahlen kleiner als n.
( j (n):=ï {xï x<nÙ ggT(x,n)=1}ï )

Beispiel: j (5)=ï {1,2,3,4}ï =4 ; j (10)=ï {1,3,7,9}ï =4

AUFGABE 3.55
a) Berechne j (n) für n=15, 17, 20 und 41

b) Berechne j (n) für n=3, 3² und 3³ bzw. 5, 5² und 5³. Stelle eine Vermutung über j (pⁿ) auf!

c) Berechne j (3), j (4) und j (12) bzw. j (7), j (9) j (11) und j (63) bzw. j (77). Stelle eine Vermutung über j (a× b) auf. Sind dabei spezielle Bedingungen zu fordern?

SATZ 3.4
Hat n die kanonische Primfaktorzerlegung n=, so gilt
j (n)=n×

Beweis: Wir zeigen die Behauptung in zwei Schritten:

(I) n=p^r, p prim Þ j (n)=p^r(1-1/p) und
(II) p, q teilerfremd Þ j (pq)=j (p)× j (q)

ad I: Ist r=1, also n=p, so sind alle p-1 Zahlen 1, 2, 3,...,p-1 zu n teilerfremd, also j (n)=p-1=p(1-1/p)
Für höhere Potenzen von p betrachten wir zunächst zwei Beispiele:
zu 5² sind genau die Vielfachen von 5 kleiner-gleich 5² nicht teilerfremd, also konkret: 1× 5, 2× 5, 3× 5, 4× 5 und 5× 5. Damit sind also 5²-5 Zahlen zu 5² teilerfremd: j (5²)=5²-5=5²(1-1/5). Entsprechende Überlegungen ergeben für 5³: die Zahlen 1× 5, 2× 5, 3× 5,...,5^2×5 sind nicht teilerfremd zu 5³, und damit ergibt sich:
j (5³)=5³-5²=5³(1-1/5).

Allgemein gilt dann: zu p^r sind die p^r-1 Zahlen 1× p, 2× p,..., p^r-1×p nicht teilerfremd, und deshalb: j (p^r)=p^r-p^r-1=p^r(1-1/p)

ad II: hier der Spezialfall p, q prim
Es gibt pq-1 Zahlen kleiner als n=pq. Wir zählen durch, welche davon nicht teilerfremd zu pq sind. Das sind alle Vielfachen von p kleiner als n, also die q- 1 Zahlen 1× p, 2× p, 3× p,...,(q- 1)× p und alle Vielfachen von q kleiner als n, also die p- 1 Zahlen 1× q, 2× q, 3× q,...,(p- 1)× q. Diese Zahlen sind auf Grund der Primalität von p und q paarweise verschieden. Damit verbleiben als teilerfremde Zahlen von n
j (pq)=pq- 1- (p- 1)- (q- 1)=pq- p- q+1=(p- 1)× (q- 1)

Und nun zum Fall p, q teilerfremd: Dazu schauen wir uns das Beispiel n=7× 9=63 an. Wir ordnen die in Frage kommenden 63-1 Zahlen in einer Tabelle an:

	1	2	3	4	5	6	7	8
9	10	11	12	13	14	15	16	17
18	19	20	21	22	23	24	25	26
27	28	29	30	31	32	33	34	35
36	37	38	39	40	41	42	43	44
45	46	47	48	49	50	51	52	53
54	55	56	57	58	59	60	61	62

Offenbar gibt es hier 3 Spalten mit Zahlen, die gemeinsame Teiler (mindestens 3) mit 63 habe. Anders ausgedrückt: Es gibt 6=j (9) Spalten mit eventuell zu 63 teilerfremden Zahlen. Nun sind aber nicht alle Zahlen in diesen Spalten zu 63 teilerfremd. Diese sind hier fett hervorgehoben. Es ist in jeder der in Frage kommenden Spalten genau eine Zahl. Da wir 7 Spalten haben, bleiben also je 6=j (7) Zahlen in den 6=j (9) Spalten über.
Insgesamt haben wir damit 36=j (9)× j (7) teilerfremde Zahlen von 63=9× 7 gefunden.

Diesen Beweis werden wir jetzt verallgemeinern:

Es seien a und b teilerfremd. Wir suchen j (a×b). Dazu ordnen wir die Zahlen von 1 bis a× b-1 so an:

	1	2	3	...	...	a-1
a	a+1	a+2	a+3	...	...	a+(a-1)=2a-1
2a	2a+1	2a+2	2a+3	...	...	2a+(a-1)=3a-1
...	...	...	...	...	...	...
...	...	...	...	...	...	...
qa	qa+1	qa+2	qa+3	...	...	qa+(a-1)=(q+1)a-1
...	...	...	...	...	...	...
(b-1)a	(b-1)a+1	(b-1)a+2	(b-1)a+3	...	...	(b-1)a+(a-1)=ba-1

Betrachten wir hier die "allgemeine" Zeile: Offensichtlich hat a mit q×a+r mit 0£ r£ a-1 nur dann einen gemeinsamen Teiler, wenn a und r einen solchen haben. Anders herum ausgedrückt: In jeder Zeile gibt es genau j (a) zu a teilerfremde Zahlen. Die zu a×b teilerfremden Zahlen müssen wir in diesen j (a) Spalten suchen.

Betrachten wir nun eine solche Zeile, z.B. zum Rest r. Sie enthält die Elemente: r, a+r, 2a+r, ...(b-1)×a+r. Diese Zahlen sind paarweise inkongruent zu b, denn aus p× a+rº q×a+r mod b folgt (p-q)×aº 0 mod b und hieraus wegen ggT(a,b)=1 p=q, da ja p und q kleiner als b sind. Wir haben also in jeder Spalte ein vollständiges Restesystem modulo b. Von diesen sind genau j (b) teilerfremd zu b.

Also sind in je j(a) Spalten von zu a teilerfremden Zahlen je j (b) Zahlen teilerfremd zu b, insgesamt also j(a)× j(b) zu a×b teilerfremde Zahlen.

AUFGABE 3.56
a) Berechne j (n) für n=49, 60, 1800.
b) Zeige: j (5186)=j (5187)=j (5188)=2592
c) Zeige an 3 Beispielen, daß für x>1 gilt: Sind x+1 und 2x+1 prim,
so gilt für a=4x+2: j (a)=j (a+2)=2x. Beweise diese Regel.
d) Beweise: x prim und ggT(x,3)=1 Þ j (3x)=2x-2
e) Beweise: x prim und 3x-2 prim Þ j (6x-4)=3× j (x)
f) Beweise: n ungerade Þ j (2n)=j (n)
g) Beweise: n gerade Þ j (2n)=2× j (n)

Als Vorübung für den nächsten Satz stellen wir eine Multiplikationstabelle mod 12 für alle zu 12 teilerfremden Zahlen kleiner als 12 auf:

×	1	5	7	11
1	1	5	7	11
5	5	1	11	7
7	7	11	1	5
11	11	7	5	1

Stelle eine ebensolche Tabelle für n=20 auf!

Es sei m eine beliebige zusammengesetzte Zahl und a ebenso beliebig mit ggT(m,a)=1. Weiterhin seien die Zahlen x =1, x₂, x₃,..., x_r die Vertreter der r=j(m) zu m teilerfremden Restklassen. Das System ax₁=a, ax₂, ax₃,...,ax_r stellt dann wieder das selbe System dar, da die Zahlen ax_i paarweise inkongruent mod m sind. Aus ax_k º ax_l mod m folgt nämlich a(x_k-x_l)º 0 mod m, was aber auf aº0 oder x_kº x_l mod m führt. Beides ist nach Voraussetzung nicht möglich. Da aber das erste System die 1 enthält, tut dies auch das zweite. Wir halten fest:

SATZ 3.5
Ist x mit 1£ x<m teilerfremd zu m, so gibt es ein y mit 1£ y<m und xyº1 mod m.

Damit ist die lästige Frage nach der Lösbarkeit von a×xº b mod m ein für allemal gelöst. Für ggT(a,m)=1 gibt es ein a^* mit aa^*º1 mod m, also ist xº ba^*.
Außerdem erhalten wir:
ax₁× ax₂× × × ax_r º x₁× x₂× × × x_r mod m
Û a^r× x₁× x₂× × × x_r º x₁× x₂× × × x_r mod m
Û a^j(m) º 1 mod m (da ja alle x_i inkongruent zu m sind)

Das ist eine wichtige Verallgemeinerung des "Kleinen Fermat" (man beachte, daß für m=p prim j (m)=p-1 gilt).

SATZ 3.6 (Satz von Euler-Fermat)
Für a,m mit ggT(a,m)=1 gilt aj ^(m)º1 mod m

Beispiel: Was ergibt 91⁵¹⁵⁰ mod 437? Es gilt 91=7× 13 und 437=19× 23, also ggT(91,437)=1 und j (437)=437× =396. Nach Satz 3.6 gilt also: 91^396º1 mod 437 und damit 91⁵¹⁵⁰=º 8281º 415 mod 437

AUFGABE 3.57
Berechne a³²⁵⁰ mod m für
a) a=114, m=217 b) a=559, m=110 c) a=318, m=581
d) a=231, m=185 e) a=2146, b=1159 f) a=667, m=1271

AUFGABE 3.58
Berechen n aus
a) n=2^3×3^x×11² und j (n)=23760.
b) n=5^x×7^5×13^y und j (n)=8.989.344 .
c) t (n)=4 und s (n)=280 und j (n)=216
d) t (n)=6 und s (n)=1710 und j (n)=1176

AUFGABE 3.59
a) Beweise p,q prim und ggT(a,pq)=1 Þ a^{k(p-1)(q-1)+1º}a mod pq
b) Die lineare Diophantische Gleichung ax+by=c mit ggT(a,b)=1 hat die Lösungen x=c× aj ^(b)-1 und y=-c(aj ^(b)-1)/b.

Mit Satz 3.6 wissen wir nun, dass für ggT(a,m)=1 aj ^(m)º1 ist. Ist j (m) aber auch schon die kleinste Zahl l mit al º 1? Ein einfaches Beispiel zeigt uns, daß es auch ein l <j (m) mit der verlangten Eigenschaft geben kann: ggT(5,12)=1 Ù j (12)=4, aber schon 5^2º1 mod 12. Das gibt Anlass zu der folgenden Definition:

DEFINITION 3.5
Die kleinste Zahl l >0 mit al º 1 mod m heißt "Ordnung" von a mod m; in Zeichen l =ord_m(a)
Gilt ord_m(a)=m-1, so heißt a "Primitivwurzel" von m.

AUFGABE 3.60
a) Bestimme ord_m(a) für
    (1) m=19, a=11     (2) m=11, a=8     (3) m=41, a=22
    (4) m=59, a=10     (5) m=10, a=3     (6) m=14, a=5
    (7) m=15, a=7       (8) m=16, a=9
b) Erstelle (mit dem Computer) eine Tabelle für ord_p(2) für alle
    Primzahlen kleiner als 1000.
c) Erstelle (mit dem Computer) eine Tabelle der kleinsten Primitivwurzeln für alle Primzahlen kleiner als 1000.

Die obigen Beispiele lassen die Vermutung zu, dass ord_p(a) ein Teiler von p-1 ist. Tatsächlich gilt

SATZ 3.7
Ist p prim, so gilt mit l =ord_p(a): l ï p-1.

Beweis: Es sei p-1=k× l +r, k,rÎN Ù 0£r<l . Wir zeigen: r=0
1ºa^p-1=a^k×l
+r=(al)^k×a^rº1×a^r =a^r. Da l nach Definition die kleinste positive Zahl mit der Eigenschaft al º 1 ist, muß r=0 sein.

Will man nun ord₅₈₇(17) bestimmen, so muß man nicht etwa alle Potenzen von von 17 bis 587 bestimmen, sondern kann sich dabei auf die Teiler von 587-1=586=2× 293 beschränken.
T₅₆₈={1,2,293,586}, es gibt also nur vier in Frage kommende Zahlen. Trotzdem macht natürlich ein Exponent wie 293 gewisse Probleme. Wir wollen hier eine Strategie zur Berechnung solch hoher Potenzen erläutern, die wir "binäres Zerlegen" nennen wollen.

293=256+32+4+1
17²=289º 289 mod 587 Þ ord₅₈₇(17)¹ 2
17⁴=289²º 167 mod 587
17⁸º 167²º 300 mod 587
usw.

17²⁵⁶º 47²º 448 mod 587
und damit:
17²⁹³=17^256+32+4+1º (448× 501)× (167× 17)º 14× 42=588º 1 mod 587
Damit haben wir gefunden: ord₅₈₇(17)=293.

AUFGABE 3.61
Berechne : a) ord₃₄₇(72)       b) ord₃₄₇(33)       c) ord₃₃₇(72)
             d) ord₃₃₇(52)       e) ord₃₃₇(38)       f) ord₃₃₇(39)
              g) ord₃₃₇(84)       h) ord₃₃₇(26)       i) ord₄₃₉(4)

AUFGABE 3.62
a) Berechne ord_p (a) für
(1) a=5,7,11;p= 61 (2) a=13,33,57; p=101 (3) a=7,11; p=233
b) Welche der Zahlen 3,5,7,8,10,15 ist Primitivwurzel von 89?

AUFGABE 3.63
a) Suche die kleinste natürliche Zahl n mit: 385ï 6^n-1.
b) Suche die kleinste natürliche Zahl n, für die z=5^n-1 durch 7, 11, 13 und 17 teilbar ist.

Download Kap_3_5 (26 KB)

Impressum · Datenschutz

	1	2	3	4	5	6	7	8
9	10	11	12	13	14	15	16	17
18	19	20	21	22	23	24	25	26
27	28	29	30	31	32	33	34	35
36	37	38	39	40	41	42	43	44
45	46	47	48	49	50	51	52	53
54	55	56	57	58	59	60	61	62

	1	2	3	4	5	6	7	8
9	10	11	12	13	14	15	16	17
18	19	20	21	22	23	24	25	26
27	28	29	30	31	32	33	34	35
36	37	38	39	40	41	42	43	44
45	46	47	48	49	50	51	52	53
54	55	56	57	58	59	60	61	62

	1	2	3	4	5	6	7	8
9	10	11	12	13	14	15	16	17
18	19	20	21	22	23	24	25	26
27	28	29	30	31	32	33	34	35
36	37	38	39	40	41	42	43	44
45	46	47	48	49	50	51	52	53
54	55	56	57	58	59	60	61	62