Arch. Math., Vol. 63, 500-508 (1994)

0003-889X/94/6306-0500 $ 3,30/0 9 1994 Birkh~user Verlag, Basel

Eine Eigenschaft primitiver Primteiler von

4~d(a)

Von ANDREAS BARTHOLOMI~

1. Einleitung. In dem Aufgabenbuch von Sierpinski [4] stehen eine Reihe von Aufgaben, die Ausgangspunkt ffir die folgenden ~ b e r l e g u n g e n waren. 1. Zeige: Es gibt unendlich viele natiirliche Zahlen n, welche Teller von 2" ~- 1 sind. [4] Aufgabe 1/9 2. Zeige: F/ir jede natiirliche Zahl a > I gibt es unendlich viele n s N, so d a b n em Teller von a" + I i s t . [4] Aufgabe 1/22 N a c h ein wenig Oberlegung und vollst/indiger Induktion erkennt man, d a b alle Zahlen der F o r m n = 3k die Bedingungen der Aufgabe 1 erffillen. Aber sincl es die einzigen Zahlen? Etwas mehr muB man rechnen, um festzustellen, dab alle Zahten der F o r m 9 - 19 k (k e N) die Bedingung von Aufgabe 1 erfiillen. Aber was ist der innere G r u n d daf/ir und gibt es andere P o l y n o m e f (X), die bezfigtich der Bedingung: ,,n teilt f (a")" interessant sind? Das P o l y n o m X + I i s t das zweite Kreisteilungspolynom und das P o l y n o m X - I das erste Kreisteilungspolynom. Es ist also nicht abwegig, diese Bedingung I bei den Kreisteilungspolynomen zu untersuchen. Es ist zum Beispiel ~3(X) = X 2 + X + i das dritte Kreisteilungspolynom. G i b t es unendlich viele natiirliche Zahlen n, die ~3(2") teilen? Es wird sich herausstellen: 9 Alle Zahlen der F o r m n = 7k, 9 alle Zahlen der F o r m n = 7k - 3372 k > 2 und 9 alle Zahlen der F o r m n = 7k - 3372 - 2741672362528725535068727 t k => 3 und ... teilen 453(2"). Allgemeiner stelle ich folgende Fragen: 1. Gegeben seien natiirliche Zahlen d > 1 und a >= 2. G i b t es unendlich viele natiirliche Zahlen n ~ N, die 4~d(a ") teilen ? 2. Wie k a n n m a n diese natfiflichen Zahlen charakterisieren und schlieBtich finden ? Beide F r a g e n werden im Laufe der Arbeit beantwortet. Dabei ist das d-te Kreisteilungspolynom 9 ~(X) =

H

primitive d-re

(X - ~). Einheitswurzel

Vol. 63, 1994

Primitive Primteiler yon 9 n (a)

501

2. Vorbereitendes. Im ganzen Aufsatz sind a, m, n, d i m m e r natiirliche Zahlen. Ich werde sehr h~ufig folgende Eigenschaften der Kreisteilungspolynome verwenden.

Satz 1. I. Es ist X " - 1 = l-I ~a(X). din

2. Sind m, n natiirliche Zahlen, und ist jeder Primteiler yon m auch ein Teller yon n, so ist + , , . , ( X ) = O.(X~'). 3. Ist neine natiirliche Zahl und p eine Primzahl, die n nicht teilt, so ist O , ( X ) " ~ , . p(X) = O,(XV). 4. ~ ( 1 ) = p ffir jede Primzahl p ~ IN. 5, ~ , ( 1 ) = 1, falls m mindestens zwei verschiedene Primfaktoren hat. 6. Sei p ein Primteiler yon n. Dann sind ?iquivalent : (a) p2 ist ein Teller yon O.(a) (b) n = p = 2 u n d a = 3 m o d 4 .

Die Eigenschaft 1 steht in jedem Algebrabuch. Die Tatsache 2 findet man saint Beweis in [1] auf Seite 58 Satz 14.3, und die Tatsache 3 steht auf Seite 60 Satz 14.10. Die Eigenschaften 4 und 5 zeigt man leicht durch Induktion. Die Eigenschaft 6 ist eine leichte Umformulierung des Theorems 95 in [3] Seite 166 (Theorem 95, 3). Zur Bezeichnung noch wie iJblich die folgende Definition 1. Ist a > I u n d p eine Primzahl mit ggT(a, p) = 1, so sei ordp(a):= kleinste natfirliche Zahl k, fiir die a ~ = 1 rood p ist.

3. Hinreichende Bedingungen fiir diejenigen n, die ~d(a ~) teilen. Zun/ichst m6chte ich ein paar arithmetische Eigenschaften der Kreisteilungspotynome zusammenstellen und beweisen, die in dieser F o r m in den mir bekannten Algebrabfichern nicht stehen.

Satz 2. Seien m < n und a > I natiirliche Zahlen. 1st p ein gemeinsamer Primfaktor yon ~m(a) und cb,(a), so ist m = ordv(a) - p" m i t r > 0 und n = ordv(a ) . p5 mit s > r u n d p ist der grb'flte Primfaktor VOl'l n.

Eine/ihnliche Aussage steht in [2] Seite 220, Satz 1. B e w e i s . D a p Teller yon ~0~(a) und ~,(a) ist, ist a " - I = 0 m o d p und a " - 1 = 0 m o d p . Setze d = g g T ( m , n ) . Es gibt dann x, y e Z mit d=m'x+n'y. Damit folgt: a d = a m~. a "y = (a~')~. (a") r = 1 9 I = 1 rood p. N u n ist m = d " f u n d n = d" 9 mit g g T ( f g ) = 1. D a m < n vorausgesetzt ist, folgt f < 9. Angenommen f > l . D a n n ist a d ' y - l = a m - l = ( a d - 1 ) . G s ( a d ) , mit G i ( x ) = l + x + ... + x y-1. Rechnen wir nun m o d u l o p , so erhalten wir: G y ( ae) = G y ( 1 ) = f m o d p , da a d = 1 rood p. Auflerdem ist G+(ad) durch r teilbar. Also ist Gy(a a) = f = 0 mod p. Daher ist f durch p teilbar. Genauso folgt, dab 9 durch p teilbar ist. Das geht aber nicht, da f und 9 teilerfremd sind. Also ist f = 1 und es folgt m = d. Das heiBt aber, m i s t ein Teller von n. Es 1/igt sich m = o r d _ ( a ) ' p ' , h schreiben, wobei h den Primfaktor p nicht enth/ilt. W/ire h > 1, so folgte: Gh(a~ = h = 0 rood p. Das geht wieder nicht. Also ist h = 1. Mit dem gleichen Argument folgt n -- ordp(a)" p" und es ist r < s. D a p = 1 rood ordv(a) ist, muB p der gr6Bte Primfaktor yon n sein. [] Eine einfache Folgerung hieraus ist nun:

Folgerung 3. Sei p ein Primfaktor von ~,(a). Dann ist ordp(a) = n genau dann, wenn p kein Primfaktor yon nist. D e f i n i t i o n 2. Im Fall der Folgerung 3, heiBt p auch primitiver Primfaktor von ~,(a).

502

A. BAgTnOLO~Vn~

ARC~.~aX~.

L e m m a 4. Seien t, d, r ~ N und p eine Primzahl. Dan n gilt:

I. Ist tein Vielfaches yon d, so ist r ~) = p rood q)d(a). 2. 1St t kein Vietfaches yon d und p --- I rood d, so ist q~p(at) = 1 rood ~d(a). Beweis. (1)

Z u 1: Es ist a ~ = ~ rood ~(a),

D a t e i n Vielfaches yon d ist, ist auch a ~ = 1 rnod ~a(a). Es folgt: q~r(a t) = ~p;(l) = p rood ~d(a). Z u 2: Wir k 6 n n e n t < d voraussetzen. Andernfalls ist t = k . d + t ' mit f < d und at = a k'd+'' = at' rood q~d(a). Well p = 1 rood d ist, gilt: a p = a a'~*l = a rood q~d(a). Wir h a b e n : (2)

a t -- 1 = (aP) ' -- I = a ' ' p -- i = (a t -- 1)" ~ . ( a ' ) rood ~d(a),

Sind (a ~ - i) u n d ~a(a) teiterfremd, so k 6 n n e n wir obige Gleichung m o d u l o ~ ( a ) kfiIzen, Es ergibt sich ~ p ( d ) = 1 rood ~d(a). A n g e n o m m e n a' - 1 und ~d(a) h a b e n einen Primteiler q geme~nsam. D a n n gibt es einen Teller m yon t, so d a b q ein Primteiter yon ~b,.(a) und ~a(a) ist. Also ist m = ord0(a) ~q~ < d = ord~(a) - q! mit I > s. Dabei ist q der gr6Bte P r i m f a k t o r yon d. Einen zweiten gemeinsamen P r i m f a k t o r k 6 n n e n a ~ - 1 und Ca(a) nicht haben. !. Fall: qZ ist kein Teiler yon ~a(a), D a n n ist ~ ( a ) = q , gr wobei W a n d a t - 1 teJlerfremd sind. Wir k 6 n n e n also die Gleichung 2 m o d u l o W durch a t - 1 kiirzen und e r h a l t e n (3)

~(a') = t mod

D a p = i rood d ist, gilt (4)

p = I rood q.

t ist ein Vielfaehes yon ord~(a) also folgt: ~r(a ~) = ~e(t) = p = I rood q und damit (5)

t0n(a' ) = 1 rood q.

Aus 3 und 5 folgt z u s a m m e n : ~ ( a *) - t i s t durch q ua~d W t e i l b a r a n d d a h e r d u t c h q- W = q~d(a). Das heiBt q~n(a') = 1 rood q~(a). 2. Fall: q2 ist ein Teller yon q,a(a). Wegen Satz I Tell 6 gilt d a n n : q = d = 2 a n d q~a(a) = a + I. t ist n a c h Voraussetzung ungerade, also a * = a = - 1 rood ~a(a). Also ist rb~(d) = ~ ( - t) = I rood ~n(a). [] L e m m a 5. Sei wieder p = t rood d, r eine Primzahl und s e N, so daft r . s kein Vielfaches yon d ist. Dann ist ~,.p(a ~) = 1 rood ~d(a). B e w e i s. 1. Fall: r = p. D a n n ist ~r. p(as) = r (a ~) = q~p(a~'~) = 1 rood q~d(a) (nach L e m m a 4). ' 2. Fall: r • p. D a n n 91st ~,.r(a ~ )- fbv(a ~ ) = ~v(a "~ ) = I rood fbd(a ). N u n 1st aeb r ~ p(a s ) = i rood ~a(a). D a m i t folgt die Behauptung. L e m m a 6. Seien r u n d s Zahten, so daft r- s k e i n Vielfaches yon d umt quadratfrei ~st. Dann ist ~ . p ( a ~) = 1 rood r B e w e i s. Wir ffihren den Beweis durch I n d u k t i o n nach der Anzahl der Pfimfaktoren yon r, Ist r selber P r i m z a h l oder 1, so 1st die B e h a u p t u n g schon gezeigt. Sei also r = Pl"''Pk" U n d wenn r weniger als k Primfaktoren hat, so sei die B e h a u p t u n g richtig. M a n hat: ~bp~..-pk.p(aS)" ~p2 ,, .rk-p(as) = r .p~.~(aS'"') 9 N a e h I n d u k t i o n s v o r a u s s e t z u n g ist r

1 mod~'a(a )und

Also ist ~p,., .w.p(a ~) = I rood ~n(a).

[]

Cp~.,.pk.v(a~)= I rood(ha(a).

Vol. 63, 1994

Primitive Primteiler von q~a(a)

503

Satz 7. Sei d eine quadratfreie Z a h l und r, s mit r 9 s = d. AuJ3erdem sei p = I m o d d. O a n n ist ebr. p(a ~) = p rood qid(a). B e w e i s. D u t c h I n d u k t i o n nach der Anzahl der Primfaktoren von r. 9 r = 1: D a n n ist s = d und qSv(ad ) = ~p(1) = p rood ~a(a). o r sei Primzahl. D a n n ist ~,.p(a~) 9 ~p(a ~) = ~bp(aa) = p. 9 Sei die Behauptung richtig fiir alle r mit weniger als /~ Primfaktoren. U n d P~ > P2 > "'" > Pk die verschiedenen Primfaktoren yon r. D a n n ist q~m . . . p~. p(a~) " cbp:. . . p~. p(a ~) = ~e~. . . p~. p(a~" P~).

N a c h Induktionsvoraussetzung ist die rechte Seite der Gleichung = p m o d ~d(a). Wegen L e m m a 6 ist der zweite F a k t o r der linken Seite = 1 rood ~d(a). D a n n ist C])pl...g k .p(a s) = p m o d ~ d(a).

[]

Folgerung 8. I s t d e N quadratfrei und p = 1 m o d d. D a n n ist ~d.p(Cl) = p m o d ~d(a).

Satz 9. Ist d ~ N und p = 1 m o d d eine Primzahl, so ist ~d.p~(a) = p rood q~e(a) f i i r alie r > 1.

B e w e i s. Zun/ichst sei r = 1. Ist d quadratfrei, so ist die Behauptung schon bewiesen. Andernfalls 1/igt sich d = b . c schreiben. D a b e i ist b quadratfrei und c enth/ilt nur Primfaktoren, die in b vorkommen. D a n n hat man: ~d. p(a) = ~bb.~. p(a) = ~b.p (a~) 9 Es ist ~ a ( X ) = ~ b ( X ~) wegen S a t z l Teil2. Wegen F o l g e r u n g 8 ist ~b.p(a~)= p m o d ~d(a). D a h e r ist ~bd.p(a ) = p m o d ~e(a). Sei nun r > 1. D a n n ist ~a. v, (a) = ~bd.v, _, (a p) = ~a. v~-~(a) m o d 4~d(a). Durch I n d u k t i o n sieht m a n die Behauptung.

[]

Folgerung 10. I s t p ein primitiver P r i m f a k t o r yon q~e(a), so ist ~n.p(a) genau einmal durch p teilbar, a u s g e n o m m e n p = 2 und d = 1 und a = 3 rood 4.

B e w e i s . Ist p ein primitiver Primfaktor von 4~a(a), so ist p = 1 m o d d. D a m i t folgt die Behauptung (wegen Satz 1 Tell 6). Folgerung 11. Seien m < n und a > 1 natfirliche Zahlen. D a n n sing dquivalent:

1. ggT(~m(a), ~,(a)) = p. 2. m = ordp(a ) - pr und n = ordv(a ) 9 pS mit r < s. 1. ~ 2.: Ist schon beweisen. 2. ~ 1.: Sei d = ordv(a). D a n n ist p ein primitiver F a k t o r yon ~a(a), und ~,(a) ist genau d n m a l durch p teilbar. ~m(a) ist mindestens einmal durch p teilbar. Also ist p ein gemeinsamer Primfaktor. Einen zweiten k6nnen sie wegen Satz 2 nicht haben. []

504

A. BARTHOLOMI~

ARCH. MATH.

Lemma 12. Sei m ein Faktor yon (~d(a~) und p ein primitiver Faktor yon ~d(a~), so gilt: m " p teilt ~a(a~'P). B e w e i s . Da p ein primitiver Prinffaktor von ~d(a m) ist, kommt p nicht in d vor. Also ist: ~d.p(a~). ~d(a ~) = r Der erste Faktor ist wegen Satz 9 durch p teilbar, der zweite Faktor nach Voraussetzung durch m. Daraus ergibt sich die Behauptung. [] Lemma 13. Seien p >_ q primitive Primfaktoren yon ~d(a), dann ist q ein primitiver Primfaktor yon ~d(aO. B e w e i s . Es ist p = 1 rood d und infolgedessen ist ap = a rood q. Also ist ~d(a~) dutch q teilbar. Und q muB primitiv sein, da q ja nicht in d vorkommt.

Folgerung14.

Ist m irgend ein Teiler von ~a(a), so gilt: 1. Wenn m nur primitive Primfaktoren von ~d(a) enthiilt, so ist m Teller yon ~d(a~). 2. 1st m = p 9 m' und p der einzige nicht primitive Primfaktor und sind sdmtliche Primfaktoren von m' auch primitive Primfaktoren yon ~d. p(a), so ist m Teller yon ~d(am): B e w e i s . Besteht m nur aus primitiven Primfaktoren, so folgt die Behauptung durch I n d u k t i o n und wiederholte Anwendung yon L e m m a 12 und L e m m a 13. I m andern Fall ist m = P" m', wobei p der einzige nicht primitive P r i m f a k t e r yon m ist. Die Primfaktoren yon m' sind alle = 1 rood d, also ist m' = 1 rood d. D a h e r hat m a n am' = a m o d ~d(a). U n d da ~)d(a) durch p teilbar ist, ist a m" = a m o d p; Also ist: ~a(a") = q)d(a pm') = ~d.p(a m') = ~e.p(a) = ~d(a p) = ~d(a) m o d p ist durch p teilbar. Wegen der Argumente vorher ist ~d.p(a m') = Cd(a m) durch m' teilbar. Fiir Primzahlen p hat m a n insbesondere: Satz 15. Fiir eine Primzahl p sind dquivalent: 1. p ist ein primitiver Primfaktor yon r ). 2. Fiir alle Zahlen k e N O ist pk+ l ein Teller yon ~d(aPk). 3. p2 teilt ~/id(aP). B e w e i s. 1. ~ 2.: Gilt wegen L e m m a 12 und 13. 2. ~ 3.: Ist klar. 3. ~ 1.: D a p2 ein Teiler yon ~e(a e) ist, ist p ein Teiler von ~d(a p) = ~ d ( a ) r o o d p. A n g e n o m m e n p ist kein primitiver Primfaktor yon ~a(a). D a n n m u g p ein Teller yon d sein wegen Satz 1 Teil 2. Wegen Satz 1 Teil 6 k a n n d a n n pa nur Teiler yon ~ ( a p) sein, wenn d = p = 2 und a p = a 2 = 3 rood 4 ist. Das k a n n nicht sein. [] Jetzt ergibt sich in v611iger Analogie zu Aufgabe 1 die Antwort auf F r a g e 1 in d e r Einleitung.

Folgerung16, M i t der einzigen Ausnahme yon a = 2 und d = 1 gibt es stets unendlich viele n E N , die Teiler yon ~a(a") sind. Wie man solche n finder, wird im Beweis beschrieben.

Vol. 63, i994

Primitive Primteiler von ~ (a)

505

B e w e i s . Hat ~d(a) /iberhaupt primitive Primfaktoren, so gibt es wegen Satz 15 unendlich viele n e N, die Teiler von ~e(a n) sin& Nach dem Satz yon Zsigmondy ([1] Seite 66, Satz 15.5) gibt es stets solche primitiven Primfaktoren mit folgenden Ausnahmen: 1. d = 2 und a + 1 ist eine Zweierpotenz. 2. d = 6 und a = 2 . 3. d = 1 u n d a = 2 . Zu 1: Ist a + 1 eine Zweierpotenz, so ist aufjeden Fall a ungerade und a 2 + I = ~4(a) keine Zweierpotenz mehr. Also enth/ilt ~ ( a ) mindestens einen ungeraden primitiven Primfaktor p. Also sind s/imtliche pS Teller v o n ~4(aP~). U n d da ~4(a r') gerade ist, folgt: S/imtliche 2 - p s teilen ~4(a p~) = ~ 2 ( a 2 "P~). Zu 2: Ist d = 6 und a = 2, so hat ~6(2) = 22 - 2 + 1 = 3 keinen primitiven Primfaktor. Betrachten wir ~ 6 ( 2 3) -----2 6 -- 23 + 1 = 3 9 19. Es ist 3 ein Teller y o n ~ 6 ( 2 3) = 4~18(2), und 19 ist sogar primitiver Primteiler von ~1s(2). Also gilt fiir s/imtliche n = 3 . 1 9 s, dab sie Teiler v o n ~18(219") = ~ 6 ( 2 n) sind. Die letzte Ausnahme bleibt tats/ichlich Ausnahme. Hier gibt es keine n, die diese Bedingung erf/illen. Den inneren Grund werden wir etwas sp/iter kennenlernen (vergl. Satz 19).

4. Kennzeichnung der n, die ~d(a ~) teilen. Bis jetzt wissen wir, wie wir bei gegebenem d und a jeweils unendlich viele n finden k6nnen, die n I ~d(an) erffillen. Wir brauchen ja nur primitive Primfaktoren yon ~a(a) zu finden. Aber erhalten wir auf diese Weise alle M6glichkeiten? Die Antwort lautet im wesentlichen ja. Aber die Antwort muB etwas vorbereitet werden. Satz 17. Es sei p eine Primzahl und a, r natiirliche Zahlen. 1)ann gilt:

{ mod 9 p,(a) =

mod p

a= mod sonst

B e w e i s. Zun/ichst sei r = 1. Es ist auf jeden Fall (a - 1) = (ap - 1) = (a - 1). ~,(a) mod p. Die erste Gleichung gilt wegen des kleinen Satzes yon Fermat, w/ihrend die zweite aus Satz 1 Teil I folgt. Ist nun a #: 1 m o d p , so ergibt sich: 1 = ~p(a) m o d p . Ist a = l m o d p , so folgt ~ p ( a ) = l + a + . . . + a p-l=p=Omodp. Seinun r>l. Aus Satz 1 Tell 2 folgt: ~pr(a) = ~ g - l ( a p) = ~p~-i (a) mod p (wegen des kleinen Satzes yon Fermat). Es folgt die Behauptung durch InduktiOn. [] Satz 18. Sei d, r ~ N und p eine Primzahl, die nicht in d vorkommt. Dann gilt fiir jede natiirliche Zahl a > I: (~modpfallsordp(a)=d ~d. pr(a) = mod p sonst

506

A. BARTHOLO/r

,~RCH. MATH,

B e w e i s. Wegen des Satzes 1 Teil 2 ist die Behauptung nut ffir r = i zu zeigen. 1st d = I so kennen wir die Aussage schon, wegen Satz 17. Sei die Behauptung ffir alte s < d und beliebiges a > i richfig. Zun/ichst nehmen wir an, dab ordp(a) kein Teller yon d ist. Dann ist ( d - ~3 in 2g/p;E invertierbar. Betrachten wir die Gleichung d"

-

I = (a ~ -

1) = ( a ~ -

1).

I1

p's[p-d

~p.~(a) = (a d -

1)

" (s , d^l-ls
p(o) m o d p .

Der erste Faktor auf der rechten Seite ist nach Induktionsvoraussetzung = I rood p. Damit folgt ~a-p(a) = 1 rood p. Sei nun ordp(a) ein echter Teller von d. D a n n ist d = ( p i " p 2 - ~ ' p k ) ' p ~ + l " ' ~ P~, wobei p~.-- Pk = ordv(a) ist. 1. Fall: p~ k o m m t unter den P2,...,P~ nochmal vor. Dann ist 4~d~p(a)= (Pv~...p .p(aPl). N u n ist (aP0V~P~ = 1 mod p. Das heigt ordp(a p~) ist ein Teiler yon d P z " ' P k und damit ein echter Teller von - - . Es folgt ~m.p~.,~p~-v~+,..-p-p(a)= Pl 9 ~.p(a m) = I mod p. Pl

2. Fall: pt k o m m t nur einmal als Primfaktor von d vor. D a n n hat man: q~a.p(a)" 4~vL.,(a) = qS• o r d e ( a ) = p l . . - p k ist ~e- p(a) = 1 mod p. Bleibt nur noch der faktor yon 4~a(a) und also, da ~d(a) durch p

= i m o d p,

d kein Teiler y o n - - , also ist ~ a p ( a ) = l m o d p . D a m i t ist Pl w Fall d = ord~(a) zu fiberlegela. D a n n ist p ein primifiver Primalso p = 1 I-nod d. Nach Satz 9 ist ~d.p(a) = p rood 4~e(a) und teilbar ist, auch ~,~.p(a) durch p teilbar. []

B e i s p i e 1. Sei d = 6 und p = 5. D a n n hat man ~b~.~(X) = ~ o ( X ) = X 8 + X 7 - X 5 - X ~ - X 3 + X + 1. Man rechnet nun leicht nach, dab f/Jr alle a e {0; 1,2, 3,4} ~ o ( a ) = t rood 5 iSt. Jetzt kann unsere Frage 2 aus der Einleitung beantwortet werden. Satz 19. Seien a, n > 1 und d > t natiirtiche ZahIen. n ~ N teile ~a(a~). Dann ist der kleinste Primfaktor yon n ein Teller yon ~a(a). B e w e i s. Sei p der kleinste Primfaktor von n = p ' . m, m and p teflerfremd. Und d = c- p% c u n d p teilerfremd. N a c h dem kleinen Fermat ist a n = a" rood p. D a n ein Teiler yon qVa(a~) ist, teilt p auch ~/ia(a"). Wegen Satz 18 ist alas genau d a n n der Fall, wenn ordp(a") = c ist. ordp(a m) ist ein Teller von p , 1. Jeder Primfaktor yon m i S t

Vol. 63, 1994

Primitive Primteiler yon ~ (a)

507

gr6ger als p. Also sind m und c teilerfremd. Weiter ist a ~~ = I mod p und damit ordv(a) ein Teiler yon c. D a (am)~ i mod p, ist c = ordp(a ~) ein Teiler yon ordp(a). Das heigt c = ordp(a). Damit ist p ein Teiler von q~(a). Ist c = d, so sind wir fertig. Andernfalls mug man nur Satz 9 anwenden und erh~ilt das gewiinschte Ergebnis. [] Satz 20. Die Zahl n teile cbd( ) , und n = p]~ p]~ sei die Primfaktorzerlegung, wobei die Primfaktoren tier Gr6fle nach geofdnet sind. Dann gilL" P2~..., Ps sind primitive Primfaktoren yon ~ a(ap?) ..... cbn(ap~.... P~zs~). a n

9 9

B e w e i s. Sei i __>2. Es muB dann Pi ein Teiler y o n ~d(a p~.... P~-11) sein. Denn Pl ist ja der kleinste Primfaktor yon n' =

n 9"

und n' teilt ~bd((am)"'), m

p]~ . . . . . . .

Pi-1

Angenommen es wfire kein primitiver Faktor. D a n n ist p~ Primfaktor yon d und z w a r der gr6gte. Betrachten wir nun ein Pk mit i < k < i. Dann ist Pk Teiler von ~d((a~)P~). Es mug Pk ein primitiver Faktor sein, sonst w~ire Pk gr6Bter Primfaktor von d. Das war aber schon p~. Daher ist Pk = 1 rood d und infolgedessen (da p~ Faktor von d ist) -= 1 rood Pi. Das geht aber nicht, da Pk < P~ ist. Insgesamt hat man einen Widerspruch. [] N u n k6nnen die Zahlen n, die Teiler von ~ba(a") sind, vollst~indig charakterisiert werden. Es gilt: Satz 21. Sei n = p] . . . . p~s die Primfaktorzerlegung yon n, wobei die Primfaktoren der Gr6fle nach geordnet sind. Dann gilt: n teilt ~d(a") genau dann, wenn folgende beiden Bedingungen erfi;tllt sind : 1. Pl ist Primteiler yon q~a(a). Ist Pl nicht primitiv, so ist rl = 1. 2. Fiir alle s >- i >- 2 ist pi primitiver Primfaktor yon ~d(a p~.... p~ql).

B e w e i s. p~ muB Primfaktor v o n CPd(a) sein wegen Satz 19. Ist p~ nicht primitiv, so ist Pl ein Teiler yon d. Angenommen p~[ ~d(a n) = ~d((a~)m). Also ist wegen Satz 15 Pl ein primitiver Faktor yon ~ d ( ( a ~ ) . In d k o m m t p~ also nicht vor. Oas ist widerspriichlich. Die Bedingung 2 ist schon vorher gezeigt worden. Zur Umkehrung: Wegen Folgerung 14 ist p~ ein Teiler yon ~d(am). N u n folgt durch vollstfindige Induktion und mit dem Lemma 13 die Behauptung. [] Z u m SehluB noch zwei Beispiele: 1. Ist M = 2p - 1 = ~bp(2) eine Mersennsche Primzahl, so gilt ffir alle k ~ N und allen = M k, dab n ein Teller yon ~p(2") ist. 2. Euler zerlegte die 5re Fermatzahl F 5 = 225 + i = tP26(2 ) = 641 9 6700417. D a beides primitive Primfaktoren sind, gilt ffir alle natfirlichen Zahlen der F o r m n = 641r- 6700417 ~, dab n ein Teiler y o n t~26(2n ) ist. Dasselbe gilt natiirlich fiir alle anderen Zerlegungen von Fermat-Zahlen. Dank: Herrn Josef Rung m6chte ich daffir danken, dab er reich auf einen Fehler im Beweis zum Lemma 4 aufmerksam machte und mir half den Fehler zu beseitigen.

508

A. BARTHOLOM~

ARCH. MATH.

Literaturverzeichnis

[1] H. LiJNEBURG,Galoisfelder, Kreisteilungsk6rper und Schieberegisterfolgen. Mannheim ~979. [2] H. LONEBUR~, Ein einfacher Beweis fOx den Satz von Zsigmondy fiber primitive Pfimteiler yon A N - 1. LNM 893, Berlin-Heidelberg-New York 1981. [3] T. NAGELL,Introduction to Number Theory. Stockholm 1951. [4] W. SmRPINSKI,250 probl~mes de th6orie ~16mentaires des nombres. Paris 1972. Eingegangen am17.2.1994 AnschrifldesAutors: Andreas Bartholom6 Schirmgasse 275 D-84028 Landshut