Eine Bemerkung über die Ordnungen von 2 (mod U)bei ungeradem U

Von

HELMUT MÜLLER

Abstrakt. Da 2 und eine ungerade Zahl u, u ^ 3 teilerfremd sind, existiert dieOrdnung l�u� von 2 �mod u� in der primen Restklasse Z=uZ. Im Zusammenhang mitdem ,,qx� 1ª-Problem haben Z. Franco und C. Pomerance die Verteilung von l�u�studiert und dabei gezeigt, daû die asymptotische Dichte der Zahlen u, für die l�u� nichtdurch eine feste Zahl n teilbar sind, Null ist. In dieser Note wird dieses Ergebnis fürprimes n � q quantifiziert: Es gilt für x! 1

x

log 1=�qÿ1�x�Xu % xqBl�u�

1� x

log 1=qx:

1. Es sei u ^ 3 eine ungerade natürliche Zahl. Dann sind 2 und u teilerfremd, so daû esZahlen l 2 N gibt mit

2l � 1 �mod u� :Der kleinste dieser Exponenten l � l�u� heiût Ordnung der Restklasse 2 �mod u� in derprimen Restklassengruppe �Z=uZ��. Bekannlich teilt l�u� stets f�u�, wobei mit derEulerschen Funktion f�u� die Anzahl der primen Restklassen modulo u bezeichnet ist.

Im Zusammenhang mit einer Vermutung von R. E. Crandall über das ,,qx� 1ª-Problemhaben Z. Franco und C. Pomerance ([2] 1)) die Verteilung der Ordnungen l�u� studiert unddabei folgendes Resultat erzielt (Theorem 5):

Für jedes feste n 2 N hat die Menge der ungeraden Zahlen u mit nBl�u� die asymptotischeDichte 0.

Ziel dieser Note ist es, für primes n diese Aussage in einer etwas quantitativeren Form zubeweisen, nämlich

Satz. Ist q 2 N, q ^ 3 eine Primzahl, so gilt für x!1x

log 1=�qÿ1�x�Xu % xqBl�u�

1� x

log 1=qx:

Arch. Math. 69 (1997) 217±2200003-889X/97/030217-04 $ 2.30/0� Birkhäuser Verlag, Basel, 1997 Archiv der Mathematik

Mathematics Subject Classification (1991): 11A25, 11N25.1) Bei der Aufzählung der ,,Wieferichª Zahlen bis 1000 ist die 55 vergessen worden.

Wie in [2] werden die gesuchten Zahlen u mit qBl�u� mit Hilfe der Lösungsanzahlengeeigneter Kongruenzen bestimmt. Daher betrachten wir zunächst für eine ungeradePrimzahl p die Kongruenz

xq ÿ 2 � 0 �mod p� ;�1�ihre Lösungsanzahl sei ��p�. Für sie gilt bekanntlich

��p� � 0 oder ��p� � �pÿ 1; q� :Verschwindet ��p�, so teilt q die Ordnung l�p�. Wegen l�p� jf�p� � pÿ 1 erhalten wir weiterdie ¾quivalenzen

p �j 1 �mod q� () ��p� � 1p � 1 �mod q� () ��p� � 0 oder ��p� � q :

�2�

Ehe wir mit dem Beweis des Satzes beginnen, notieren wir noch das folgende, leicht zubeweisende

Lemma. Ist 1 < n1 < n2 < . . . eine Folge natürlicher Zahlen mitXni % x

1ni� a log log x� b� o�1�

für a, b 2 R und x! 1 , so gibt es ein g > 0 mitYni % x

�1ÿ 1

ni

�� g � log ÿax :

Be we i s de s Sa tz es. Im folgenden seien mit c1; c2; . . . geeignete Konstantenbezeichnet, deren exakte Werte hier nicht interessieren. Da das Polynom xq ÿ 2 über Q�x�irreduzibel ist, gilt nach dem Primidealsatz (siehe z. B. [1], Lemma 2.11, S. 93) für x!1X

p % x

��p�p� log log x� c1 � o�1� :�3�

Zerlegen wir nun diese Summe inXp % x

��p�p�Xp % x��p��1

1p� q

Xp % x��p��q

1p

�4�

und verwenden den Primzahlsatz für die arithmetische Progression in der FormXp % x

p�h �mod q�

1p� 1

f�q� log log x� c2 � o�1� für �h; q� � 1 ;

so erhalten wir nach (2) für x! 1Xp % x��p��1

1p�

Xp % x

p�j 1 �mod q�

1p� qÿ 2

qÿ 1log log x� c3 � o�1� :

218 H. MÜLLER ARCH. MATH.

Mit (4) und (3) folgt darausXp % x��p��1

1p� 1

q�qÿ 1� log log x� c4 � o�1�

und weiter Xp % x��p��0

1p�Xp % x

1pÿXp % x��p��1

1pÿXp % x��p��q

1p

� 1ÿ qÿ 2qÿ 1

ÿ 1q�qÿ 1�

� �log log x� c5 � o�1�

� 1q

log log x� c5 � o�1� :�5�

Setzen wir noch für x > 3

P1�x� :�Yp % x

qjl�p�

p und P2�x� :�Y

p % x��p��0

p ;

dann wird P1�x� stets von P2�x� geteilt. Da für alle Primteiler p von u offensichtlich l�p� j l�u�gilt, erhalten wirX

u % xqBl�u�

1 %Xu % x

pju)qBl�p�

1 �Xu % x

�u;P1�x���1

1 %Xu % x

�u;P2�x���1

1 :

Nach Theorem 3.5 in ([3], Seite 105) ist diese Summe für x!1

� x � f�P2�x��P2�x� � x �

Yp % x

��p��0

�1ÿ 1p� :

Nach obigem Lemma und (5) ist dies weiter

� xlog1=qx

:

Damit ist die obere Abschätzung des Satzes bewiesen. Um auch die untere Abschätzung zuerhalten, setzen wir

S :�Xu % x

q2Bupju)p�j 1 �q�

1 �Xu % x

qBf�u�

1 %Xu % x

qBl�u�

1 :

Um S weiter abzuschätzen, definieren wir eine zahlentheoretische Funktion f für einePrimzahlpotenz pe durch

f �pe� :�1; p � q; e � 1;

1; falls p �j 1 �mod q� ;0; sonst;

8><>:

219Vol. 69, 1997 Eine Bemerkung über die Ordnungen von 2 (mod U)

und setzen f auf N multiplikativ fort. Dann gilt

S �Xn % x

f �n� :

Wegen 0 % f �n� % 1 und des Primzahlsatzes für die arithmetische Progression in der FormXp % x

f �p� �Xp % x

p�j 1 �mod q�

1 � qÿ 2qÿ 1

� xlog x

läût sich auf f ein Satz von E. Wirsing ([4]) anwenden, der hier für x!1 liefert

S � c6 � xlog x

�Y

p % x

n1� f �p�

p� f �p2�

p2 � � � �o:�6�

Bis auf eine Konstante ist das Produkt gleichYp % x

p�j 1 �mod q�

n1� 1

p� 1

p2 � � � �o�

Yp % x

p�j 1 �mod q�

�1ÿ 1

p

�ÿ1� c7log �qÿ2�=�qÿ1�x

nach obigem Lemma. Setzen wir dies in (6) ein, so folgt schlieûlich

S � c8 � x

log 1=�qÿ1�x;

womit der Satz bewiesen ist.

Will man die Unsymmetrie in den Abschätzungen des Satzes vermeiden, wird man wohlberücksichtigen müssen, daû die Bedingungen

��p� � 0 und l�p� � 0 �mod q�nicht äquivalent sind, wie sich an dem Beispiel p � 151, q � 5, l�151� � 15, aber225 � 2 �mod 151� ablesen läût.

Literatur

[1] P. D. T. A. ELLIOTT, Probabilistic Number Theory I. New York-Heidelberg-Berlin 1979.[2] Z. FRANCO and C. POMERANCE, On a Conjecture of Crandall Concerning the qx� 1 Problem. Math.

Comp. 64, 1333 ± 1336 (1995).[3] H. HALBERSTAM and H.-R. RICHERT, Sieve Methods. London 1974.[4] E. WIRSING, Das asymptotische Verhalten von Summen über multiplikative Funktionen. Math.

Annalen 143, 75 ± 102 (1961).

Eingegangen am 1. 10. 1996

Anschrift des Autors:

Helmut MüllerMathematisches SeminarUniversität HamburgBundesstraûe 55D-20146 Hamburg

220 H. MÜLLER ARCH. MATH.