Arch. Math., Vol. 42, 362-365 (1984) 0003-889X/84/4204-0362 $2.30/0 �9 1984 Birkhfiuser Verlag, Basel

Teilbarkeitseigenschaften der iterierten Euler'schen Phi-Funktion

Von

FRANZ HALTER-KOCH und WERNER STEINDL

1. Sei qo: N - + N die Euler ' sche P h i - F u n k t i o n ([4], chap. VI), (po= id N und ~o z = (p o ~o z - 1 fiir l e N. Die so i ter ier te Euler ' sche P h i - F u n k t i o n war auch in neuerer Zei t i m m e r wieder G e g e n s t a n d e lementa r -zah len theore t i sche r Unte r suchungen , siehe e twa [11, [3] und [5]. Die vor l iegende N o t e schliel3t an [1] an; ffir Q, l ~ N sei

Sq(/) - {n e NI q~l(n) [Qn},

Po(I) = n~S~( l ) l ~0/SQ(I) ,

und f/Jr n e N sei

C(n) -- m i n { / > 0l ~o~(n) < 2},

also C(1) = C (2) = 0, ~o c (")(n) = 2 ffir n > 2 und ~o c (")- l(n) > 2 ffir n > 2. In [11 wurde die M e n g e S~(l) volls t / indig charak te r i s ie r t ; wir un te rsuchen bier a l lgemeiner die Mengen So(1 ) fiir bel iebiges Q, geben im Fa l le eines ungeraden Q eine vollstf indige Charak te r i s i e - rung (in Vera l lgemeinerung von [1]) und zeigen a n h a n d von Beispielen das Feh len / ihn l i - cher Gesetzmfil3igkeiten ffir gerades Q.

2. L e m m a 1. Seien Q, l, n ~ N .

a) So(l) = {2"mlmePQ(1), ~ > 0}. b) Aus n ~ Po(1) folgt 4Xn. c) Ist C(n) < l, so folgt n ~ SQ(l) und genau dann n ~ PQ(1), wenn 2Xn. d) Ist C(n) > l, Q ungerade und n e PQ(1), so folgt n - 2 m o d 4 . e) Fi;tr ungerades n ist genau dann n ~ S2Q(1)\Se(1 ), wenn 2n ~ PQ(l).

B e w e i s. Sind a, l, n ~ N und setzt man L = C(n), so gilt:

[2 ~-1. ~oZ(n), falls -= lmod2 , I < L + 1; n

= ~ 2 ~- ~oI(n), falls n --- 0mod2, l < L + 1; /2 max(~ falls n =- 1rood2, l > L + 1; [2 max{~ falls n--- 0rood2, l > L + l .

Aus diesen (durch Induktion leicht zu beweisenden) Formeln ergeben sich unmittelbar die Behaup- tungen von Lemma 1.

Vol. 42, 1984 Phi-Funktion 363

I m Hinb l i ck auf L e m m a 1, d) und e), genfigt es nun, Zah l en n -- 2 r o o d 4 mi t C(n) > l zu untersuchen.

Sei Q = 2qm mi t q > 0 und m ---- l m o d 2 ; sei nePo(1), C(n) > l u n d n = 2 m o d 4 . F/Jr j ~ {0, 1 . . . . . I} setzen wir

r 2

~o'(n) = 2",. r I Pj,aa'~ ~ = 1

mit rj > O, paa rweise versch iedenen unge raden P r imzah len p j , , , . . . , p ~ , , , , aj > 0 und a~,Q > 1 ffir a l l e j e {0 . . . . ,1}, 0 e {1 . . . . . ri}. W e g e n n = 2 m o d 4 ist d a n n a o = 1 und aus C(n) > I folgt aj > 1 ffir alle j e {1 . . . . . l} ferner ist

r j_ 1

q)J(n) = (p [ ( p a - l ( n ) ] = 2 a , - 1 - i . I-[ p~:_;, ,g-i " ( & - i , 0 - 1), 0 = 1

und da raus folgt

a j > = a j _ i - - l + r j_l

ftir alle j e { 1, 2 . . . . , l}. W e g e n n ~ Po(l) ist q~l(n)[ Q n und folglich

a l < q + l.

Addie r t m a n alle diese Ungle ichungen , so folgt

I

Z (rj-a -- 1) __< q. ] = l

3. Sei nun Q ungerade , also q = 0. Is t d a n n n ~ PQ(1) und C(n) > l, so folgt n --- 2 m o d 4; ist u m g e k e h r t n - 2 m o d 4 und C (n) = l, so folgt n E PQ(/). W i r in teress ieren uns dahe r im F o l g e n d e n nur noch ffir den Fa l l C(n) > l; d a n n ist aber r, > 1 und folglich rj > 1 ffir alle j E {0 . . . . . 1 - 1}. Aus 2. ergibt sich nun unmi t t e lba r :

L e m m a 2. Sei Q ungerade, I ~ N , n6Po.(l ) und C ( n ) > 1. Dann gilt f i i r alle j ~ { 0 . . . . . l - 1}

~r =- 2p~,

mit ungeraden Primzahlen p j und cj > 1. D e r folgende Satz br ing t die angek i ind ig te Klass i f ika t ion der n ~ Po(l) fiir ungerades Q.

Satz. Seien Q, 1, n ~ N , C (n) > l, 2 X Q. Genau dann ist n ~ PQ(I), wenn einer der folgenden Fiille vorliegt:

A) n = 2 . 3 c m i t c > l + 1. B) n = 2p mit einer Primzahl p der Form p = 2 . 3 c + 1, wobei c > m a x {2, I} und

3 c + i - l l Q .

C) n = 2Z(p + 1 ) - 2 mit einer Primzahl p > 3 derart, daft P@2_ (2 l _ 1) Q und die l Zahlen 2rp + 2 r - 1 (r = 0 . . . . . l - 1) prim sind.

z.,

364 F. HALTER-KOCH und W. STEINDL ARCH. MATH.

B e w e i s . Na ch L e m m a 2 ist q)J(n)=2p~J ffir alle j E { 0 . . . . , / - 1 } m i t Exponen ten c o . . . . . c~_ 1 s N , also speziell n = 2p{~ ~ Wi t zeigen zun/ichst :

~Ist cj > 2 ffir ein j ~ {0 I - 2}, so folgt

(*) (Pj =Pj+I = " . = P l - 1 . . . . = 3 .

Ff i r j 6 {0 . . . . . l - 2} gilt n / imhch q ) j + l ( n ) = cp (2p}J) = p~J 1. (pj _ 1) = 2p~+§ ist n u n cj > 2 oder pj = 3, so folgt pj+ 1 = Pj = 3 und da raus (,) du rch Indukt ion .

F a 11 1 :po = 3. W egen C(n) > l folgt c o > 1 + 1, also gilt A).

F a l l 2 : P o > 3. D a n n i s t c o = l wegen(*) .

F a 11 2 a : Es gibt e in j s {1 . . . . . 1 - 1} mit c o = c 1 . . . . . cj_ 1 = 1 und c~ > 2. Wegen (*) ist d a n n Pj = P j + I . . . . . Pt-1 = 3. W/ire j > 2, so folgte

q)~ - 1 (n) = q~ (2pj _ 2) = P j - 2 -- 1 = 2pi_ 1,

qfl(n) = p j_ 1 - 1 = 2C'pi = 2 c ' . 3,

also P~-2 = 1 + 2 - (2 c'. 3 + 1) -= 0 m o d 3 , abe t cj > 2, ein Widerspruch . Folglich i s t j = 1,p 1 = 3, c I > 2, n = 2Po und qo(n) = Po - 1 = 2 - 3 cl. Wegen C(n) > / folgt c 1 > l,

und aus ~ol(n) = 2 - 3 c ' - l+ 112 Qpo folgt 3 c~-1+ I IQ, so dab B) mit p = Po, c = c~ gilt.

F a l l 2 b : c o = c , = . . . = c l _ ~ = l . W i r s e t z e n p l , = p ; d a n n i s t q ~ ( n ) = p - l > 2 , a l s o p > 3 und p - l [ 2 Q p o. N u n erhhlt m a n durch Induk t i on unmi t t e lba r pj = 21 J- ~. (p + 1) - 1 ffir alle j E{0 . . . . . l - l } , also s ind die l Zah len 2 ' p + 2 " - 1 ( r = 0 . . . . , l - l ) Pr imzahlen , und

n = 2Po = 21(p + 1) - 2; wegen nQ = 2 1 + 1 Q - P @ + 2Q �9 (2 z - 1) ist p - l l n Q / iquivalent zu

- 1 Q P ~ �9 (2 l - 1), und es gilt C).

B e m e r k u n g . Llegt im Satz der Fall B) vor, so ist no twendig p < 1 + 2 Q - ( 2 I - 1 ) , n < 2P(p + i ) - 2.

e w e i s . A u s P ~ l (2 ~ _ I ) Q f o l g t p < 1 + 2 Q . ( 2 l - 1 ) ; ist U p + 2 ~ - B 1 P r lmzah l fiir e i i 1

r > 1, so folgt 2 ' ~ 1 m o d p also sicher r =t = p - 1. Gilt n u n B), so sind die l Zah len 2~p + 2 ~ - 1 ( r = 0 . . . . . l - 1 ) Pr imzahlen , also l - l < p - 1 , und da raus folgt n = 2 t ( p + l ) - 2 < 2P(p + 1) - 2, q.e.d.

4. Die beiden folgenden Beispiele zeigen, dab im Falle eines geraden Q keine so emfache Gesetz- m/if3igkeit wie die in Satz 3 fo rmuher te gelten kann :

1) n = 2 - 7 - (64p + 63), p = 1122659, I = 8 Q = 24. 3 . 7 - 23 �9 41, q)a(n) = 25. 3 �9 72. 23 - 41 (Sonderrolle von 7);

2) n = 2 . 1 1 . ( 6 4 p + 6 3 ) , p = 2 1 6 4 2 2 9 , 1 = 7 Q = 24. 101 - 487, q)7(n) = 25. 11 �9 101 �9 487 (Sonderrolle von 11).

Die in den beiden Beispielen verwendeten P r imzah len p haben die Eigenschaft , dab die 7 Zah len 2~p + 2 ~ - 1 (r = 0, 1 , . . . , 6) alle P r imzah len sind. Bis heute s ind unseres Wissens keine 1/ingeren s o g e n a n n t e n , , C u n n i n g h a m - K e t t e n " bekannt . Der k leme Fe rma t ' s che Satz lehrt, dab eine yon p ausgehende Ket te von P r imzah len 2"p + 2 * - 1 (r = 0, 1 . . . . ) h6chs tens die L/tnge 1 + ordp(2 ) < p h a b e n kann.

Aus A. Schinzel 's Hypo these H ([4], Chap. III ,w 8) folgt fiir jedes r e N die Existenz unendl ich vieler C u n n i n g h a m - K e t t e n der L/inge r; m a n ha t hierffir nu r die r P o l y n o m e fj(x) = 2ix + 2 J - 1 (1 = 0 . . . . . r - 1) zu betrachten. Wir verfeinern diese K o n s t r u k t i o n und zeigen:

B e m e r k u n g . Es gelte die Schinzel 'sche Hypo these H ffir l ineare Po lynome ; p sel eine Pr im- zahl, L = C(p) und l > L + 2. D a n n gibt es unendl ich viele Zah len Q mit 2 z I[ Q und z u j e d e m solchen Q ein n ~ Po.(1) mit p in , aber p I Q .

Vol. 42, 1984 P h i - F u n k t i o n 365

B e w e i s . Wir be t rach ten die l Po lynome

f~(x) = 2 r + l p . ( 2 x + 1) + U +1 - 1 eTl[x]

(r = 0 , . . . , l - 1); sic haben posit iven h6chs ten Koeffizienten, sind irreduzibel, und zu jeder Pr imzahl 1--1

q gabt es ein z e ~g mit q ] I~ fr(z) (man ha t nu t z E 7l mit p �9 (2 z + 1) -= - 1 rood q zu w/ihlen). r = O

Nach der Hypothese H gibt es d a n n aber unendl ich viele z E Z , so dab die l Zah len P, = 2 r + l p - (2z + 1) + 2 r+l - 1 P r imzah len sind; mit n = 2pPl_ 1 und Q = 2 L. (2x + 1) folgt die Behauptung.

Literaturverzeichnis

[1] M. HAUS~tANN, The solut ion of a special ar i thmet ic equat ion. Canad. Math . Bull. 25, 114 -117 (1982).

[2] D. H. LEItMER, On cer tain chains of primes. Proc. L o n d o n Math . Soc. 14A, 183-186 (1965). [3] H. N. SHAPmO, A n Ar i thmet ic Func t ion Aris ing f rom the ~b Funct ion . Amer. Ma th . M o n t h l y

50, 1 8 - 3 0 (1943). [4] W. SIERPINSK~, E lementary Theory of Numbers . Warszawa 1964. [5] W. STEIND>, Bemerkungen zur i terierten Euler ' schen Ph i -Funkt ion . Disser tat ion, Graz 1978.

Eingegangen am 14. 6. 1983

Anschr i f t des Autors :

F ranz Ha l t e r -Koch und Werner Steindl Mathemat i sches Ins t i tu t der Universi tf i t Graz Halb/ i r thgasse I / I A-8010 G r a z