Teoria liczb 83-01-14015-1 [PDF]

Zitiervorschau

SPIS RZECZY Przedmowa ...........................•............................•.................

7

Oznaczenia. . . . .. . . . .. . . . . . . . . .. .. . . . . . . . . .. . . . . . . . . . . . . . •. . . . . . .. . •. .. . . . .. .•. .. . . . .

\\

Rozdział

13

1.

Podsławowe pojęcio

1.1. Podzielnośt. liczby pienr.'SZc . . . . .. . . . .. . . . . . . . . . . . . . . . .. . . . .. . . . .. . . . . . . . . . . . . . . . . . 1.2. JedflQ7,nOC7.nośł ro7J.:łoou na czynniki pienr."S7.e .. _ . _. . . . .. . . . .. . • . .. . . . .. . •. .. .. . . . 1.3. LiniOY>l: ro....nania diorantycuoe. . . . .. . . . .. . . . . . . . . . . .. . •. . . . . . .. . •. .. . . . .. .•. .. .. . ..

13 24 31

Rozdzioł

2. Kongruencje...................................... .•........ .•........

36

Podsl.a"''O''l: własności Reszty wz&l~nie pierwsu z modułem. . . . . . .. . . . .. . . . .. . . . . . . . . . . . . . . . . . . . . .. . . . .. . Kongruencje kwadnlłOY>\': . .. . . . . . . . . . . . . . . . .. . . . .. . . . .. . . . . . . . . . . . . . . . .. . . . .. . . . .. . ZastOSQYl'llnie sum trygonometrycznych w teorii kongroencji.. . . . . . .. . .. . . . . . •. . . . .. . . . .

36 50 58 67

2.1. 2.2. 2.3. 2.4.

Rozdział

3. Równania

diofanłyczne

79

3_1. Równania drugiego stopnia 3.2. Równania wyższych Slopni Rozdzioł

_. _

.................................

4. Funkcje arytmetyczne...

79 89 98

4.1. Podstawowi: pojęcia . . . . . . . . . . . . . . • . . . . . . . . •• . . . . . . . . . . 4.2. Funkcje addytywne i ll1uhiplikatywne .. .. ..•.. .. .•..... ....•..... . 4.3. Gęstości i waflości średnic 4.4. Charaktery .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ....................

98 107 124 134

Rozdzial 5. liczby pierwsze

.

146

5.1. Twierdzenie Czebyszewa 5.2. S7.eregi DirichJcla 5.3. Twicrd7.cnic o liczbach pierwszych

.

Rozdzial 6. Metody sita 6.\. Sito Er'ltoslcncsa 6.2. Wielkie SilO Rozdział

.

.

. . . .. .. .. . . .

. ........................

-

.

.

. ... .. ..... ..... .. ... .. ... .. ... . ..

. .

7.1. TWierdzenie Minkowskiego o bryle wypuklej 7.2. Punkty kratowe w obszarach na plaszczy1:nie

. .

172

.

196 196 204

. . . . . . . .. .....

216

.

,

7. Zagadnienia geometryczne w teorii liczb

146 156

.

216 225

""'w.

, N:uk;ewi l. tj. "łamka alb nie da ~'ię IIprm'óć. Dowód: Istnienie

się

przedstawienia wynika z definicji liczb wymiernych jako ilorazów liczb całkowitych. By udowodnić jcdnoznaczność tego przedstawienia, przyjmijmy, że w = a/b jest nieskracalnym ułamkiem z b > O. Niech nadto spośród wszystkich przedstawień liczby w w postaci ułamka, ułamek w = x/y (x. y E Z, Y > O) ma licznik o najmniejszej wartości bezwzględnej. Wystarczy teraz wykazać równości a = x i b = y. Z wniosku l otrzymujemy xla, a zatem a = xal przy pewnym al E Z. Wówczas z hx = ay = alXY otrzymujemy b = alY, a więc al dzieli zarówno a, jak i b. Ze względu na al = y/b> O otrzymujemy al = l, a więc y = b i x = a. D Następujący

żądanego

rezultat jest

często

zwany zasadIIiczym twierdzeniem arytmetyki:

WNIOSEK 3. Je-I'li P je~'1 liczbą IJierwszą dzielącą iloczyn (/wóch liczb całkowitych. to

dzieli

też jedną

z nich.

Dowód: Jeśli plah, to mozemy napisać ab = pc, gdzie c jest liczbą całkowitą.

Rozpatrzmy

ułamek

p a r = - =-.

b

c

Niech r = x/y (x. y E Z) będzie przedstawieniem liczby r w postaci ilorazu liczb całkowitych z minimalnym, co do modułu. licznikiem. Z wniosku l wynika xlp, a więc x = ±I lub x = ±p. Ponadto z tegoż wniosku otrzymujemy xla. Jeśli teraz x = ±p. to pla, a jeżeli x = ±L to P l - = ±-,

b

a

więc

b/ P =

±y E Z i widzimy,

że

Y

plb. D

WNIOSEK 4. Je-I'li p jest liczbą IJienvszą dzielącą ilocz)'n alal'"

najmniej jedllą

{In.

/o

p dzieli przy-

z liczb al, a2, ... , ano

Dowód: Zastosujemy

Przypadek fi = 2 jest zawarty w poprzednim wniosku, a krok indukcyjny wynika z uwagi, że jeśli plala2" ·an +! = al ((/2 ... all+d. to z poprzedniego wniosku wynika. że plal lub też plal" ·an i możemy skorzystać z przesłanki indukcyjnej. D indukcję względem fi.

2. Liczby pierwsze są cegiełkami, z których zbudowane treścią następującego twierdzenia:

są

liczby naturalne. Jest to

16

1. Podslowowe

pojęcio

TWIERDZENIE 1.3. Każda liczba /latura/na II > /I

przy czym k > I. liczby

zaś

I da

się przed~'lawi('

w postaci (1.1 )

= P1P2'" {h,

PI .... , Pl

są

/Jienvsze.

Dowód: Zastosujemy indukcję. Przy n = 2 przyjmiemy oczywiście k = 1, PI = 2. Załóżmy teraz prawdziwość tezy dla wszystkich fi < N. Jeśli N jest liczbą pierwszą, to kladziemy k= 1, PI =N. W przeciwnym razie możemy napisać N=ab, 1 2). to liczba MI' jest I,ierwsza wtedy i tylko wtnly, gdy M"ISI'_I'

Dowód tego testu znaleźć można m.in. w następujących książkach: Sierpirlski [41, Narkiewiez [2]. Bardzo prosty dowód znalazł niedawno J.w. Bruce [l]. Największą obecnie (grudzień 2002) znaną liczbą pierwszą jest liczba M 13466917 , mająca 4053946 cyfr (M. Cameron, student z Kanady), a poprzednim I rekordem była liczba M6972S93 (N. Hajratwala i zespół, czerwiec 1999). Zobaczymy później, że zbiór wszystkich liczb pierwszych jest nieskończony. a więc znajdowanie coraz to większych takich liczb może świadczyć jedynie o rozwoju techniki obliczeniowej, a do samej teorii wnosi niewiele. Nie jest to wszakże zadanie całkowicie bezużyteczne, gdyż duże liczby pierwsze są używane do konstrukcji trudnych do złamania kodów (patrz np. Koblitz [1]). 4. Ilość liczb pierwszych nie przekraczających x oznacza się tradycyjnie przez JT(x). Mamy oczywiście JT(2) = l, 7T(IO) = 4, a nietrudno sprawdzić. że 7T(IOO) = 25, 7T(IOOO) = 168, 7T(I04) = 1291. Nieco dłużej trwa sprawdzenie równości JT(I0 8) = 5761455. Już w Elementach Euklidesa można znalcźć dowód tego. że liczb pierwszych jest nieskończenie wiele, Ij. Podamy teraz cztery dowody tego rezultatu: TWIERDZENIE 1.4. Zbiór P liczb pierwszych jestllieskOllczolly. Dowód I (Euklides). Przypuśćmy. że P = (PI. P2 ..... Pll} jest zbiorem skończonym.

Liczba N = [ + PI Pl' .. PIP jest większa od jedności, a przy tym daje ona resztę l =F O przy dzieleniu przez każdą liczbę pierwszą. Zatem nie dzieli się przez liczbę pierwszą, co przeczy wnioskowi l z poprzedniego twierdzenia. O

równą żadną

Dowód II (L. Euler). W tym dowodzie wykorzystamy rozbieżność szeregu harmo-

Il1cznego

IAktualną liSIę największych znanych liczb pierwszych można znaleźć ..... inlernecie pod adresem www.ulm.edulresearch/primesl/largesl.hlml

ISB~ ~Hl1-14015-1. l,)

by

W~ PW~

2lJ(lJ

18 1. Podstawowe

pojęcia

Przyjmijmy. że zbiór {PI. P2, ...• p,,} jest zbiorem wszystkich liczb pierwszych. Korzystając z wzoru na sumę postępu geometrycznego, otrzymujemy dla x > l "(

f1 \-

l=l

I )-' p' = k

I

"00

00

I

00

f1 L:: jPk; = j,=o L:: j,=O L:: (lo

l=l J=O

PI

...

00

i,), >

P"

\

L:: m'

(1.2)

m=l

wobec wniosku 2 z twierdzenia 1.3 każda liczba naturalna 11/ > l da się w postaci iloczynu potęg liczb pierwszych. Niech gdyż

przedstawić

"( \-- )-'

a~f1

\ Ih

k=l

i niech T

będzie liczbą naturalną

tak

dobraną,

T

by

zachodziła nierówność

\

L::->a. m

tII= l

Jest to

możliwe

Korzystając

0/

= lim

ze względu na rozbieżność szeregu harmonicznego. z (1.2), otrzymujemy teraz

n"( x\)-1 l-

Pk

' ..... ll=1

co jest jawną

> lim sup

sprzecznością.

.l..... I

L00 -,l > lim sup L ----;l = L -l T

m=l 111

x_I

T

m=1 11/

> a.

m=1 11/

D

Dowód III (C. Goldbach). Liczby F" = 2 2"

+

I są przy

/l

= \,2 .... większe od

jedności.

a zatem z wniosku l z twierdzenia 1.3 wynika. że każda z nich ma dzielnik picrwszy. Niech q" będzic jednym z dzielników pierwszych liczby F". Pokażemy, że liczby ql. q2, ... są wszystkie różne, a to da nam natychmiast nieskOl1czoność zbioru liczb pierwszych. Przypuśćmy, że dla pewnych 11/ < /l mamy qm = q". Ponieważ przy odpowiednim a E N marny ,. 2- = aq", - l.

a zatem

F" __ ,,2' _

+I

_

,,2~ 2"-" _ (_)

+l

_

_ (aq", - l) 2'-"

+ l.

Stosując do potęgi «(I(lm -\ )2'-" wzór dwumianowy Newtona. widzimy, że wszystkie jego składniki poza ostatnim dzielą się przez q"" a ostatni składnik jest równy (-I )2'-~ = l. Zatem przy odpowiednim naturalnym b możemy napisać Fil = bqm + 2 = bq" + 2,

a ponieważ q"IF", przeto z twierdzenia 1.1 (i) wynika podzielność liczby 2 prl:ez q", a więc qll = 2. To nie jest jednakże możliwe, gdyż q" jest dzielnikiem nieparzystej liczby F". D Najprostszy - jak przez C. Hermite'a:

się

wydaje -

jest

następujący

dowód podawany na

wykładach

Dowód IV: Oznaczmy przez q" najmniejszy dzielnik pierwszy liczby II!+ 1. Ponieważ II! + l daje resztę I z dzielenia prLez każdą liczbę pierwszą P II, a WIęC

lim,,_oo ą" = 00, D

w. N..k; l wszystkich liczb b i • a wówczas iloczyn d D > (/ byłby wspólnym dzielnikiem liczb ai. Z uwagi tej będziemy częSIO korzystali. 6.

Jeśli

TWIERDZENIE 1.6. Jeśli al,

jedna jest

różna

al, ... , ak są liczbami calkowitymi. z klórych przynajmniej od zera, 10 iS/IIiejq takie liczby całkowite XI, Xl .... , Xb że k

La;xi =

(1.4)

(01,02 .... ,Ok),

i=1

a przy Iym (aj.a2 ..... ak) w postoci (lA).

je!itllajlllniejszą

ficzbą naturalną.

dajqcq

się

przedstawil

Dowód: Niech d = (al. a2 ..... ad. a I niech będzie zbiorem wszystkich liczb cał­

kowitych dających się przedstawić w postaci (lA). Widzimy bez trudu. że jeśli a,b E I, to a±b E I, ajeśli a E I, a fl jest dowolną liczbą całkowitą, to /la E I. (Używającjęzyka algebry. możemy zatem powiedzieć. że / jest ideałem w pierścieniu liczb całkowitych). Oznaczmy przez D najmniejszą liczbę naturalną, zawartą w I. Z twierdzenia 1.2 wynika. że możemy znaleźć liczby całkowite lfi. ri spełniające równości aj

= qi D

+ 'i,

O···(1-ax,,)= I+Aa. gdzie A jest pewną liczbą całkowitą. Jeśli liczba naturalna h dzieli zarówno a, jak i al a2 ... a". lo dzieli lewą stronę oSlatniej równości. a więc musi dzielić i prawą. co jest wszakże możliwe jedynie w przypadku b = l. D WNIOSEK 4. Jeśli liczb)' al, .... a" E Z sq IJarami względnie pierwsze i wszystkie dzieIq liczbę

a. to iloczyn

(I

I (/2 ...

a" dzieli

(I.

Dowód: Pokażemy przez indukcję. że dla k = 1.2, ... , /I iloczyn (/1(/2' •. ak dzieli a. W przypadku k = l 10 jest jasne. przyjmijmy więc. że dla pewnego k > l mamy 0la2" ·ada. Wtedy. przy odpowiedniej liczbie całkowitej b, liczba ak+1 dzieli iloczyn

22

1. Podstawowe pojęcia

a = ata2'" alb. Poprzedni wniosek pokazuje, że (aHI, t/la2 ... ak) = l i, korzystając z wniosku 2, otrzymujemy ak+db = a/ala2" ·ak. Istnieje zatem liczba całkowita c taka. że aHlc = a/alil2'" ak. a zatem alil2'" tlkaHIC = a, tj. ala2" ·tlk+lla. D

7. Znajdowanie największego wspólnego dzielnika pary liczb poprzez szukanie ich dzielników może być, przy większych liczbach. czynnością nader wyczerpującą. Znacznie lepszym sposobem jest metoda opisana w siódmej księdze Elementów Euklidesa, z tego powodu znana pod nazwą algofylmu Euklidesa. którą teraz opiszemy. Jeśli a > b są danymi liczbami naturalnymi, to zdefiniujemy ciągi f -I. fO, fI, ... oraz ql. q2, ... w sposób następujący: kładziemy f_l = a. fO = b. a jeśli dla pewnego k > O mamy już określone liczby f_l. '0, fI, ... , 'k, a prty lym 'k > O, to wyznaczamy f HI l th+! przez fk_1 = ql+I'k

+ 'HI

(O < f HI < fd·

(1.5)

(Z twierdzenia 1.2 (ii) wynika. że w ten sposób liczby f Hl i ąHI są wyznaczone jednoznacznie). W szczególności mamy a = ąlb +fl i b = ą2fl +f2. Ponieważ ciąg fi jest malejący, zatem przy pewnym n otrzymujemy rll_1 > O, r" = O. TWIERDZENIE 1.7. Jdli ciąg ' i jeJI zdefilliowany przez (l.5). a

/I

je.ft najwcześniej.fzym

indeksem, dla którego f" = O, to (a,b)=rll_l.

Dowód: Pokażemy przez indukcję, że f,,_1 dzieli 'j dla j = 11,11 - I ..... l, 0.-1. W istocie, f"_IIO = fil i fll_drll_l, a jeśli r,,_1 dzieli f1+1 i fk, to wobcc (1.5) dzieli także rl:_l.

Prosta indukcja pokazuje, że r _l jest wspólnym dzielnikiem {/ i b, a więc 0< rll_1 < (a, b). Teraz pokażemy, że (a. b) dzieli wszystkie wyrazy ciągu 'k. W istocie (tl. b) dzieli r _I = a i ro = b, a jeśli dzieli rl:_1 i 'b to wobec (1.5) dzieli także fk+l. Zatem (a, b) dzieli f,,_I. co prowadzi do (a. b) < f,,_1 i ostatecznie otrzymujemy (a. b) = f,,_I' D ll

algorytmu Euklidesa jest konieczność wielokrotnego wykonywania dzielenia z resztą, co dla dużych liczb może być czasochłonne. Podamy teraz inny sposób znajdowania największego wspólnego dzielnika, zaproponowany w 1962 r. przez R. Silvera i J. Terziana. nie mający tej wady. Stosuje on jedynie odejmowanie i dzielenie przez 2. a w wiciu przypadkach jest szybszy od algorytmu Euklidesa. Algorytm ten nazywa się Wadą

binarnym algofytmem znajdowania największego WSfJ61ncgo dzielnika. Pomysł

jest bardzo prosty: jeśli liczby a, h są obie parzyste. to zastępujemy a przez a/2 i b przez b/Z, zapamiętując wspólny czynnik 2; jeżeli dokładnie jedna z tych liczb jest parzysta. 10 dzielimy ją przez 2. nie zmieniając drugiej. Jeśli wreszcie obie są niepar,.o;yste i różne, to odejmujemy mniejszą od większej, a mniejszą zostawiamy bez zmiany. Następnie powtarzamy te czynności. Czytelnik sprawdzi bez trudu, że przy tej procedurze iloczyn (a. b) przez iloczyn pamiętanych dwójek nic ulega zmianie, a ponieważ mniejsza z liczb stale się zmniejsza. więc po pewnym czasie algorytm musi doprowadzić do a = b lub min {a. hl = l, co oczywiście wyznacza szukany największy wspólny dzielnik.

1.1. Podzielność, liczby pierwsze

23

Procedurę tę można

nieco przyspieszyć, jeśli w przypadku nieparzystych (j, b o dużej różnicy, zamiast brania różnicy wykonamy dzielenie z resztą. Obliczając tym sposobem na przykład największy wspólny dzielnik liczb 23458 i 1235. otrzymujemy

23458

1235

11729

1235

i tu, zamiast odejmowania, wykonujemy dzielenie z

1235

614

1235

307

928

307

resztą,

eo prowadzi do pary

i dalej mamy:

464 307 232

307

116 307 58 307 29 307 29

17 = 307 - 10 . 29.

widzimy, że szukany NWD jest równy jedności. Analizę algorytmów Euklidesa i binarnego można znaleźć w II tomie książki D. Knutha [l]. a niedawno B. Vallee II J pokazała. że średnia liczba kroków w algorytmie binarnym dla nieparzystych liczb a. b < N jest równa w pr.t.ybliieniu c log N z pewną dodatnią stałą c.

a tu

już

,

Cwiczenia I. Niech Pn oznacza

(i)

/l-tą liczbę pierwszą.

Udowodnić. że

.-.

lim sUP(P"+1 - p") = 00 .

(ii)

Udowodnić nierówność

Pn < e l +"

2. (i) (ii)

Pokazać. że jeśli

Pokazać. że jeśli

2n

2" -

+ [ jest l jest

(11 = [.2 ....). liczbą pierwszą,

liczbą pierwszą.

to

to II

11

jest

jest

potęgą

liczby 2.

też Iil:zbą pierwszą.

IS(l~ ~J-1)1-14(l15·1.

" by

W~

PWN 2\lOJ

24 1. Podstowowe

pojęcia

3. Udowodnić, że jeśli zmodyfikujemy algorytm Euklidesa. biorąc zamiast najmniejszej nieujemnej reszty resztę o najmniejszej bezwzględnej wartości, to teza twierdzenia 1.7 pozostanie nie zmieniona. 4. Niech Un oznacza II-Iy wyraz ciqgll Fihollacciego zdefiniowanego wzorami 1/1

(i)

=

/12

Udowodnić, że

= 1.

/1"+1

(u ... u") =

=

/I"

u(..."\

+ 1/"_1 i

(11 = 2. 3." ,),

wykorzystać

to do dowodu istnienia

nieskończenie

wielu liczb pierwszych. (ii) Udowodnić, że dla II = 1.2, ... zachodzi wzór u. =

5. (i)

Pokazać. że

dla

ciągu

CI + ./5)" - CI - ./5)" 2"./5 Fibonacciego (unl zachodzi

nierówność

ldu n (11= 2. 3, ... : I = 1.2....). (ii) Wykorzystać (i) do pokazania, że jeśli m < /l. to liczba kroków walgorytmie Euklidesa zastosowanego do pary a. h (gdzie a = /I ... b = un) nie przekracza 5r. gdzie r jest ilością cyfr liczby a w zapisie dziesiętnym. (iii) (Lamć [I)) Pokazać. że wynik (ii) jest słuszny dla dowolnych liczb naturalnych (l < b, U"+5I

>

6. Wykorzystać metodę pierwszego dowodu twierdzenia lA do pokazania. że istnieje nieskończenie wiele liczb pierwszych zarówno w postępie arytmetycznym 411 - I. jak i w postępie 611 - I.

1.2.

Jednoznaczność rozkładu

na czynniki pierwsze

I. Jednym z podstawowych rezultatów elementarnej teorii liczb jest twierdzenie o jednoznaczności rozkładu liczb naturalnych na czynniki pierwsze, które teraz przedslawimy: TWIERDZENIE 1.8. Każdą liczbę naturalną n > 1 !/Iożna przedstawić jednoznacznie

w po-

staci (1.6)

II=PI"'Pk,

przy czym Pl < P2 < ... < Pk dzielnik pierwszy liczby II.

są

liczbami pierwszymi,

Wśród

liczb Pi

wystąpi

kaidy

Dowód; Istnienie takiego przedstawienia jest zawarte w lwierdzeniu 1.3, Pozostaje zatem wykazanie jedyności. Zastosujemy tu indukcję. Dla liczby fi = 2 leza twierdzenia jest oczywista. Przypuśćmy, ze twierdzenie jest fałszywe i niech N będzie najmniejszą liczbę naturalną, mającą dwa rMne rozkłady (1.6), powiedzmy

N = PIP2' ,. pr

=Qlą2'·'ą.,

ISB~ ~HlI-14(l15-1.

o by W~ PWN 2\lOJ

1.2. jednoznaczność rozkładu na czynniki pierwsze

25

gdzie PI < P2 < ... < p, i ąl < ą2 < ... < tj, są liczbami pierwszymi. Z wniosku 4 z twierdzenia 1.2 otrzymujemy. że prą pewnym j liczba Pl dzieli ąj. a więc ąj = PI' Widzimy teraz, że liczba N/PI = P2'" p, =qlą2" 'qj-lqj+I" . q..

jest mniejsza od N i ma dwa różne rozkłady. wbrew wyborowi N. By udowodnić drugą część tezy twierdzenia. zauważmy, że jeśli (1.6) jest jedynym rozkładem n na czynniki pierwsze oraz P jest liczbą pierwszą, dzielącą //, to rozkładając iloraz n/ P na czynniki pierwsze. n/ P = ql ... ą, Geśli n/ P = l, to nie ma czego dowodzić). otrzymujemy

// = a zatem liczba P musi

pąl

wystąpić wśród

"'q,

= Pl ···/h·

liczb Pi. D

Wiele innych dowodów tego twierdzenia można znaleźć w książce P. Ribenboima [2]. Teraz możemy precyzyjniej sformułować wniosek 2 z twierdzenia 1.3: WNIOSEK l. Każdą liczbę nall/mlną fl > l można zapisać jednoznacznie w postad

,

n =

n "·

Pj'

1=1

przy czym r jest iloJcią rożnych dZielników pierwszych liczby //. PI < Pl < ... < P, liczbami pierwszymi. aj zaś sq liczbami natum///)'mi.

są

Dowód: Wynika z twierdzenia przez pogrupowanie jednakowych czynników pierwszych. D WNIOSEK 2.

Każdą liczbę całkowitą

n

=1=

O. ± I

mOŻl/a zapisać

,

n = sgn //

n

jednoznacznie w postaci

I)~i •

i= l

przy czym r > J. Pl < Pl < ... < p, sq liczbami ,)ienvsz)'mi. I/alumlnymi.

Dowód: Wystarczy

zastosować

poprzedni wniosek do liczby

WNIOSEK 3. Każdą liczbę calkowi/q " =1=

n=

E

O można

n

zapi.mć

aj

zaś

sq liczbami

n/ sgn n = 1111. D

jedllovwcznie w postaci

pa p (").

pEl'

przy czym E = ± I. ap(n) E No. czynników różnych od jed//oJci.

Dowód: Dla

WysfęplljqCy tli

ilocz)'1l zawiera jedynie skOJlczellie wiele

= ±l przyjmujemy ap(n) = O dla wszystkich p. Jeśli zaś n ma postać występującą w poprzednim wniosku. to dla P = Pi (i = 1.2..... r) przyjmujemy ap('l) = aj, a dla pozostałych liczb pierwszych P kładziemy op(n) = O. Jednoznaczność II

przedstawienia wynika

bezpośrednio

z poprzedniego wniosku. D

IS(l~ ~J-1)1-14(l15·1.

" by

W~

PWN 2\lOJ

26 l. Podstawowe

pojęcia

WNIOSEK 4. KaŻl/ą liczhę wymlernq

w

różną

od zera /Iloma

zapisać

jedllovwcVlie

w lJOstaci

przy czym fe = ± I. lip (w) E Z. Występujący czy"ników różnydIod jedno.l'ci.

iloczyn zawiera jedynie skOllczenie wiele

tli

Dowód: Wystarczy rozpatrzyć prLypadek, gdy w > O. Napiszmy w = a/h, przy czym a i b są liczbami naturalnymi. Korzystając z wniosku I, otrzymujemy

w=

n

p"p(a)~"p(b).

pĘI'

możemy więc przyjąć

lip(W) = lip (a) - lip(b). Zauważmy. że różnica lip (a) - li/,(b) zależy jedynie od liczby w, a nie od wyboru a, b. W istocie, jeśli w = c/d przy naturalnych c, d, to ad = be i, korzystając z wniosku I. otrzymujemy równość

n

p"p(a)+ap(d)

=

pEl'

n

p"p(b)+"p(C).

pEl'

Z tegoż wniosku wynika teraz Op(b) +ap(c) = op(a) + al,(d), a więc op(a) - al,(b) = ap(c) - op(d). Pozostaje pokazać. że każde przedstawienie liczby w w postaci

w=

n

pC

p

,eP

przy

cI'

E Z powstaje w

powyższy

sposób. ale to wynika z uwagi,

c=npC

p

d ~

n

,eP

,cP

Cp>O

cp {3. W przypadku ogólnym napiszmy v = alb, w = cld (a. b. c. d E Z, a =1= O. c =1= O i v + w =1= O, względnie v =1= w). Wówczas mamy ad ± he v ± UJ = ---cc-;-bd i, korzystając z (i) i już udowodnionej dla liczb całkowitych części (iv), otrzymujemy a,,(v

± w)

= ap(ad

± be) -

> min{ap(a)

((,,(bd)

+ a,,(d), a p (b)

- ((p(c)} - ((,,(b) - ((,,(d)

= minla,,(a) - a,,(b). Cip (c) - Cip(d)} = min{Ci,,(v), Ci,,(W)}. Jeśli

strony

Cip (v) < Cip (w), to przede wszystkim mamy Cip (v

±

w) > Ci,,(V). z drugiej zaś

możemy napisać

a,,(u) = Ci,,(U ± w =f w) > min{a,,(u ± w). al,(w».

a

ponieważ nierówność

WNIOSEK l. JeJJj a. h

dla

każdej

((,,(v) > ((,,(w) jest wykluczona, prl.:eto ((,,(v)

sq liczbami

całkowitymi,

=

((,,(v

±

w), O

to a dzieli b wtedy i tylko wtedy, gdy

liczby pierwszej p mamy ((r(a) < ((,,(b).

Dowód: Wynika z (i) i (ii). O

Liczby

całkowite II, spełniające

nazywają się żaden

dla

każdej

liczbami bezkwadmlOw}'mi.

Są

liczby pierwszej p warunek ((,,(n) < l, to zatem liczby, które nie dzielą się przez

kwadrat liczby naturalnej> l.

WNIOSEK 2. Każda liczba /latllralna II da się jedllol)laczllie przedstawić w postaci n = ah 2, gdzie li, h są liczhami naturalnymi i a jest liczhą bezkwadratową.

Oow6d: Przyjmując za b największy kwadrat liczby naturalnej dzielący II i kła­ dąc {/ = lilIi, otrzymujemy żądane przedstawienie. Przypuśćmy teraz, że mamy II = ab 2 = olbf z bezkwadratowymi a, al i niech p będzie dowolnym dzielnikiem pierwszym

28 1. Podstawowe

pojęcia

liczby a. Z (i) wynika

+ 2a p(b)

O'p(n) = l

= O',,(ad

+ 2a p(bd.

a więc O'p(al) jest liczbą nieparLystą i widzimy, że p dzieli al, Zatem każdy dzielnik pierwszy a dzieli aj i, zamieniając rolami a i aj, otrzymujemy, że a i al mają te same dzielniki pierwsze. Ponieważ obie te liczby są bezkwadratowe. przeto muszą być równe. a wtedy otrzymujemy b = hl, D WNIOSEK 3. (i) Liczba wymierna n jest k-tą potęgą pewnej liczby wymiernej wtedy i tylko

wtedy. gdy dla kaidej liczby pierwszej p mamy kIO'p(II). m, /I są względnie pierwszymi liczbami /lall/ralnymi. kt6rych iloczyn jest k-tą potrgą liczby naturalnej. 10 kaida z liczb m. " też je.l·t taką potęgą. Jdli za.\" k jest liczbą nieparzystą, to teza ta zachodzi także dla względnie pierwszych liczb m. n (ii)

Jeśli

całkowitych.

(Hi) Jdli przy pewnym naturalnym k liczba C(ltkowiw k-tą potęgą

liczby wymiernej. to jest ona że

liczby

11

jest

k-tą potęgą

pewnej

całkowitej.

Dowód: (i) jest konsekwencją części (i) twierdzenia. By udowodnić (ii), zauważmy, jeśli p jest liczbą pierwszą, dzielącą jedną z liczb III. n, to nie może ona dzielić

drugiej. a zatem ap(m/f) = O'p(m) lub O'p(mll) = O'p(n) i pozostaje skorzystać z ostatniej równoki w części (i) twierdzenia. W przypadku 2ik i całkowitych 11/. II wystarczy dodatkowo zauważyć. że - l = (- l)k. Wreszcie (iii) wynika z (i) i uwagi. że O' ,,(n) > Q pociąga za sobą O'p(n)/k > Q. D WNIOSEK 4. Dla każdej liczby pierwszej p i n = 1.2, ... mamy

",,(n')

~

f [",].

k=1

P

Dowód: Wobec (i) mamy "

00

.,,(n') ~ La,,(k) ~ L L k=l

ale

L

k::o" a,(k)=j

a,,(n ')

~

L

,~

k::o" l"

k::on a,{kl=j

L l::o,,/p'

I"

~~j

j=1

l.

pll

([

;1]- [p;~, ])

~ fj ['p7] - fu - I) [:1] j=1

)=2

l

" ,,"'1.'_"""" hu"" '".b, ISB~ ~J-1)1-I4(l1

S-I. " by

\ol ......" .

W~

"00'

PWN 2\lOJ

1.2. Jednoznaczność rozkładu na czynniki pierwsze

29

nazywamy wykładnikiem odpowiadąjącym liczbic picrwszcj p. Moż~ na pokazać (Ostrowski [l]), że jeśli I (x) jest funkcją o wartościach calkowitych, określoną dla niezerowych liczb wymiernych i spełniającą warunki (i) i (iv) twierdzenia 1.9, to istnieje liczba pierwsza p i stała c taka, że I(x) = cap(x). Warto zwrócić uwagę na fakt, ze w pewnych podzbiorach zbioru liczb naturalnych, zamkniętych na mnożenie. może nie być jednoznaczności rozkładu na czynniki nierozkładalne, a więc nie jest tam słuszny analogon twierdzenia 1.8. W istocie, rozpatrzmy zbiór A złożony ze wszystkich liczb naturalnych postaci 4n + I (n = O. L 2....). Jest on zamknięty na mnożenie ze względu na (4111 + 1)(4/1 + l) = 4(4mll + m + II) + I. Liczbę n E A nazwijmy pierwszą w A, jeśli nie można jej przedstawić w postaci iloczynu różnych od jedności elementów A. I lak na przykład liczby 5.9,13,17,21. 33 i 37 są pierwsze w A, natomiast 25 nie, bo 25 = 5·5 i 5 E A. Nictrudno pokazać, że każda liczba z A, różna od jedności, da się przedstawić jako iloczyn liczb pierwszych w A. Jednakże przedstawienie to może nie być jednoznaczne, gdyż na przykład liczba 693 ma dwa rozkłady: 693 21 ·33 9·77. Zagadnienie jednoznaczności rozkładu w zbiorach tego typu było badane w pracach: Niven, James II], Schreiber II]. Funkcję a p (II)

=

3,

=

z wprowadzonych funkcji a p (II), udowodnimy tcraz kilka wspólnego dzielnika i najmniejszej wspólnej wielokrotności:

Korzystając

największego

własności

TWIERDZENIE 1.10. Niech al. a2, ... , a" będą lIiezerowymi liczbami ClIlkowi/ymi.

(i) JCoI'/i d = (al. a2"'" a n ),

/0

dla

każdej

liczby pienv.\'zej plIWIlly

ap(d) = min{a,,(ad. a p(a2) ..... ap(n)J.

(ii) JCoI'Ii D = [al, a2, .... a li ]. to dJa każdej liczby pierll'.fzej p mallly a,,(D) = max{ap(ad, af!(a2),

(iii) JCoI'Ii Nlai dla i = 1.2

, II.

/o

NI(al.

(/2

, af!(II)}.

an ).

(iv) JCoI'li a,iN dla i = 1,2 , II, /0 [al,a2,'" ,a"lIN. (v) Jeśli a, b są liczbami lIa/uralnymi. /0 «(I, b)[a, bl = ab. Dowód: Niech I)

= n"El'pcF, gdzie cr = min{af!(a;):

= J,2, ... ,nj.

Wobec wniosku l z twierdzenia 1.9 D dzieli każdą z liczb ai. a zatem O < D 2, to korzystając z twierdzenia 2.6, otrzymamy i prosta indukcja pokazuje złożoną, to wystarczy teraz

słuszność

wniosku w tym przypadku. zastosować wzór (2.7). D

Jeśli

N jest

liczbą

Dla danego wielomianu F[X] E Z[Xj i liczby naturalnej N oznaczmy przez iF(N) liczbę tych a mod N, dla których kongruencja F(x) = a (mod N) jest rozwiązalna. Dla późniejszego zastosowania przyda się nam następujący rezultat: WNIOSEK 4. Jeżeli p jest liczbą pierwszą. F(X) E Z[XJ, k > l oraz iF(pk+l) = pi FUl), /O Z rozwiązalności kongruencji

wynika

rozwiązalność kongruencji

F(x)

=a

(mod pk+l).

Dowód: Niech r = i FCpk) i niech {F(a) mod pk: a =0, I, ... , ,l- II = {a],a2, ... ,arl

oraz IF(b)mod ,/+1: b=0.1, ... ,,l+I-I}=lb l ,b2, ... ,bs l.

przy czym s = pl". Oczywiście mamy przy tym hi = aj, + tipk (mod pHI) przy odpowiednim wyborze l < ji < r oraz O < ti < p - l. Dla ustalonego m < I" oznaczmy przez s(m) liczbę tych indeksów i, dla których zachodzi równość ji = m. Wówczas mamy L:.:'=l(P - s(m» = pl" - .\' = O, ale z ostatniej części twierdzenia wynika nierówność O < s(m) < p i widzimy, że dla każdego 11/ mamy .1'(11I) = p. W szczególności każda reszta mod pHI przystająca do któregoś ai mad pl: okazuje się jedną z reszt b i . O 4, Istnieją oszacowania wielkości AFCpk) zależne od wyróżnika wielomianu F. Za-

nim udowodnimy takie oszacowanie, omówimy podstawowe różnik wielomianu II-tego stopnia F(X) =a"X"

"

własności wyróżnika.

+ ... +ao =a" n(X -Zj) j=1

Wy-

(2.11)

W.

I\.u", Ó + l będzie t > (k + 1)/2. Rozpatrzmy kongruencje

I

>

oraz (2.12)

Z wniosku z lematu 2.5 wynika, F(a)

że są

one

równoważne

kongruencjom

+ pl F'(a)x = O (mad pr)

z r = k, względnie r = l + k. Widzimy zatem, że pierwsza z nich jest spełniona dla wszystkich wartości x, więc ma pk rozwiązań mod ,l. druga zaś. po podzieleniu przez pk, na podstawie twierdzenia 2.1 (iv) przybiera postać F(a)

F'(a)

'--':,"+ p". p"

t

x

=

O (mod p).

48 2. Kongruencie Ta ostatnia kongruencja ma dokładnie jedno rozwiązanie mod p, ponieważ F'(a)p,-k jest liczbą całkowitą i nie podzielną przez p; widzimy więc, że zbiór rozwiązań kongruencji (2.12) wypełnia dokładnie jedną klasę reszt mod p. a zatem kongruencja ta ma li rozwiązań mod pk+l. Ostatecznie widzimy, że kongruencje F(x)

= O (mod pk)

mają

tyle samo rozwiązań leżących w zadanej klasie reszt mod p'. Przeto dla k > ó liczba Af"{Jl) nie zależy od k, a zatem, korzystając z wniosku 3 z twierdzenia 2.6, otrzymujemy

Praca Sandora zawiera także nieco mocniejsze oszacowanie w przypadku k . .. a mIanOWICIe (Patrz także Huxley [I D. Najmocniejsze ze znanych oszacowań tego typu c.L. Stewart ([ll. [2]):

podał

> I +ó,

niedawno

wielomian F E Z[X] stopnia k jest nieprzywiedlny nad ciałem liczb wymiernych, \O dla nieskończenie wielu liczb pierwszych p zachodzi równość Ał'(P) = k. Dowodzi się tego zazwyczaj przy użyciu teorii liczb algebraicznych, ale I. Gerst i J. Brillhart [II pokazali, że można to uczynić, korzystając wyłącznie z prostych faktów z teorii ciał. Udowodnimy teraz pewien słabszy wynik, posługując się jedynie elementarnymi środkami:

6.

Można udowodnić. że jeśli

TWIERDZENIE 2.9. Jeżeli F(X) jesT wielomianem sTOpnia dodatniego o całkowiTych współczynnikach.

to dla nie.l·kUliczenie wie/II liczb pienv.\·z)'ch mamy AF(P) > O.

Dowód: (według L Schura [I J). Jeżeli F(O) = O, to oczywiście dla każdej liczby pierwszej p mamy AF(p) > O. Niech zatem F(O) = a =1= O. Przypuśćmy teraz. że jedynie dla liczb pierwszych PI. P2, .... Pr mamy AF(P) > O. Oznaczmy przez A ich iloczyn i rozpatrzmy wielomian G(X) = F(aAX)/a. Ma on współczynniki całkowite,

które z

wyrazu wolnego, równego l, całkowitego x mamy

wyjątkiem

każdego

G(x) = l (mad p,) Jeżeli

dzielą się

wszystkie przez A, a więc dla

(i=1.2, ... ,r).

p jest liczbą pierwszą, a liczba b spełnia G(h)

= O (mod p),

(2.13)

to

F(aAh) = aG(b) = O (mad p),

a więc p jest jedną z liczb Pi. co jest sprzeczne z (2. ł 3). Widzimy więc. ze dla kazdej liczby pierwszej P mamy ).,c(p) = O, a więc C(X) może przyjmować dla całkowitych argumentów jedynie wartości O, l i -l. Zatem G(X) musi być wielomianem stałym, a to oznacza. że F(X) jest też wielomianem stałym. wbrew założeniu. O

IS(l~ ~J-1)1-14(l15·1.

" by

W~

PWN 2\lOJ

2.1. Podstawowe

własności

Ćwiczenia I.

Udowodnić.

ze

jeżeli p

liczbą pierwszą.

> 2 jest

==

I

x p-

to kongruencja

I (mod p")

ma prLy każdym II > l dokładnie p - I rozwiązań. 2. (i) (Twierdzenie Wilsona) Udowodnić, że jeżeli p jest

liczbą pierwszą. to

(p - l)! = -l (modp).

(ii) (Lagrange)

Pokazać, że jeśli

(11 - l)! - -I (modli),

jest liczb~l pierwszą. 3. (i) Udowodnić. że dla nieskończenie wielu liczb 11 liczba II! + l jest złożona. (H) Udowodnić, że dla nieskończenie wielu liczb II liczba II! - l jest złożona. 4. (Hurwitz) Niech p będzie nieparLystą liczbą pierwszą i niech rl. rl, .... rp oraz s" Sl •...• sp będą pełnymi układami reszt mod p. Pokazać. że układ lo

11

nie jest

pełnym układem

5. (Clement [I ])

reszt mod p.

Pokazać. że

na lO. by liczby

/I

> I i

11

+ 2 byly obie pierwsze.

potrzeba i wystarcza. by 4«11 - l)!

+ I) = -11

6. Nieeh Ul = 2 < I/l < ... bczkwadratowych. Pokazać. że

(mod//(n

będzie ciągiem

.

\im sUP(U'-ł-1 - lin)

+ 2)).

wszystkich naturalnych liczb

= 00•

-~

7, Niech F(X) będzie wielomianem o całkowitych współczynnikach. (i) Pokazać, że dla każdej liczby całkowitej a liczba ptl(a)

k' jest przy k = 1.2.... liczbą całkowitą. Oi) Pokazać. że jeśli x - Xo (mod N). to dla k = F(x) = F(xo)

, xo)F (xo)

+ (.r -

+(x-xol

ptl(a)

L:;':':

kl

+ (x

ł.

- xo/

2.... mamy F(2)(a)

2!

+ ...

(modNk+I).

8. Niech F(X) = x" + (Ii Xi E Z[Xl i niech p będzie liczbą pierwszą. Pokazać, że kongruencja F(x) _ O (mod p) ma pierwiastek wielokrotny wtedy i tylko wtedy. gdy wyróżnik wielomianu F dzieli się przez p.

49

50 2. Kongruencie

9. Niech F(X) będzie wielomianem kwadratowym z nieznikającym wyróżni­ kiem. (i) Pokazać. że dla nieskończenie wielu liczb pierwszych p zachodzi równość "'-Ap) = 2. (ii) Pokazać, że istnieje nieskończenie wiele liczb pierwszych p. dla których mamy ),Ap) = O. (iii) Pokazać. że równość AF(P) = I może zajść jedynie dla skończenie wielu liczb pierwszych p.

2.2. Reszty

pierwsze z

modułem

reszt mod N, zawierającą liczbę m względnie pierwszą z N. to każda liczba III I leżąca w II jest również względnie pierwsza z N. W istocie, w prleciwnym razie istniałby dzielnik d > l liczby N. dzielący mi. a wówczas mielibyśmy dlNlm - mj. a zatem dl'" i l < dl(m. N). co jest niemozliwe. Każdą taką resztę II będziemy nazywać resztą mad N względnie pierwszą z N. Zbiór wszystkich takich reszt oznaczamy przez G(N). Liczbę elementów zbioru G(N) oznacza się przez ip(N). Zdefiniowaną w ten sposób funkcję nazywamy fimkcją Elliera. Jeśli p jest liczbą pierwszą. to oczywiście ip(p) = p - I, gdyż kaida niezerowa reszta należy do G(p). Dla potęg liczb pierwszych zachodzi wzór

l.

Jeżeli II

względnie jest

klasą

(k ~ gdyż zbiorem reprezentantów dla G(pt) jest zbiór

//- L n::"cp'

elementów.

,'"

1= pt -

L

1=

1.2.... ).

li 3 grupa G(2 3 ) jest obrazem homomorl1cznym grupy G(Z") przez odwzorowanie 0/8.2"' przeto grupa G(2") nie może być cykliczna. By udowodnić, że jest ona postaci C2 ffi C2"-" zauważmy przede wszystkim. że 5 mod 2" ma w grupie G(2") rząd równy 2,,-2. Rzeczywiście, mamy

1/

i ogólnie 52' = 1

+ 2 H2 + akZk+3

(ak E Z),

a zatem przy k < /I - 3 jest 52' "1= I (mod 2n ). Oznaczmy przez G I podgrupę cykliczną grupy G(Z") generowaną przez 5, a przez G2 podgrupę dwuelementową, generowaną przez 2" - ł. Ponieważ jedynym wspólnym elementem tych podgrup jest I mod 2". zatem G(Z") zawiera sumę proslą Gl EEl G2. Ze względu na #GI = 2"-2, #G2 = 2 i G(2") = 2"-1 otrzymujemy #G(2") = #G I . #G 2, a więc G(n) = Gl E9 Gl. W pozostałym przypadku (n > 2. p nieparzyste) potrzebny nam będzie prosty lemat o współczynnikach dwumianu Newtona:

p jest liczbą pierwszą. to dla j = 1.2, ... , p - I dzieli się przez p.

LEMAT 2,14, Jeśli

1011mvski

e)

współczynnik

new-

Dowód: W wyraieniu

J.) ~ ~P'--cc j!(p-j)!

(p

licznik dzieli

się

przez p. a mianownik nic. O

WNIOSEK. Jeśli p jeslliczbą pierwszą oraz a, b E Z. to dla k = I. Z., .. mamy

,

,

,

(a +h)f' = al' +hf' (modp). Dowód: Dla k

= l wynika to

nietrudną indukcję.

bezpośrednio

z lematu, a dla

większych

k stosujemy

D

Niech g mod p będzie generatorem grupy G(p). Generatora grupy G(p") szukać wśród elementów postaci

będzicmy

~=g+tp(modp")

przy t = O. I..... p - I. Oznaczmy przez r ~r

= (g

rząd

+ tpY =

elementu

l (mod p"),

~

w grupie G(p"). Wówczas

56

a

2. Kongruencje

WięC

gr _ (g

+ tp)'

_ l (mod p),

przeto r dzieli się przez rząd g mad p, równy p - I, Z drugiej strony, r jest dzielnikiem #G(p") = rp(p") = p"-I (p_ I), lak więc przy pcwnym j z przcdziału [O, fl - I] mamy r = pj (p - 1). Pokażemy, że jeśli t będzie tak wybrane, by spełniony był warunek (2.18) 10 j będzie równe

/I -

grupy G(p"). W istocie,

zachodzi (2.18), to

a

stąd dzięki

jeśli

I, a więc będziemy mieli r = rp(p")

lematowi 2,14 oraz

nietrudną indukcję

nieparzystości

że

będzie

generatorem

p otrzymujemy (pł0 2)

dochodzimy do

(g+tp)"!(p-Il = I +aj+lpj+l dlaj=I.2,.,. Widzimy więc,

g

możemy napisać

(g+tp)p(p-ll=(l+OIP)P=1+a2p 2 i przez

I

przy j
l miala {,iawiostek pierwotlly, potrzeba i wystarcza.

aby N była poręgą liczby {)ie/wszej Ilieparzysrej lub {JOdwojeniem takiej potęgi. jednq Z liczb 2, 4.

bądź reż

Dowód: Załóżmy, że N ma pierwiastek pierwotny. Ponieważ suma prosta grup cyklicznych jest cykliczna dokładnie wtedy, gdy jej składniki mają rzędy parami względnie

ISB~ ~HlI-I4(l15-1.

o by W~

PWN 2\lOJ

2.2. Reszty względnie pierwsze z modulem

57

nI'

pierwsze, zatem z wniosku 3 z twierdzenia 2.1 I wynika. że jeśli N = p"" jest kanonicznym rozkładem liczby N, to grupa G(N) jest cykliczna wtedy i tylko wtedy, gdy wszystkie grupy G(p"'r) są cykliczne i mają rzędy parami względnie pierwsze. Ponieważ dla p > 2 mamy 21#G(p"") i ten sam warunek jest spełniony dla p = 2 w przypadku Cl" > 2. zatem N może mieć co najwyżej jeden nieparzysty dzielnik pierwszy i nie może się dzielić przez 4. Widzimy więc, że N jest jedną z liczb wymienionych w sformuło­ wanym wniosku. Pozostaje pokazać, że liczby postaci N = 2 p " (p> 2) mają pierwiastki pierwotne, ale to wynika z wniosku 4 z twierdzenia 2.1 I. D WNIOSEK 2. Jdli liczba N ma pierwiastki pierwotne. to ma ich I{!(I{!(N».

Dowód: Wynika z prostego faktu. że jeśli G jest m-e1emelllową grupą cykliczną, to ma ona I{!(m) generatorów. W istocie, jeśli g jest generatorem G, to h = ga (I O. Wiadomo też, że dla nieskończenie wielu p mamy rep) < 5 (Heath~Brown [l]). Z drugiej strony wiadomo (Graham, Ringrose [l]). że oszacowa~ nie rep) = D (log p log lag log p) nie jest prawdziwe. Przypuszcza się. że najlepszym oszacowaniem jest r(p) = o (log2 p), które można wyprowadzić z pewnych nie udowodnionych dotąd hipotez (Bach [I D. dla

każdego tO

Ćwiczenia ł. Wyznaczyć

pierwiastki pierwotne dla wszystkich liczb pierwszych p < 20

i ich kwadratów. 2. Dla liczby pierwszej p,

różnej

od 2 i 5 oznaczmy przez a(p) długość okresu

rozwinięcia dziesiętnego

liczby l/p. (a) Pokazać. że IO"IP) == 1 (mot! 10). (b) Pokazać. że jeśli II :> 1 i 10" = l (mod p). lO n dzieli się przez a(p). (c) Udowodnić. że a(p) < p - I, a równość zachodzi tutaj wledy i tylko wtedy. gdy 10 jest pierwiastkiem pierwotnym mod p. (d) Znałe.i.ć a(101). a(257). (1(9901). a(65537). 3.

jest

Pokazać. że

kongruencja 2 P- 1 - I (mod pZ)

spełniona

dla liczb 1093 i 3511. (Uwaga: nic są znane żadne inne liczby pierwsze

spełniające tę kongruencję).

ISB~ ~J-1)I-14(l15-1.

" by

W~

PWN 2\lOl

58 2. Kongruencje

4. (i) Sprawdzić. i:e liczby 645 i I09Y są liczbami pseudopierwszymi. (ii) Pokazać, i:e jeśli N jcst liczbą pscudopicrwszą. to 2"" - I tci:. (iii) Pokazać. że 341 jest naj mniejszą liczbą pseudopierwszą. (iv) Znaleźć warunek konieczny i doslateczny na 10, by kwadrat liczby pierwszej p

był liczbą pseudopierwszą.

5. (i) Udowodnić. że liczby 1729 i 294409 są liczbami Carmichaela. (ii) Pokazać, że na to, by N było liczbą Carmichaela. potrzeba i wystarcza, by N było liczbą bezkwadratową i aby dla każdej liczby pierwszej plN zachodził warunek p-liN-l. (iii) Pokazać. że liczby Carmichaela muszą mieć przynajmniej trzy różne dzielniki pierwsze. (iv) Sprawdzić, że 561 jest najmniejszą liczbą Carmichaela. 6. (Gauss [l])

Pokazać. że

gdy N ma pierwiastki pierwotne. . . w przeciwnym raZlc.

2.3. Kongruencje kwadratowe I. Zajmiemy

się

teraz

rozwiązywaniem

kongruencji kwadratowych. Niech

F(X) = aX 2

+ bX + c

będzie

wielomianem o współczynnikach całkowitych. o których możemy za/ożyć. bez ograniczenia ogólności, że spełniają warunek (a. h. c) = I. Niech ..1 = hl - 4ac bę­ dzie wyróżnikiem F i niech p" (II > I) będzie potęgą liczby pierwszej p. Będziemy rozpatrywali kongruencję (2.19) zakładając. że p"ła. jeśli

bowiem warunek ten nie jest spełniony. to (2.19) staje się kongruencją liniową. a ten przypadek rozpatrzyliśmy w poprzednim rozdziale. Na początek pokażemy. że można sprowadzić badanie kongruencji (2.19) do badania układu złożonego z kongruencji liniowej i kongruencji kwadratowej dwumiennej. LEMAT 2.15. Jeśli p"ła. 10 kOl1grueflLjll (2.19) ma rozwiązanie wledy i tylko wtedy. gdy układ

kOllgruencji

.

.

ma rozwlqwme.

2ax

l = ..1

(mod 4al)")

+ h =Y

(mod 4ap")

2.3. Kongruencje kwadratowe

Dowód: Ze

względu

na

59

tożsamość

4aF(X) = (2aX

+ b)2 -

L1

otrzymujemy. że jeśli x jest rozwiązaniem (2.19), a y = 2ax + b (mod 4a p n), to mamy i = L1 (mod4ap li). Na odwrót, jeśli uklad kongruencji podany w lemacie ma rozwią­ zanie x, y, to 4ap" dzieli 4(/ F (x), a więc F (x) = O (mod p"). D Zajmiemy się teraz rozwiązywaniem kongruencji kwadratowych dwumiennych i rozpoczniemy od przypadku, gdy I' jest liczbą pierwszą nicparzystą: TWIERDZENIE 2.16. Niech p będzie nieparzystą A =F O. PiA) i niech C(X) = X 2 - a.

ldli

pła,

li

r = O.

/o

liczbą pierwszą,

niech a = 1" A (r > O,

kOllgruellLja x 2 = (/ (mod 1''')

lila

rozwiąwnie

wtedy i tylko wtedy. gdy jest x2

Jeśli

-

rozwiązaln(/

a (mod p).

(2.20)

kongruellLja (2.21 )

warunek ten jest spe/niony, to AG (p") = 2.

pla i n I i pły. Nasza kongruencja przybiera teraz postać (2.22) /)2:; = 1'" A (mod p"). Pozostaje

zauważyć. że jeśli

x jest

rozwiązaniem

i

Jeś1 i /I

< r, to nasza kongruencja przybierze

p!s y2

postać

= O (mod p").

a zatem każda liczba podzielna przez p'" jest jej pierwiastkiem i otrzymujemy Adp") = p ,,-s. . W przypadku n > r kongruencja (2.22) jest równoważna kongruencji

p!s-'i

= A (mod/)Ii-'),

60 2. Kongruencje a zatem musimy mieć 2s = l' i )'2 - A (mod p"-'). Z udowodnionej części twierdzenia wynika, iż ta ostatnia kongruencja jest rozwiązalna wtedy i tylko wtedy, gdy rozwiązalna jest kongruencja = A (modp),

l

a jeśli lO zachodzi. to reszt mod p". D Pozostał

istnieją dokładnie

dwa

rozwiązania

mod p"-', które

dają

2p'

nam do rozpatrzenia przypadek p = 2.

TWIERDZENIE 2.17.

Niech a = 2' A (I' > O. A =1= O, 2łA) i niech C(X) = X 2 - a.

(i) W przypadku

/I

= l kongruemja G(x) - O (mod 2")

(2.23)

a w przypadku /I = 2 lila jelfno rozwiązanie. gdy 41a. dwa zaś rozwiązania, gdy 2ła, i nie ma rozwiązań, gdy 211a. (ii) D/a II = 3 kOllgruencja (2.23) ma ezlery rozwiązania, gdy a = l (mod8) lub 41a. a nie ma rozwiąZali w pozostałych przypadkach. ma jedno

(iii)

rozwiązanie,

Jeśli 11

wtedy, gdy a

=

>4 i 2ła. Ij. r = O. /O kongruencja (2.23) lila rozwiązanie wtedy i tylko l (mod 8). Jdli warullek tell jest spełlliony, to AG (2") = 4.

(iv) Je.fli" > 4 i r > l, lo w IJrzypadku r > II mamy AG (p") = 2"-"', gdzie sojest lIajmniejszą liczbą naturalną spełniającą So > /l/2. a w przypadku r < n kongruencja (2.23) ma rozwiązanie wtedy i tylko wledy, gdy l' jesl parzyste, powiedVllY r = 2.\· i rozwiązalna jest kongruencja

Jeśli

wanmki te

są spełnione, /O

2S

Adp") =

2s~l.

12s+2,

gdyr=n-I, gdy r = II - 2. gdyr r, to

kładąc

22. 2 będą liczbami pierwszymi spełniającymi p = I (modq) i niech G(p)q będzie zbiorem wszystkich q-tych potęg elementów C(p). (i) Pokazać. że C(p)~ jest podgrupą C(p) i znałeźć jej rząd. (ii) Pokazać. że grupa ilorazowa C(p)/C(p)~ jest izomorficzna z grupą A~ (I-tych pierwiastków z jedności. (iii) Niech 1/11 : C(p) __ C(p)/C(p)~ będzie kanonicznym homomorfizmem. a 1/1~:

C(p)/C(p)~

__

A~

izomorfizmem. o którym mowa w (ii). Niech 1/1: C(p) __ A~ będzie homomorfizmem powstałym przez zfożenie 1/11 i 1/12' Uogólniony symbol Legendre'a definiuje się wzorem niech

będzie

Pokazać, że

dla tego symbolu

słuszne są

twierdzenia analogiczne do twierdzell

2.19 i 2.20.

2. Pokazać. kongruencja

że jeśli

p jest nieparzyst'l liczbą pierwszą. a k jest naturalne. to

x'=-I (modp)

jest

rozwiązalna

3. (i)

wtedy i tylko wtedy. gdy (k. p - l) dzieli (p - 1)/2.

Pokazać. że

do

każdego II można dobrać liczbę

X'

N tak. by kongruencja

= I (mod N)

miała

co mtimnicj N rozwiązań. (ii) Czy w (i) można słowa ..co najmniej"

zast'lPić słowem

.. dokładnie"?

4. Niech N będzie zadaną liczbą naturalną. Dla ilu wartości pierwszych z N kongruencja x' - (I (mod N) ma rozwiązanie? S. Pokazać. że jeśli liczby p i q = 4p pierwiastkiem pierwotnym dla q.

+l

są

(I

względnie

obie pierwsze. to liczba 2 jest

2.4. Zastosowanie sum trygonometrycznych w teorii kongruencji

6. Niech p = 1 mod 4

67

będzie liczbą pierwszą. Pokazać, że jeśli

_ (p-')'

x = ±

2

. (modp).

to x 2 = -I (mod p). Skorzystać

(Wskazówka:

2.1». 7. (i)

z twierdzenia Wilsona (zadanie 2 (i) w podrozdz.

Pokazać. że jeśli al. al XI

a2 ..... a•. b

są

liczbami

całkowitymi.

to równanie

+ (12X2 + ... + a"x. = b

ma rozwiązanie wtedy i tylko wtedy. gdy dla dowolnego naturalnego N kongruenCJa ma

.

.

rozwIązanie.

(ii) Niech f(X) = X 6 + 19X'+56X 1 - 196. Pokazać. że dla każdego natural· nego N kongruencja f(x) == O (mod N) ma rozwiązania. ale równanie f(x) = O nie ma rozwiązań wymiernych.

2.4. Zastosowanie sum trygonometrycznych w teorii kongruencji l. W tym paragrafie podamy wzór na

liczbę rozwiązań

f(xl. Xl, ... , X,,)

przy czym N jest

dowolną liczbą naturalną, a

kongruencji

= O (mad N), o funkcji

f

(2.27)

zakładamy, że

ma

następującą

własność:

Jeśli

dla i = 1,2, .... N mamy

f ną.

= y,. (mod N), to = f (YI . )'2 ....• y,,)

Xi

(x I. X2, .•.. x,,)

(mad N).

Mówimy wówczas. że funkcja f jest okresowa mod N ze względu na każdą zmienZ wniosku I z twierdzenia 2.1 wynika. że tę własność ma każdy wielomian. Rozpoczniemy od elementarnej tożsamości:

LEMAT 2.25,

Jeżeli

N jest liczbq natllralnq, to dla a E Z mamy

L

Sa(N) = t

exp (2rr iat) = N ",od N

loN'

gdy Nla, IV

przeclIvllym

indeks w pierwszej sumie przyjmuje wartości od O do N - I. Jeżeli Nla, to wszystkie składniki sumy są równe jedności, a więc suma jest równa N. Jeśli zaś Nfa, to widzimy. że składniki sumy tworzą postęp geometryczny o pierwszym wyrazie równym l j jlorazie równym z = exp(2rriajN), a więc Dowód:

Możemy przyjąć, że

raZił!.

ZN -

S"(N)

l

= z , = O.

D

68 2. Kongruencie TWIERDZENIE 2.26.

Liczba rOZlViqzwl kongruencji (2.27) jest równa

x. mod N

Dowód: Zamieńmy w powyższym w myśl poprzedniego lematu mamy

I"

N/

~

modN

exp

wyrażeniu kolejność

(2n;/ --[(Xl, .... X,,) ) = 11. O· N

.

.

sumowania i zauwazmy. ze

gdy NI[C!:I, . ... x,,) w przeciwnym razie. D

Otrzymany wzór zastosujemy do oszacowania liczby

rozwiązań

kongruencji (2.28)

gdzie FI. F2.... , Fr są wielomianami jednej zmiennej o współczynnikach całkowitych, o stopniach odpowiednio równych kl. k2, .... k r , a a jest liczbą całkowitą. Twierdzenie 2.26 pokazuje. że liczba "A(N) rozwiązań tej kongruencji równa jest

x, m n;=ln~!~ mamy ),,, >

p~-l -IR"I > p~-l (1 -

(I - ~) p-"}]n)

Szczególnie ważny jest przypadek. gdy FI(X) Wtedy 'I = (s - n)/n, a więc kongruencja

xl' +x2+ ... +x; =a

=

F2(X)

(modp)

>

p'~2 > O.

= ... =

O

F,(X) _ X".

(2.36)

ma rozwiązanie dla każdego a, o ile s > l +11 oraz p > 1I'"/(~-II). Zastępując w powyż­ szym rozumowaniu oszacowanie Mordella przez nierówność (2.35). możemy w podobny sposób otrzymać istnienie rozwiązania kongruencji (2.36) dla s = 2 i P > n 2. Używając metod czysto algebraicznych, można uzyskać rezultat lepszy od wynikającego z poprzedniego twierdzenia: 2.29. Jeżeli p jest liczbą pienv.rzą. to dla dowolnej liczby calkowitej (/ kongruencja (2.36) ma rozwiązallie, o ile tylko s >n.

TWIERDZENIE

2.4. Zastosowanie sum trygonometrycznych w teorii kongruencji

Dowód: Oznaczmy przez A, zbiór tych niezerowych elementów są

sumami co

i /I-tych

najwyżej

elementów tego

potęg

ciała.

Mamy

ciała

73

Zj pZ, które

oczywiście

Al CA 2 C .... a ze skończoności Zj pZ wynika, że dla pewnego r mamy At At+ l Oznaczmy przez r naj mniejszą taką liczbę I. Udowodnimy, że r nie przekracza /I. W tym celu rozpatrzmy grupę G(p)n złożoną Z /I-tych potęg elcmentów G(p). Grupa G(p) jest cykliczna na podstawie twierdzenia 2.12, a więc i grupa ilorazowa G(p)/G(p)n jest cykliczna; poniewaz każdy element g tej ostatniej spełnia warunek gn = l, przeto ma ona co najwyżej /I elementów. Zauważmy teraz. że każdy ze zbiorów A i jest sumą mnogościową pewnej liczby warstw grupy G(p) względem G(p)n. Rzeczywiście,jeśli x mad p leży w A;, a y mad p leży w tej samej warstwie co x mod p. lo z jednej strony marny x = x;' + ... + x;' (mod p). a z drugiej strony y = xz" (mod p) przy pewnym Z nic dzielącym się przez p, przeto

=

y-

(Xl z)"

+ ... + (XI z)"

= ...

(mod p).

od liczby warstw. a więc r < /I. Ponieważ oczywiście O E Al C Ar, pozostaje wykazać. że Ar zawiera wszystkie niezerowe reszly mod p. a lO wynika z uwagi. że

Z tego wynika.

że

r nie

może być większe

a=)"+ln+ ... +I".EA~CAr' O "

WNIOSEK. Jeżeli IV

.f

= /I

którym nie wszystkie

+

razy

kongruencja (2.36) ma dla kaidego a rozwlqwme. dzieIq się przez p.

Xi

l. to

Dowód: Z twierdzenia wynika istnienie

rozwiązania

kongruencji

x;'+ ... +x~=-l (modp). a ponieważ oczywiście nie wszystkie wynika z kongruencji

Xi mogą dzielić się

przez p. zatem teza wniosku

x;' +... +x:: + I" = O (modp).

O

Jak pokazali M.M. Dodson i A. Tietlivliinen III. dla dużych 1/ kongruencja (2.36) ma rozwiązanie już dla s > 68Ji/log2/1. Ten wynik jest bliski optymalnego. gdyz w tejże pracy jest pokazane. że w przypadku, gdy p jest liczbą pierwszą postaci 311 + l. wówczas kongruencja ta nic ma rozwiązania prL.y .1' < (J37," - 1)/2 i odpowiednio dobranej liczbie a. 4. Zajmiemy

się

teraz

kongruencją

(2.36) w przypadku

modułu złożonego:

TWIERDZENIE 2.30. Jeśli

J 4n

s >

l 211

dla /I parzysr)'ch. lllll /I nieparzyslyCh.

10 dla kaidego wlkowitego a i naturalnego N kongruencja

x;' +x2+ ... +x; ma rozwiqzallie

spełniajqce

(N.

XI. X2 • •..•

-li

x 5 ) = l.

(modN)

(2.37)

74

2. Kongruencje

Dowód: Z chińskiego twierdzenia o resztach wynika. padek, gdy N = 1/ jest potęgą liczby pierwszej. LEMAT 2.31.

Niech p

będzie liczbą pierwszą.

t Jeśli pła.

all > 2

że

wystarczy

liczbą IIall1ralną

rozpatrzyć

przy-

i niech

gdy p =F 2. gdy IJ = 2.

~

a kongruencja

(2.38) IIW

rozwiązanie dla

k=

I.

to ma ona

rozwiązanie

dla

w.\·zY~·lkich

k >

1.

Dowód: Jeśli płn, to wystarczy zastosować wniosek 2 z twierdzenia 2.6. Możemy zatem przyjąć, że p dzieli n. Rozpatrzymy wpierw przypadek p =F 2. Jeśli g jest pierwiastkiem pierwotnym mod pk, to kongruencja (2.38) ma rozwiązanie dokładnie wtedy, gdy przy pewnym j > l mamy (l

= gin

(mod li).

Ponieważ potęg

grupa G(pk) jest cykliczna o (p - l)pk-I elementach, zatem liczba II-tych w niej zawartych jest równa najmniejszej liczbie dodatniej Sk, dla której Skn =0 (mod(p - l)pk).

(2.39)

By wyznaczyć takie Sb napiszmy d = (11. P - I). Wówczas n = dni, p - 1= dą, przy ezym (II], q) = l. Ponieważ wobec ptp - l mamy ar(IId = a,,(n) = t - l, pn:elO 111 = pl-l l, przy czym pt/. Kongruencję (2.39) możemy teraz zapisać w postaci .\"kdlp,-I - O (moddqpk-l),

a

WIęC

= O (modqpk-r). l prowadzi to do Sk = O (modqpk-I) Skl

Ze względu na (l. pą) = dodatnia liczba .fh spełniająca tę

j

widzimy, że najmniejsza

kongruencję, to

Sk = q

l-I.

(2.40)

Zatem kongruencja (2.38) ma przy k = I rozwiązania dla s, = ą = (p - 1)/(11. P - l) wartości (l. a ponieważ z (2.40) wynika, ze dla k > t mamy St = PSt-l, prLeto z wniosku 4 z twierdzenia 2.6 otrzymujemy. że jeśli x" = li (mod p"-I) ma rozwiązanie, to kongruencja x k - a (mod p") jest także rozwiązalna. Podobne rozumowanie przeprowadzimy w przypadku p = 2, Z założenia 21k wynika, iż wszystkie k-te potęgi w grupie G(2") leżą w klasie reszt l mod 4. Twierdzenie 2,12 pokazuje teraz, że wszystkie te potęgi leżą w cyklicznej podgrupie H" C G(2"), generowanej przez g = 5 mod zn. Ponieważ H" ma 2,,-2 elementów, a więc k-te potęgi lo elementy gk. gU, ... , gS!.:, gdzie S jest najmniejszą liczbą dodatnią, spełniającą kongruencję sk - O (mod 2,,-2). Napiszmy k = 2'-2/ z 2łl. Wtedy ta kongruencja przybiera postać s12 1- 2 = O (mod 2/1-2), a więc si = O (mod 2"-1) i otrąmujemy, że S = 2"-',

2.4. Zastosowanie sum trygonometrycznych w teorii kongruencji Zatem kongruencja (2.38) ma przy II = t rozwiązania dla jednej wynika teraz dokładnie tak samo jak w przypadku p t- 2. O

wartości

75

a. Teza lematu

LEMAT 2.32. Kongruencja (2.37) ma przy N = pl rozwiązanie, w którym nie wszystkie

Xi

dzidą się

przez p.

Dowód: Rozpoczniemy od przypadku p = 2. Jeśli n jest nieparzyste. to t = 2 i 21 = 4. a przy tym liczby 0, I, 3 - (-I)" (mod4) są n-tymi potęgami mod 4, a 2 = 1"+1", azatemjuż prLY s = 2 ri. li,'zb, w"""''''. WUJ IS(l~ ~J-'.l1-14(l15·1. "

by

W~

PWN 2\lOJ

80 3. Równania diolontyczne możemy więc zakładać. że

przynajmniej jedna z liczb a. c nie znika. Zamieniając w razie konieczności zmienne x i y. możemy więc prąjąć, że a to o. a wówczas równanie (3.1) możemy zapisać w pasIaci

+ by + d)2 - .1l + ay = p. = 2(2ac - bd) i P = d 2 + 4ak.

(2ax

(3.3)

przy czym .1 = b 2 - 4ac. a Teraz rozpatrzymy osobno przypadki L1 = O i .1 nasze równanie przybierze postać

to

O. W pIerwszym przypadku

=

p.

(3.4)

(2ax

, + by + d)~ + ay

Gdy a = O. rozwiązanie istnieje jedynie wówczas. gdy p = y2 jest kwadratem liczby całkowitej i pozostaje rozwiązać dwa równania liniowe lax Jeśli zaś

a

=1=

+ by = ±y -

d.

0, to po podstawieniu

x

= 2ax +by+d.

y = -ay

otrzymamy równanie którego

,2 _ p.

w liczbach wymiernych wyraża Sil; wzorami X _ t. Y _ gdzie' przebiega wszystkie liczby wymierne. a to prowadzi do pełne rozwiązanie

x=

1-

hefi -I')/a - d 2a

y = (fi -I')/a.

(3.5)

Teraz łatwo już otrzymać całkowite rozwiązania (3A). o ile one istnieją. W istocie. przede wszystkim zauważmy. że jeśli x. y w (3.5) są całkowite. to , też jest całkowite. gdyż w tym wypadku ,2 = P - ay E Z. Widzimy też, że warunkiem koniecznym istnienia rozwiązań całkowitych jest rozwiązalność kongruencji Z2 P (moda). Załóżmy, że warunek ten jest spełniony i niech li. l2, .... lr będą rozwiązaniami tej kongruencji. Nadto niech (zf - p)fa = M; (i = 1,2•.... r). Wówczas y w (3.5) będzie całkowite wtedy i tylko wtedy. gdy przy pewnym I a więc 3n7 = af + wbrew wyborowi /I. Istnienie rozwiązania wymiernego równania (3.2) można sprawdzić, korzystając z twierdzenia udowodnionego przez Legendre'a, pokazującego. że (3.2) ma nietrywialne rozwiązanie wymierne wtedy i tylko wtedy. gdy ma ono rozwiązanie w liczbach rzeczywistych oraz każda z poniższych kongruencji jest rozwiązalna: Nie

każde

hi.

x2

:::

hc (mod lal),

x2

:::

ca (mod Ibl),

x2

:::

ab (mod leI).

Twierdzenie to można wyprowadzić z ogólniejszego twierdzenia Minkowskiego-Hassego, którego dowód znajduje się m.in. w podręczniku Z.1. Borewicza i I.R. Szafarewicza

[ II. Twierdzenie 3.2 pozwala na znajdowanie wszystkich

rozwiązań całkowitych

równa-

lila

(3.10) jeśli

znamy przynajmniej jedno jego nania Pitagorasa

rozwiązanie.

Zilustrujemy to na

przykładzie

rów-

(3.11) Zauważmy, że

wystarczy rozpatrywać rozwiązania naturalne tego równania, które speł­ niają warunek (x. y) = l, gdyż jeśli (x. y) = d > I, to dlz i możemy obie strony naszego równania podzielić prLez d 2 , a liczby x/ci i y/d są względnie pierwsze. Jeśli ten warunek jest spełniony, lo dokładnie jedna z liczb x musi być parzysta. W istocie, gdyby obie liczby x. y były nieparzysIc, to mielibyśmy Z2 ::: x 2 + )'2 = 2 (mod 4), co nie jest możliwe. WNIOSEK

2 (Euklides). Wszystkie

rozwiązania

lIaturalne rówIlania Pitagorasa

x 2 +l=Z2. spełniajqce warunki

(x, y)

= I, 21y,

2łx mają pOSIaĆ

y= gdzie

II


v. Ostatecznie 1/ - v.JJ
"

A(N) =

dla N = 1.2.... lJlchOl/zi

nierówność

IA(Nll
oo A (n)b ll = O, pozostaje

Zupełnie

więc zastosować

twierdzenie. O

tak samo otrzymujemy

WNIOSEK 3. Jeżeli

fI (z).

h(z) .... ; bl(Z), b2(Z) .... są ciągami funkcji o wartościach zespolonych określonych IV pewnym zbiorze X oraz istnieje srała C raka. że lJfa wszystkich Z E X oraz N = 1,2, ... mallly N

IL ,",(zll < C. ,,=1

(/ przy rym lim,,_oobll(z) = O jednostajnie IV X oraz szereg :L:llb,,+I(z) - bll(z)1 jesr zbieiny jednostajnie w X, to .I·zereg :L:l bll(Z)f,,(z) jest też zbieiny jednosrajnie w zbiorze X. O

Drugi sposób oszacowania sum, polegający na zastąpieniu sumy calką, zostal zastosowany po raz pierwszy przez Eulera [21 i Maclaurina t I J (tzw. wzór Elllera-Macla/lri/la). Podamy tUlaj pewien szczególny przypadek tego wzoru. wystarczający w większo­ ści arytmetycznych zastosowań. Czytelnik zainteresowany pełną postacią wzoru Eulera-Maclaurina, znajdzie ją w książce G.H. Hardy'ego poświęconej teorii szeregów rozbieżnych (Hardy [2]). Jeieli A jest liczbą naturalną. a funkcja f (t) > Ojest monotoniczna przedziale domkllięrym [A. x]. /O

TWIERDZENIE 4.4. (i) IV

,

L A::;n::;.
O.

(4.5) i (4.6) zwykle nazywa się wzorem Mijhiusa. aczkolwiek po raz pierwszy pojawiła się dopiero w pracach R. Dedekinda i J. Liouville'a w 1857 r. Sam Mobius wprowadził funkcję Il w 1832 r.. ale użył jej do innych celów.) (Równoważność

Dowód: Wzory (4.5) i (4.6) dadzą się zapisać w postaci I * f = g. względnie f = Il * g. a więc ich równoważność wynika z wniosku 3. Jeżeli zachodzi (4.5). to mamy

Lg(n) a

że ilość

Jeżeli

liczb n O.

lego równania w liczbach

,B~

gJ-1.lI-14lJI S-I. " by

W~

PWN 2\lOJ

4.2, Funkcie addytywne i multiplikatywne

115

Dowód: Pierwsza nierówność wynika z prostej uwagi, że wszystkie rozwiązania naszego równania w liczbach całkowitych otrzymamy, zmieniając lnaki w jego rozwiąza~ niach naturalnych. a możemy dokonać 2 l - 1 takich zmian. By udowodnić drugą. zastosujemy indukcję. Ponieważ d 2(n) = d(II). zatem w przypadku k = 2 nasza teza wynika z twierdzenia. Załóżmy jej słuszność dla pewnego k > 2 i zauważmy, że

d,+,(n)

~

l ~

L "I "XHL="

Z

założenia

L

L

l ~

xHdn ', .. ,x.=n/xHl

Ld,(n/d) din

~

Ld,(n). din

indukcyjnego otrzymujemy

L B(k. E/2)d€/2 < B(k. E/2)JI€/2 L 1

dl+I(JI)
2 mamy

L d(n) = x logx + (2y -

l)x

+ .1(x),

gdzie .1(x) = O(X I/ 2). a y jesl slalq Ell/era.

Dowód: Skorzystamy tu z prostej uwagi. żejeśli a,b są liczbami to przynajmniej jedna z tych liczb nie przekracza fi. Mamy

naturałnymi

i ab < x.

Ld(n)= L L "S"

ns..

".b

ub=1I

=2

L

[;]-[v'XJ'=2x L~ -x+O(v'X) "s";;

uS";; Stosując

wniosek 3 z twierdzenia 4.4, otrzymujemy

Tutaj warto zauważyć. a mianowicie przestawienie

daje

słabsze

libyśmy

tezę

twierdzenia. O

że

metoda zastosowana przy dowodzie twierdzenia 4.10. kolejności sumowania w wyrażeniu

oszacowanie reszty.

Rzeczywiście. stosując ją

w tym przypadku. otrzyma-

,

Nm; 2 //lamy

rr'

La(ll) = _x 2 < 12 "_.t

+ O(x log x).

Dowód: Wynika z twierdzenia i lematu 4./1. D Uwaga: Jak udowodnił A.Waltisz [2J, można lU zastąpI c resztę O(x log x) przez O(x log2/3 x), natomiast nie można jej zastąpić przez o(x log logx) (Pćtermantl [l]).

117

4.2. Funkc.ie addytywne i multiplikatywne

W przypadku k > l oszacowania reszty Rdx) w twierdzeniu nie da jak pokazał R.A. MacLeod LI], mamy w tym przypadku Rl(x)

lim sup

x

x_oo

Na koniec zajmiemy

się funkcją

k

I = -

l L k 2 n=! n

się poprawić, gdyż,

00

> O.

Mubiusa.

TWIERDZENIE 4.16. Dla x > 2 mamy

6 2 L/L (1l) = 2"x

n~x

+ O(.jX).

Jt

Dowód: Rozpoczniemy od udowodnienia prostego rezultatu pomocniczego: LEMAT 4.17.

Dla

II

lIaturalnych zachodzi

równo.fć

/L2(n) = L

(4.11)

IJ.-(d).

,

'(n) ~ L L lL(d) ~ L

lL(d)

L

1

d~,Ji

-

LIL(d)[;,]~ d"ó,Ji

~x

f pk. to p{II)+I'

następujące

warunki:

(b) ")+1 < 11)1 pk,

(c)

II)

= pkn)+1

+ r).

przy czym O pk. to = g(ł/)+d,

WIęC

", - I

g(Il) = g(II)+I)

+ g (11)

-

g(pkll)+I) = g(n)+d

+ . L,

E;.

l=p "jol

Jeśli teraz oznaczymy przez r największą liczbę naturalną. dla której Z warunku (b) otrąmamy r < 1 + logll/log(pk) oraz ,~l

,-1

gCII) =

L(g(1l) - g(n)+I» + gCII

F)

= gen,)

+L

,,;-1

L

ti·

)=0 i="jHP'

)=0

Równość tę możemy zapisać

lir_l>

w postaci N,

g(lI) = g(II,)

+ LEm,. )=1

przy Clym m I < 11/2 < ... , limj-_..,oo tlll j = O oral Nr l taka.

(ii) dla

każdego

że

dla wszystkich k. n mamy lak.nl < C,

k istnieje granica limn..... e ak.n = ak>

to dla każdego absolutllie zbieżJlego szeregu L~I Xk mamy

Dowód:

Jeśli

ten przypadek

dla

k mamy Xk = 0, to tcza staje się trywialna, Zadajmy liczbę fE > 0, wybierzmy M tak. by

każdego

wykluczyć.

, 1Ixkl "'9'

dowieść

1

1

1

f(m) ~ - L II

m::Sn

Lh(k)g(m/k) ~ - L II

m::Sn "'Im

h(k) k L

L "'"",n

Przyjmując

2C· -

'

=

O

E.

4C

-k /I

h(k) L

K(')

k::Sn'::S" I '"

g(r)

r"","/'"

teraz Xk

że spełnione są założenia

L

k

= h(k)/k,

a ll .", = -

" widzimy,

Ixk!

twierdzenia, napiszmy, przy naturalnym n,

- L II

ak! .

k>M

' " Ixk! +

< By

129

r

g(r).

::s,,1 l

lematu, a przy tym lim"--->ooa",.,, = M(g) oraz

h(k) k l;m , , - - " 00

n--->oo

To daje nam

tezę

twierdzenia,

~L

l>"

f(m)

1.\ l "1"",1-"1

x m::s..

o.

gdyż

f(m) - _1. L

gdy x zmierza do

k n ~ g(') ~ ,::s,,/l

~

nieskończoności.

~ (~ x

_1) L

Ix I

f(m)

~

o.

"'::'S-"

O

WNIOSEK 1. Funkcja [(II) = a(n)/n ma lI'arto§ć .frednią r6wną n 2 /6.

Dowód:

Jeśli

!I(n) =

l/",

to

f

= h

*I

i wystarczy

zastosować

WNIOSEK 2. Funkcja 1/)(")/" ma wartok średnią r6wllą

Dowód: Wystarczy

przyjąć

twierdzenie. O

6/n 2 .

g = I, h(n) = /L(n)/n. O

3, Większość funkcji arytmetycznych zachowuje się w sposób nicregularny i, by zbadać ich zachowanie, używa się różnego rodzaju aproksymacji przez funkcje o lepszych własnościach. Jednym z pojęć wprowadzanych przy tej okazji jest pojęcie aproksymanty funkcji arytmetycznej. Mówimy, że funkcja g jest aproksymamq funkcji f, jeżeli dla każdego E > O zbiór {n: If(n) - g(n)1 > Eg(n)} ma

gęstoŚć naturalną rÓwną

O.

130 4. Funkcje arytmetyczne

Pierwsze użycie lego pojęcia pojawia się w pracy G.H. Hardy'ego i S. Ramanujana [I), którą pokazali, że logarytm iterowany log logn jest aproksymantą dla funkcji wen). Ich rezultat udowodnimy w rozdziale 5 (twierdzenie 5.3). Różni autorzy zajmowali się następnic pytanicm, dla jakich funkcji f można znalcić aproksymantę niemalcjącą. To się da zrobić dla dużej klasy funkcji addytywnych, ale okazuje się, że funkcje multiplikatywne na ogół tej własności nie mają. Jest to wynik BJ. Bircha [1], którego dowód teraz podamy. TWIERDZENIE 4.25. Jeżeli fUllkcja f jest mllltiplikalywl1a, dO'/(/f/lia i llieograniczOlw oraz lila aproksJmantę niemalejqcq. to istnieje 'aka srala dodatllia C, że f(II) = liC.

Dowód: Niech g będzie niemalejącą aproksymanlą dla f. Zauważmy, że dla doslatecznie dużych /I musimy mieć g(lI) > O. W istocie, jeśli dla nieskończenie wielu /I mamy g(lI) < O, to z monotoniczności g wynika, że nie przyjmuje ona wartości

dodatnich. a

ponieważ

dla prawie wszystkich

zachodzi

/I

nierówność

f(II) - gen) < łlg(n)1 = -4g(II).

zatem 0< fen) < 18(n) < 0, sprzeczność. 11

Zatem dla doslatecznie > /lo, to zastępując g przez

()-1

gl n -

mamy g(l/) > O.

dużych II

gen),

I.

Jeśli

zachodzi to dla

gdy n > "o' d gyn O dla 1/ = 1.2.... Możemy więc przyjąć, że funkcja g przyjmuje wartości dodatnie. Niech b(n) = logf(1I). C(I1) = logg(n). Ponieważ dla każdego €O > O i prawie wszystkich II mamy If(n) - g(II)1 < Eg(n). a więc leb(nl-c(n) - 11 < E, i widzimy. że jeśli €O jest dostatecznie małe, to dla prawie wszystkich n mamy (4.15)

Ib(l1) - c(1I)1 < li. Należy udowodnić, że

przy pewnej stalej C zachodzi Dowód tego rozbijemy na kilka części.

równość

b(lI) _

C logll.

LEMAT 4.26. Mamy

lim C(II) =

"_00

00.

Dowód: Gdyby teza lematu była fałszywa, to funkcje C(II) i g(lI) byłyby ograniczone, a więc istniałaby granica a = lim,,_oo g(II). Ponieważ dla dowolnych E > O i Y/ > O i prawie wszystkich /I mamy a - 'I < g(lI) < a i If(lI) - g(n)1 < lig(II), a więc dla tych

" mamy If(lI) Istnieją

zatem

al < If(n) - g(n)1

stałe

+ Ig(lI) - al

dodatnie A, B takie,

że

< Eg(n)

+ IJ


Aj

ma II

dodatnią gęstość dolną, gdyż

= 1 (modIlo)

i [(n) > A, a

zawiera on wszystkie liczby

postaci

11/

111

=

IIflO

przy

więc

x 1= 2" +o(x).

"o

":;'X I "o

".1

(mod no) !(,,)?:A

Dla

E f2 mamy nierówności (4.16). D III

Możemy

w razie

zatem

konieczności

oczywiście

[(m) = j(n)[(no) > B

+I

>

B, co przeczy

przyjąć,

ze c(n) jest funkcją o wartościach dodatnich, wartości gen) na zbiorze skończonym.

zmieniając

LEMAT 4.27. Niech 'I > O i E hędą dowolne oraz zał6żJ//Y. że lIierównO,I'{ (4.15) zachodzi a i II b. Ismieje wówczas liczba S raka, że dla wszysIkiclI R > 5 mOŻlla dla n znaleiL' liczby 5, r. lak by

=

=

(l - t)R < .1'< R < f < (1

+ II)R.

5 - f - l (modab)

oraz

nierówIlość (4.15)

zaclwdzi dla

/I

= s.

r. as i bt.

Wiemy, że przy ustalonych a.b ilość liczb s E, nie przekracza I]R/4ab. o ile R jest dostatecznie duże. Zbiór Dowód:

A = (s: (1- t)R < s < R,s

ma I]R/ab

+ oCR)

elementów, a zatem Ib(s) - C(s)1
c(si+d - c(a) - 3€,

a zatem Ic(si+l) - c(sdl < c(a)

co prowadzi do

+ 3€,

nierówności

C(I'h) < c(S)

Ponadto zachodzi

+ hc(a) + 3h€

(II = l.

2. 3.... ).

oczywiście nierówność

> (I - 1J)l+hail S,

Sil

W taki sam sposób

(4.17)

otrąmujemy

c(tt> > c(5)

+ kc(b) -

3k€

(k

oraz lk < (1 +1J)I+ktl

J.2. 3.... )

~

s.

(4.18)

Wybierzmy teraz 11, k oraz IJ tak, by (I _1J)h+lj' > (l + lJ)k+lbk, Zauważmy, że możemy

prowadzą

i (4.18)

przy tym wybrać IJ dowolnie male. Wówczas do Sh > tk, a więc i C(I';,) > C(tk) oraz IIc(a)

Ponieważ

+ 3h€

IJ może być dowolnie male, zatem widzimy, że nierówność h log a > k log b

hc(a) > kc(h) - 3(k

+ h)€.

a przeto _Io_g_b > c"(,,b:.:)---,3e:.' loga - c(a) 3€

+

i ostatecznie c(a) laga - c(b) 10gb > -3dlaga Zamieniając

rolami

li

i b,

i

tezę

lematu. D

+ 10gb).

otrąmujemy

c(b) 10gb - c(o) laga > -3dlog a więc

(4.17)

> kc (b) - 3k€.

implikuje

a

nierówności

+ log b),

4.3. Gęstości i wartości średnie

WNIOSEK. Dla każdej pary liczb a. b mamy

da) - ~ ,(h) < 3(lb(a) - ,(a)1 laga 10gb

~

+ Ib(b)

' - ,(b)1) (~ laga

Dowód: Wystarczy zastosować lemat dla E = Ib(a) - c(a)1 111

133

l)

+~ . 10gb

+ Ib(h)

- c(b)l. D

Teraz możemy zakończyć dowód twierdzenia. Z ostatniego wniosku wynika, jest takim ciągiem liczb naturalnych, że

że jeśli

!im (h(1Il) - c(n1)) = O,

1...... 00

o(log IId.

iSlnienie takiego ciągu wynika z (4.15), zatem możemy przyjąć. że ciąg c(II)/logn ma punkt skupienia, powiedzmy C. Z wniosku z lematu 4.27 wynika. że dla wszystkich n mamy to dnd =

Ponieważ

C _ c(n) < Ib(n) - C(II)I log II log /I a zatem Ic(n) - C log III < 3Ib(ll) - c(Il)1 oraz Ib(n) - C lognl < 4Ib(lI) - dn)l. Ponieważ dla

prawie wszystkich II mamy Ib(n) -c(n)1 < (;j4. zatem dla prawie wszystkich II zachodzi nierówność Ib(ll) - Cloglll < E. Wynika stąd, że przy stałym m i dowolnym E > O możemy znaleźć liczbę 11 spełniającą (m. II) = I oraz Ib(l/) - Clognl < Ale b(lIIl1) = b(lII)

+ ben)

Ib(l1IlI) - C log(mn)1 < E.

E,

i ostatecznie

Ib(m) - C log m I = Ib(m)

+ b(lI) -

b(ll) - C log 11/1

< Ib(mll) - Clog(/IIn)1 Dowolność

E daje teraz bem) = Clogm dla

+ Ib(n) -

każdego

CIogIlI < 210.

m. D

WNIOSEK (Erd6s [4]). (i) Jeśli funkcja f jest lIIultipfikatY\lilla, dodamia i monotolliczna,

10 istnieje

stała

c taka.

że

[(n) =

lic.

(ii) Jdli funkcja g jest addytywna i mOllotollicVUl. to istllieje c log /l.

stała

c taka,

że

c(1I) =

Dowód: (i) Możemy założyć, że [ jest funkcją niemalejącą, a zatem ze względu na

fel) = I mamy f(lI) > l to teza jest spełniona z c feN) > I, a więc dla n > jest nicograniezona. bo jeśli N, lo dla N 1 = PI!J2'" Pl

dla wszystkich II. Jeśli dla wszyslkich 11 mamy fen) = I, = O. Możemy zatem przyjąć. że dla pewnego N mamy N spełniona jest nierówność [(n) > feN) > I. Zatem f PI < P2 < ... jest ciągiem liczb pierwszych. większych od mamy

,

\im inf f(Nd = lim inf 1...... 00

1...... 00

n )=1

[(p)) > lim inf f(N)1 = 00. 1--->00

134 4. Funkcje arytmetyczne

Pozostaje

zauważyć. że

założenia

twierdzenia.

g jest

sv.'Oją własną aproksymantą, a więc spełnione są

wszystkie

Ci) do multiplikatywnej funkcji f(lI) = 28{n). O Inne dowody tego rezultatu podali J.M. Cohen [lJ i E. Howe [I].

(ii) Wystarczy zastosować część

Ćwiczenia I.

Podać przykład ciągu

(a) A i n Aj = 0 (b) d(A j ) >

o

(i

zbiorów A"

i=-

Al, .... spełniających warunki

n.

(i = I. 2 .... ).

(c) Suma U:, Aj ma gęstość naturalną. która jest różna od L::I d(A i ). 2. Dla k = 3. 4.... znaleźć gęstość zbioru liczb naturalnych. nie podzielnych przez żadną k-tą potęgę liczby pierwszej. 3. Logarytmicz//a gęstoŚ« Id(A) zbioru A C N jest zdefiniowana wzorem I L logx

Id(A) ~ hm ~_o

I

":S< 1/

o ile ta gmnica istnieje. (i)

Pokazać, że jeśli

A ma

gęstość naturalną,

to ma

też gęstoŚĆ logarytmiczną

i dCA) = Id(A).

(ii)

Znaleźć pr.l)'kład

zbioru A

mającego gęstość logarytmiczną,

ale nic ma-

jącego gęstości

naturalnej. 4. Podać prLyklad funkcji h, dla której szereg L:::"~I h(II)/1I jest zbieżny, ale dla funkcji f = II * I nie jest stuSZlla równość l hm -

n

~~I

0-00 /l b l

f

lI(k)

L !(k) ~ L-· k O

5. Pokazać, że jeśli szereg L::, 11(11)/11 jest absolutnie zbieżny, to funkcja = II o I (gdzie o OlllaCZll splot unitarny) ma wartość średnią równą

f

"mI

h(I/)Ip(I1). II

4.4. Charaktery I. Ważną rodzinę funkcji arytmetycznych stanowią charaktery. zwane też charakterami Dirichleta. Są one cennym narzędziem w dowodzeniu twierdzeń związanych z rozmieszczeniem liczb o zadanych własnościach w postępach arytmetycznych. Zoslaly one wprowadzone przez Dirich1cta na potrLeby dowodu jego twierdzenia o liczbach pierwszych w postępach arytmetycznych, które poznamy w następnym rozdziale. Obecnie na

4.4. Charaktery

135

ogół

wprowadza się je na podstawie ogólniejszego pojęcia charakteru Sk01kzo/lej grupy abelowej i tak uczynimy to tutaj. Niech G będzie skończoną grupą abclową. Jej charaktercm nazywamy kaidy homomorfizm G _ T. gdzie T oznacza grupę multiplikatywną liczb zespolonych o bezwzględnej wartości równej I. Jei:eli 1J1. 1Jz są charakterami grupy G, to ich iloczyn 1ft 4J1 .1jJz definiuje się wzorem 1ft(g) Ih(g)ljJz(g) (g E G). Z takim mnożeniem zbiór wszystkich charakterów grupy G tworzy grupę. Rzeczywiście. charakter 4J(g) = l jest jednością, a 1{t(g) = ljJ(g) = 4J(g~-I) jest elementem odwrotnym do 1J. Grupę charakterów grupy G oznaczamy przez G. Nazywa się ją często grupą dualną do G. Można też definiować charaktery dla grup nieskończonych. w których jest określona pewna topologia. Teoria charakterów grup topologicznych jesl dużym działem matematyki. mającym szerokie zastosowania, także i w teorii liczb. W ramach tej teorii można podać (jak to uczynił 1. Tate w 1950 r.. patrz np. Lang II], Narkiewicz [I]) jednolity dowód równań funkcyjnych dla szerokiej klasy funkcji analitycznych, mąjących znaczenie arytmetyczne. Klasa ta zawiera w szczególności funkcję dzeta Riemanna oraz niektóre funkcje L Dirichleta, z którymi zetkniemy się w następnym rozdziale. Nas będą interesowały przede wszystkim charaktery grupy G(N), złożonej z reszt mod N. względnie pierwszych z N. By opisać jej grupę charakterów, udowodnimy kilka prostych faktów o charakterach dowolnych skończonych grup abelowych.

=

LEMAT

=

~.29.

(i) JeJl; G jest

grupą cyk/icvlą o II

grupa G jest izomorficmll z G.

li

elementach, a g jest jej generatorem. to jej element)' są określone wzorami

j 1Jj(gr)=ex p (21T,:r ) ~

(j.r=O,I, .... Il-I).

(4.19)

(i0 Jeśli_ G I. Gz są skOllczollymi grupami abelowymi oraz

H i G 1 Gl Gz są izomorficzne, IJrzedstawić w postaci

li

H = G 1 Gl Gz. to grupy kaidy charakter ljJ grupy H da się jednoznacznie (4.20)

przy czym gi E Gi. ljJi E Gi (i = 1.2). (iii) Jd/i GJ, Gz, ... , G n są Sk01lcZOIl)'l1Ii grupami ahelowym; oraz H = EE('''l Gi • 10 grupy ił i €E(.., Gi są izomorficzne. a każdy cfwrakter 1J grupy H da .vię jednoznacznie przedstawić IV postaci

~«g" ... , 8,1) ~

n" ~;(g;), ;=1

,

IJrzy czym gi

E G i • 4J; E G; (i

= 1.2..... 11).

Dowód: (i) By sprawdzić. że funkcje 4Jj. zadane wzorem (4.19), są charakterami grupy G = en wystarczy zauważyć, że jeśli O < r, s < 1/ oraz r + s = III mod II, przy czym O