Marzantowicz W. - Elementy Teorii Liczb

I I Spis treści
Wstęp . VII
Wykład l
1. Licr,l»)' naturalne i całkowite l
Ćwiczenia . 2
2. Algorytm Euklidesa 3
Ćwiczenia G
Wykład 2
3. Liczby pierwsze g
Ćwiczcuia . . 11
Zadania t2
4. Równania diofalllycznc 14
Ćwiczenia t7
Wykład 3
5. Liczby FiboJłl\cciego 19
Ćwiczenia . 21
6. Ułamki lUlIcuchowe 22
Ćwiczcuia 27
Zadaniu 28
Wykład 4
7. Kongruencje (l) 30
Ćwiczenia 33
Wykład 5
8. Kongruencje (2) 35
Ćwiczenia 38
Zadauia .. 40
I I Spis treści
Wstęp .. VII
Wykład l
l. Licr,l))' llutUl"(Ilnc i całkowite I
Ćwiczenia . 2
Ćwiczcuia
"
Wykład 2
3. Liczby pierwsze g
Ćwiczcuia . . 11
Zadania 12
4. Równania diofatllycznc I'
Ćwiczenia 17
Wykład 3
5. Liczby FiboJll\cciego 19
Ćwiczenia . 21
6. Ułamki lUlIcuchowe 22
Ćwiczenia 27
Zadania 28
Wykład 4
7. Kongruencje (1) . . . 30
Ćwiczenia 33
Wykład 5
8. KOllgruCIICjc (2) 35
Ćwiczenia 38
Zadauia . . . .
'"
'. p Z-'ltZl'di.
148~S_J.(l
El,,,,,",.,,,,, "",i. 10.». w""'..... 200ó
byWN PWN 2006
VI Spis treści
Wykład 6
9. RozwiązyW(łllie kongruencji 42
Ćwiczcnia 45
Wykład 7
10. \Vh'-SIlO~d Iic~.b pierwS:-:Fh (I) 46
Wykład 8
11. Wlasności liczb pierwszych (2) 50
Ćwiczcuia 54
Zudullia 55
Wykład 9
12. Aproksymacja liczb llicwymiernych liczbami wymiernymi (1) . . 57
Wykład 10
13. Aproksymacja liczb lIiewymicfllych liczbami wymiernymi (2) 61
Ćwiczenia 65
Zadania 65
Wykład 11
14. Przc"Xistawienie liczby 1)(Iturulnej jako sumy kwadratów (I) 67
Wykład 12
15. Przedstawienie liczby naturalnej jako sumy kwadratów (2) 73
Ćwiczeuia 75
Zadania 7G
Wykład 13
16. Funkcje arytmetyczne (1) . . . . . . . . .. . . . . . . . .. . . .
Wykład 14
17. Funkcje arytmetyczne (2) 83
Ćwiczenia 86
18. \Vla,snośd asymptotyczne fuukcji arytlllelyczllych (1) 88
Wykład 15
19. Wlasności asymptotyczllc funkcji arytmetycznych (2) 91
Ćwiczenia 95
Zadania 96
Bibliografia 98
I IWstęp
Niniejszy podrf,;"Cllnik zawiera opracowany materiał prOwadllOllYch przez: !las od
wielu lat wykladów i ćwiczell z teorii liczb dla studentów matematyki i informatyki.
Teoria liczb, jedna z dwóch (obok geometrii) najstarszych dziedzin matematyki, to
ogromny, budowany od pOllad dwóch tysięcy lat dział matematyki, pelen pięknych
rezultatów i różnorodnych metod. \V pełni podzielamy opinię wybitnego angiel-
skicgo matematyka Hardy'ego, któryapelowal, aby wlaśnie teoria liczb pojawiała
się jak naj wcześniej w edukacji matematycznej ze względu na prostotę jej pojęć
i rozumowali. Oczywiście na przestrzeni wieków w teorii liczb pojawiło siQ wiele
skomplikowanych metod i technik oraz bardzo trudnych twierdzeó. Niektóre ta-
kie twierdzenia przytaczamy w podrQczniku, podając źródła II dokładniejszym ich
. . .
omOWlClllem.
Przymiotnik "e1emcntarna" w tytule dobrze oddaje dobór treści, lIa.';z podrQclI-
nik bowiem opisuje najprostsze pojęcia i fakty teorii liczb (zakres przedstawio-
nego materiału jest oczywiście naszym sllbicktywnYlll wyborem). Cheiclibyśmy,
aby opracowanie służy lo zarówllo studentom, jak i nauczycielom akademickim pro-
wadllącym wykłady i ćwiczenia z teorii liczb. ~'Iamy też nadzieję, że zafascynowani
pięknem tej teorii, sięgną po ten podręcznik także uczniowie szkól średnich i na-
uczyciele prowadzący kółka matematyczne.
Dla podkreślenia przeznaczenia naszej książki - podręcznika towarzyszącego
30-godzinnemu wykładowi - zachowano podział materialu na 15 dwugodllinnych
wykladów. Ponadto materiał został przedstawiony w działach tematycznych, na
kOllcU każdego działu zamieszczono ćwiczenia, których rozwiązanie pozwoli Czy-
tełnikowi. łepiej zrozumieć omówiony wcześniej materiał i Ilabrać większej wprawy
w stosowaniu poznanych algorytmów. Oprócz tego, na kOłlcU kilku działów podane
zostały zadania, na ogół trudniejsze od ĆWiCZell; niektóre z tycb zada{l ukazują inne
fakty związane z omawianymi zagadnieniami.
Do korzystania. z potlręczuika wystarczy znajomość elementów teorii lfil1ogości,
ałgebry i analizy matematycznej w zakresie pierwszych dwóch lat typowych kursów
IIl1iwersyteckich z tych przedmiotów. Warto podkreślić, że teoria liczb jest wspa~
niałym źródłem tematów do pisania własnych programów komputerowych, dzięki
którym ł.atwiej badać jej problemy; możua też wykorllystać matematycl\llc pakicty
VIII Wstęp
typn MATHEMATICA, MAPLE czy DERJVE, które zawierają bogate biblioteki

z programami z teorii liczb,
Podr(;!cznik powstał dzięki iyczliwośd wielu osób. Dziękujemy doktorowi Je-
rzemu Rutkowskiemu (recenzentowi skryptowej wersji podręcznika), którego wni-
kliwe i szczegółO\ve uwagi pozwoliły uniknąć wielu usterek. Chcielibyśmy także
wspomnieć nieżyjącego już doktora Adama 1'lysiora, który przeczytał maszynopis,
wprO\vadzając do niego wiele zmian i popra\vek. Serdecznie dziękujemy też profe-
sorom Jerzemu Browkiuowi i Jerzemu Urbanowiczowi, uwzględnienie ich recenzji
i wprowadzenie dalszych zmian stworzyło ostateczną postać naszego podręcznika.
POZUUIJ -Gdm'isk
marzec - kwieciel) 2006
Autorzy
Wykład 1
[ "1 I Liczby naturalne i całkowite

Pełny obraz aksjomatyki zbioru liczb naturalnych fi = {1, 2, . , .} i podstawowe
wlasllogd zbioru liczb całkowitych Z = { ... , -2, -1, O, 1,2, ... } Czytelnik może
znaleźć na przykład w [71. Przypomnimy podstawowe fakty dotyczące zbioru liczb
naturalnych.
AKSJOMAT INDUKCJI
Jeśli S jest dowolnym Zb'i01'C7n takim, ze:
(l)lES,
(2) dla dowolnego n, jeśli n E S, to n + l E S,
to fi C S.
Konsekwencjami aksjomatu indukcji są:
TWIERDZENIE LI (zasada maksimum)

W każdym niepustym ogmniczonym podzbiorze zbioru Hczb natumlnych istnieje ele-
ment największy.
TWIERDZENIE 1.2 (zasada minimum)

W każdym niepustym podzbiorze zbioru liczb naturalnych istnieje element naJ-
mmcJszy.
TWIERDZENIE 1.3 (zasada indukcji matematycznej zupełnej)

Niech każdej liczbie naturalnej n przyporządkowane będzie zdanie logiczne p( n).
Wówczas z założeń:
(1) zdanie 1)(1) jest ],rawdziwe,
(2) dla każdego n E N, jeśli zdanie p(n) jest prawtiziwe, to zdanie p(n + I) jest
prawdziwe,
wynika prawdziwo.4ć zdań p(n) dla każdego n E N.
'. p Z-'ltZl'di. El.""",.,,,,, "",i. 10.». w""'..... 200ó
148~S_J.(l "I'WN PWN 2006
2 Wyklad l
,
Cwiczenia
1. Udowodnij, żc aksjomat indukcji i twierdzenia l.1, l.2 oraz l.3 są równoważne.
2. Znajdź bh!d w dowodzie następującego "twierdzenia": Wszyst1.'"ie koty są jed-
nakowego kolo7'U.
Dow6d
Wyst.arczy wykazać, że spelniony jest następujący warunek: Dla każdego n E fi
w dowolnym zbiorze złożonym z n kotów wszystkie koty są. jednakowego koloru.
Dla n = l warunek oczywiście zachodzi. Załóżmy, :i'.e warunek zachodzi dla n.
Wykażemy, że zachodzi dla n + 1.
\V zbiorze zło:i'.ollym z 71,+1 kotów, zgodnie z założcnicm indukcyjnym, n kotów
ma ten sam kolor, na przykład czarny:
?
ki kz k"
•k,,+ l
Ale z zalo~enia indukcyjnego koty kt, ... , k"+l są też jednakowego koloru. Po-
nieważ koty Iv.!, . .. , k" są c;;o;amc, więc kot k,,+[ też jest czarny.
3. Wykaż,:':e dla każdego n E N liczba 42"+1 + 3"+2 jest wielokrotnością liczby 13.
4. Niech n , k E N U {O}, n # k. Przez (~) oZllaczamy liczbę k!I:'! l)!' Sprawdi, że
G) E N (O! ~ I).
5. Niedł n, k E N U {O}, n ~ k. Sprawdź, że m+ e't') + ... + G) = G~D·
6. Wykaz, że dla każdego n E N U {O} zachodzi następująca równość:
(~)2 + (~)2 + ... + C:)2 = e~').
7. Dla n, r E N oznaczmy przez Sr(n) SlLmę F + 2 r + ... + nr, Sprawdź, że dla
wszystkich n, r:
(n + l)'H - (n + I) ~ (,i')S,(n) + (';')5,_,(n) + ... + CI)SI(n).
8. Wyprowadź wzory na 8[(n), S2{n), 5:3(n), 8.1(n). Udowodnij ich prawdziwość,
stosując metodę indukcji matelllatycZl1cj.
9. UdO\vodnij, że maksymalna liczba jednomianów (które nie są podobne) wielo-
mianu n zmicnHych stopnia d jest równa (";'-d).
I 2 IAlgorytm Euklidesa
Dzielenie liczb całkowitych, pojęcia podzielno<ści, dzielnika, wielokrotno<ści poja-
wiają się już w szkole podstawowej. Zasada dzielenia z reszh! opiera się na nastę
pującym twierdzeniu:
TWIERDZENIE 2.1 (o dzieleniu z resztą)

Dla dowolnych liczb całkowitych a oraz b, b =1= O, istnieją jednoznacznie określone
liczby calkowite q, r takie, że a = qb + r i O",;; T < Ibl. Liczbę q nazywamy
ilorazem, liczbę r resztą.
Dowód
Niech S = {a - qb : q E Z} n (N u {O}). Oznaczamy przez r najmtlleJszą liczbę
zbiol"ll S. Oczywiście zachodzą nierówności: O ",;; T < Ibl. Dla wykazania jeduo-
znaczności zalóżmy, że a = q1b+ r[ = rnb+ 12, gdzie {)",;; TI, 12 < Ibl. Otrzymujemy
stąd, ie I(ql - fł2)bl = h - 1'~1 < Ibl. zatem ql = q2 i 1'1 = 1'~. D
Przykład 2.2
Kwadrat każdej liczby całkowitej nieparzystej ma postać 8k + 1.
Na lllOCY twierdzenia o dzieleniu z resztą, każda liczba całkowita ma jedną z postaci
4q+0, 4q+ 1, 4q+2, 4q+3. Liczby nieparzyste zapisujemy w postaci 4q+ 1 lub
41} + 3, stąd ich kwadraty mają postać (4q + 1)2 = 16q'.? + 81} + 1 = 8(2q'.? + I}) + 1
lub (4q + 3)2 = W q2 + 24q + g = 8(2 q2 + 3q + l) + 1.
DEFINICJA 2.3
:Mówimy, że liczba calkowita b jest podzielna przez liczbę całkowitą a,
jeśli istllieje taka liczba całkowita e, że b = ae. Liczb\! a nazywamy dzielnikiem
liczby b, o liczbie b mówi się, ze jest wielokrotnościąliczby a.
Jeśli
b jest podzielne przez a (inaczej mówi<,c, a dzieli b), to uiywamy OZllacze-
nia alb, natomiast w przeciwnym przypadku stosować będziemy oznaczenie ałb.
Zauważmy, ie aby znalei.ć wszystkie dzielniki danej liczby, wystarczy zualeźć
jej dzielniki dodatnie, jeśli bowiem alb, to także -alb.
Uwaga 2.4
Relaeja podzielności w ilbiol'ze Z ma lIastępuhce wlasności:
(1) alb A ,Id => aclbd,
(2) al b 1\ al c =} al bx + cy
dla dowolnych x, y E Z,
(3) alb 1\ bla =} a=bluba=-b.
DEFINICJA 2.5
Niech a, b E Z, przy czym a f- O lub b =1= O. Największym współnym dzielni-
kiem liczb a i b nazywamy liczbę całkowitą d, spelniaj}!c}! warullki:
14';;5_3. jj by WN PWI>; 2006
4 Wyklad l
(1) dla i dlb,

(2) dla każdej liczby całkowitej c takicj, że ela i elb zachodzi nicrówIlość c ~ d.
Największy wspólny dzielnik liczb a i b oZllaczamy przez (a, b) lub NWD(a, b).
TWIERDZENIE 2.6
Dla a, b E Z, a #- O lub b #- O, istnieją x, y E Z takie, że (a, b) = ax + by.
Dowód
Oznaczmy przez d najmniejszą liczb", zbioru S = {ax + by : x, y E Z} n N. Wy-
każemy, :że d = (a, b). Mamy dl a i dl b. Gdyby bowiem na przyklad a = qd + r,
gdzie O < r < d = axo + byo, to r= a- qd = a(l- (P1J)+ b(-qVO), a zatem rE S.
Otrzymaliśmy sprzcczność z definicją liczby d. Ponicważ
oraz b=c2(a,b),
to
d = (a, b)h~ + CtYo),
czyli (a, b)ld, a WięC (a, b) ~ d. Z definicji (a, b) wIemy, ze d ~ (a, b), stąd
d~(a,b). O
Z twicrdzcuia 2.6 wYllika natychmiast
TWIERDZENIE 2.7
Jeśli dla i dlb, a#-O lub b#-O, to dl(a,b).
DEFINICJA 2.8
Liczby calkowite a i b, (~ #- O lub b #- O, nazy",'amy względnie pierwszymi, jeśli
Następujące twierdzenie podaje podstawową charakteryzację liczb względnie

pierwszych.
TWIERDZENIE 2.9
Liczby całkowite a i b takie, że a f- O lub b f- O, są względnie pierwsze wtedy i tylko
wkdy, gdy istnieją liczby całkowite x, li tIJkie, że
1 = ax+ by.
Dowód
W dowodzie implikacji ,,:::>" wystarczy skorzystać z twierdzenia 2.6. Zakładając na
odwrót, żc istnieją x, li E Z takie, żc ax + by = 1, mamy dła d = (a, b): dl b i dl a,
a stąd dlax+ by, czyli dll. Ponieważ d> 0, to d= l. D
Z t\vierdzenia tego wynikają między innymi;
WNIOSEK 2.10
Jeśli ale i ble omz (a,b) = l, to able.
Dowód
Na mocy twicrdzCllia 2.D istllieją liczby całkowite x, y takie, że 1 = ax + by. Liczby
148~S_J.tl byWN PWN 2006
a i b SI! dzielnikami liczby C, zatcm C = ax] i c = bYI dla pcwnych liczb całkowitych
XI, YI. Stąd c = cax + cby = bYlax + axlby = ab(xy) + XIY), czyli abl c. D
TWIERDZENIE 2.11 (Euklides III w. p.n.e.)

Jeślia,b,cEZ, albc i (a,b)=l, to ale.
Dowód
Z równości 1 = ax + by wyuika, żc c = acx + bcy. Ponieważ alaex] albe, to a
musi tcż dzielić lewą stronę ostatniej równości, więc a Ic. D
ALGORYTM EUKLIDESA
Opiszemy teraz procedurę znajdowania największego wspólnego dzielnika dwóch
liczb całkowitych zwaną algorytmem Euklidesa, podam! po raz pierwszy przez Eu-
klidesa w księdze VII Elementów.
Ponieważ (lal, Ibl) = (a, b), wię(: możcmy założyć, że a # b> O. \Vykonl1jąc
dzielenie z resztą, otrzymujemy
gdzie O < 1""1 < b.
Jeśli 1""1 = O, to (a, b) = b. Jeśli 7'1 t- O, to, diliel'lc b przez 1""1, otrzymamy, że
b = qz1""1 + 1""2, gdzie O < '2 < TI' Jeśli T2 = O, to (a, b) = (b, 1"")) = TI' Jeśli T2 t- O,
to T] = 1]3T2 + 7""3, 0< T:I < 1""2' Postępuj'lc podobnie, otrzym\ljemy ci'lg zależności:
a=q l b+1""I, 0<1""1 < b,
b = 1/27""1 + 1""2, 0<1""2<1""1,
1"",,_2= q"T,,_1 + Tr" 0<1""" < 7"""_1,

T,,_I = q"+I1"",, + O.
Postępowanie musi się skOliczyć, bo 1""1 > 7'2 > ... > 7'" ;;;" O. 1\vierdzimy, że
Aby to wykazać, wystarczy udowodnić na.<;tępujłlcy
LEl\IAT 2.12
Jeśli a = I]b + 1"", to (a, b) = (b, T).
Dowód
Jeśli d = (a,b), to dla i (1Ib, a więc (lir = a - qb, czyli dl(b,T) = C. Z drugiej
strony ci b i clr, II więc ci qb + r = a, czyli ci d. Ostatecznie d = c.
Zasaclllość algorytmu Euklidesa wyuika z ciągu rówIlości
(a,b) = (b,7""d = (7""1,7""2) = ... = (7"",,_1,7"",,) = (7"",,,0) = 7""". D

6 Wykład l
Przykład 2.13
(12378,3054) = 6,
bo 12378 = 4 . 3054 + 162,
3054 = 18· 162 + 138,
162 = 1 . 138 + 24,
138=5·24+18,
24 = 1·18 + 6,
18=3·6+0.
Algorytm Euklidesa pozwala także przedstawić (a, b) w postaci sumy ax+ by, to
znaczy znaleźć takie x i 11, by (a, b) = ax+ by. Korzystając z powyższych równości,
otrzymujemy
6 ~ 24 - 18 ~ 24 - (1:18 - 5· 24) ~ 6·24 - 138
~ 6· (162 -1 ·138) - 138 ~ 6·162 - 7 ·138
= 6 . 162 - 7 . (3054 - 18 . 162) = 132· 162 - 7 . 3054
~ 132· (12378 - 4·3054) - 7· 3054 ~ 132·12378 + (-535)·3054.
Przy obliczeniach ważne jest okrcślenie liczby krokó,v w algorytmie Euklidesa
w zależności od ilości cyfr liczb a oraz b (por. zadanie 9., s. 13). G. Lame wykazał,
że liczba kroków (dzielel'!) w algorytmie Euklidesa dla liczb a oraz b (a ;;;. b> O)
jest co llajwyiej pięć razy większa od liczby cyfr lic:.r.by b (por. [8], twierdzenie 3.,
,. 32).
Więk.<;z,! efektywność w algorytmie Euklidesa można uzyskać, wybierajl!c Tk+l
tak, aby Irk+d ~ .!} i zmieniając ewentualnie znak reszty.
,
Cwiczenia
1. Znajdź iloraz i resztę z dzielenia:
(a) 274 przez 6, (c) -476 przez 5, (e) -8749 przez Hl,
(b) 16809 przez 39, (d) 8749 przez -19, (f) -8749 przez -19.
2. Uzasadnij wszystkie własności podzielności w zbiorze Z zawarte w uwadze 2.4.
3. Wykaż, że dla każdego n E N:
(a) 815" + 2· 3"-1 + l, (b) 131nlJ - n.
4. Znajdź i uzasadnij cechy podzielności przez 4, 5, 8, 10.
5. Niech al, tlz, aJ, il.j E Z oraz af + ii + a:~ = a.i- Sprawdź, że przynajmniej dwie
z liczb aj, tlz, aj, (lI są parzyste.
6. Oblicz (a, b) i znajd';' liczby całkowite x, y takie, że ax + by = (a, b), jeśli:
(a) a = 56, b = 35, (c) a = -233, b = -144,
(b) a ~ 309, b ~ 186, (d) a ~ 6409, b ~ 42823.
7. Oblicz:
(a) (n,n+l), (b) (n,n+2), (c) (m+2n,2m+n), gdzie(m,n)=l.
8. Wykaż, że (5a + 4b, 4a + 3b) = 1 wtedy i tylko wtedy, gdy (a, b) = 1.
9. (a) Opieraj,}c się na defillicji 2.5, podaj definicję największego wspólnego dziel-
nika trzech liczb calkO\vitych, z których przynajmniej jedna jest różna od zera.
(b) Wyka>, " (a, b, e) ~ {(a, b), el ~ (a, (b, el) , gd,;e h " O ((a, b, e) lo
najwjększy wspólny dzielnik liczb a, b, c).
10. Oblicz (817HI, 52003, 33649).

11. (a) Zdefiniuj najmniejszą wspólną wielokrotność dwóch, trzech, skOllczollej
liczby liczb naturalnych (naj mniejszą wspóhu! wielokrotność liczb a i b ozna-
czamy przez [a, b] lub NWW(a, b)).
(b) \'Vykaż, że:
(1) jeśli n E N, to [na, nb] = n[a, b],
(2) la, hJ. (a, b) ~ la· bl,
(3) la, b, cJ ~ [la, bJ, ci ~ [a, Ib, cJ].
12. Oblicz [a, b], jeśli:
(a) a = 60, b = 61, (b) a = 482, b = 1687.
13. Rozwiąż układ równa{l
(x, y) ~ 10,
{ Ix, yJ ~ 100.
14. Liczba wymierua a jest pierwiastkiem wielomiallll U(I + alX + ... + x" E Z[xJ.
Wykaz, że a jest liczbą całkowitą.
15. (a) Udowodnij następujące stwierdzenie: Jeśli a, d są I.akimi liczbami całkowi
tymi, że dl10a - 1, to dl10q + T wtedy i tylko wtedy, gdy dl q + aT.
(b) Stosując powyzsze stwierdzenie, sprawdź, czy 191103208 (a = 2, d = 19).
16. Liczby calkowite x,y,z spelniaj,} równanie x 2 + y2 = Z2. Sprawdź, że 601 xyz.
17. Wykaż, że iloczyn k kolejnych liczb całkowitych jest podzielny przez k!.
18. Udowodllij, że 2"f3" + 1 dla dowolnej łiczby naturalnej n> 1.
19. vVyknż, żc jeśli m, n E N oraz 91m2 + mu + 11. 2 , to 31m i 3111..
20. Wielomian czwartego stopnia f E Z[x] ma nnstępllj,}cą własność: dła każdcgo
a E Z liczba 7 dzieli f(a). Wykaż, że 7 dzieli wszystkie wspólczynniki wielo-
mianu j. Czy liczbę 7 można zastąpić liczbą 5? A liczbą 8?
21. Wykaż, że w zbiorze Z2 nie istnieją punkty odległe o mniej niż ~ od prostej
y = ,JX +'5'
22. Rozpatrzmy ml.<;t,<puj'iol gr~:
• dane są dwa stosy kamieni, \v pierwszym stosie znajduje się a kamieni, w dru-
gim b kamiclli;
b, ~ Z.=y<ki. El."""",,,,,, ,,,,,'o /0.1>, w.......·• 2006
ll_148SS_J.C byWN PWN 2006
8 Wyktad 1
• rozpoczynający grę
(osoba A) wybiera stos i zabiera z niego d kamieni, jdli
wybrał pierwszy stos, to dla, jeśli drugi, to dl b;
• drugi gracz (osoba B) postępuje według tej samej zasady;
• wygrywa ta osoba, która zabierze ostatni kamieil (ostatnie kamienie).
Odpowiedz, kto powinien wygr!\{;, jdłi:
(a) a ~ 5, b ~ 3, (b) a ~ 12, b ~ 8, (e) a ~ 28, b ~ 20.
Wykład 2
I '3 I Liczby pierwsze

DEFINICJA 3.1
Liczbę naturalną n nazywamy liczbą pierwszą, jeśli n > 1 i jedynymi jej dziel-
nikami są l i n. Każdą liczbę naturalną większą od l, która nie jest pierwsza,
nazywamy liczbą złożoną.
Liczby pierwsze oznaczać będziemy zwykle literami P, q, zbiór wszystkich liczb
pierwszych {2, 3, 5, 7; 11,13, ... } zaś literą lP. Liczby pierwsze są czynnikami, na
które można l'Oillożyć każdą liczbę naturalną. Informację tę zawiera następujące
twierdzenie pochodzące Dcl Euklidesa:
TWIERDZENIE 3.2 (zasadnicze twierdzenie arytmetyki)
Każda liczba natuml1w złożona może być przetlstawiona w postaci iloczynu liczb
l)ienn.~zych. Przedstawienie laJ.-ie jest jednoznaczne z dokładnością do kolejno,{d
czynników.
Przed dowodem tego twierdzenia wykażemy kilka faktów pOlfloeniezy<.:h.
LEMAT 3.3
Jdli p E lP oruz p I a . b, to PI a lub p I b.
Dowód
Jeśli założymy, że pła, to (a,p) = l, gdyż p E IP'. Korzystając z twierdzenia 2.11,
mamy wtedy pl b. O
LEr.UT 3.4
Jeśli p E lP i plaj'" a", lo istnieje k, 1 ~ k ~ n, takie źe plaj;.
Dowód
Posłużymy się zasadą indukcji.Z twierd:.lenia 2.11, jeśli pl al'" a" = (al'" an_l)u n ,
to plal'" an_1 lub pla" i możemy skorzystać z założenia indukcyjnego. D
WNIOSEK 3.5
Jeśli
liczby p, 'lI,.'.' q" są pierwsze oruz 1) Iql ... qn, to P = 'lI; dla pewnego k,
l<k<n.
Dowód
Z lematu 3.4, istllieje takie k, że 111f1j;, ale flj; E IP' i]l > 1, a więc 11 = flj;. D
10 Wykład 2
Dowód zasadniczego twierdzenia arytmetyki

Istnienie rozkładu. Niech liczba n będzie liczb,! złożoll1!. Zbiór takich d E N, że
1 < d < n i dl n jest lliepusty. Oznaczamy przez Pl najmniejszą liczbę tego zbioru.
Liczba 1)1 jest pierwsza, bo w przeciwnym przypadku istniałoby q < Pl takie, że
ą> l i qlPl, co przeczyłoby \vyborowi Pl. Stąd możemy zapisać
gdzie 1 < nI < n.

JeślinI E IP', lo otrzymaliśmy żądany rozkład, a jeśli nie, to powtarzamy rozumo-
wanie dla nI i otrzymujemy
n = 1)1' P2 '112, gdzie l < 112 < nI, 1)1, P2 E IP' itd.
\V k06cll llzyskujemy przedstawienie
n= PI"'Pb
gdyż nI > 11.z > ... > 1 jest ciągiem małejącym liczb naturalnych, a więc ciągiem
Sk011czonym.
Jednoznaczność rozkładu. Nk"Ch n = Pl'" Pr = '11'" fis (1' :;;; 8), gd;"ie p, i %
są pierwsze i uporządkowane lIiemałejąco, to znaczy
Pl :;;; P2 :;;; .. . :;;; Pn

POllieważ 1)11'11'" q~, ;"atem ;" wnioskl\ 3.5 wynika, że 1)\ = I/k dla pewnego k,
l :;;; k :;;; 8, a stąd Pl ";!; ąl· Analogicznie: ąll Pl ... P" więc ql ";!; Pl, czyli Pl = ql·
D;"ici,!e wyj~ciową równo~ć pr;"e;" Pl = 1/1 i postępuj,!C tak samo dla kołejnych
czynników obu rozkładów, otrzymalibyśmy
l=qr+l"'q~ oiler<s.
Nie jest to możliwe, a więc 7' = S oraz Pi = q,.. o
WNIOSEK 3.6
Każda liczba natumlna n > l może być zapisana jednoznacznie w postaci kano-
nicznej
11 = ,{l:l
1 ... ,>"'
,. ,
gdzie Pi E lP, aj E N, Pl < P2 < ... < p,-.

Czasami używa się zapisu n = fl'iEP pf;, gd;"ie ai E N U {O} oraz aj = O dła
prawie wszystkich i.
Przyklad 3.7
24=2~·31, 100=2 2 .5'2, 17640=2:1 .3'2.5.7'2, 2006=2·17·59.
Z definicji liczby pierwszej nic wynika bezpośrednio nicskoóCZOllOŚĆ zbioru lP.

Zgodną z intuicją. odpowiedź daje następujące:
TWIERDZENIE 3.8 (Euklides)

Istnieje nieskorkzenie wiele liczb pien/Iszych.
'1I_148~S_J.'" by WN I'W N 2IJ06
3. Liczby pierwsze 11
Dowód
Przypuśćmy, że [fi' = {PI,l-'2, ... ,p,,}, gdzie Pl = 2, 1-'2 = 3, ... Rozpatrzmy liczbę
naturalną N = Pl ... p" + 1. Ka mocy zasadniczego twierdzenia arytmetyki liczba
N dzieli się przez pewną liczbę pierwszą q. Ale z zalożenia q = Pi, dla pewnego
l ';';;i';';;n,astąd qIN-Pl"'p,,=l,coprzcczynierówności q>l. D
Podamy teraz elementarną metodę znajdowania wszystkich liczb pierwszych
mniejszych od danej liczby naturalnej n, zwaną sitem Eratostenesa (IlI w. p.n.e.).
SITO ERATOSTENESA
Podstawą tej metody jest następująca obserwacja: Każda liczba naturalna złożona
n ma co najmniej jeden dzielnik l)ierlJ).~z!l l', laki że l' .;.;; ..;n. Rzeczywiście, niech
n = a . b, gdzie l < a < n, l < b < n. Zakładając, że b .;.;; a, mamy b2 .;.;; a . b = n,
czyli b .;.;; ..;n, ale b musi dzielić sit;; przez pewną liczbę pierwszi! lJ, a stitd dla niej
P';';; b.;.;;;n.
Metodę tę najlepiej zilustrować na przykladzie.
Przyklad 3.9
Niech n = 100. Wypiszmy kolejne liczby naturrtlne od 2 do 100. \Vykrdhny z tej
listy krotności liczby 2, czyli liczby parzyste. Najlllniejsza z liczb nieskceślonych,
tj. 3, ml\t;i być liczbą pierwszą. Następnie z pozostałych liczb wykreślamy krotno-
ści 3, czy li 3, 9, 15, 21, ... Najmniejsza z liczb nieskreślonych, tj. 5, musi być liczbą
pierwszą. DaJej postępujemy tak samo. Postępowanie nasze SkOlkzy się w następ
uym kroku dla p = 7, bo ';100 = 10. Liczby nieskreślolle, a więc u nas lIiebędące
krotnościami 2, 3, 5, 7, oraz te wymienione są wszystkimi liczbami pierwszymi
muiejszymi od 100. Są to: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
59,61,67, 71, 73, 79, 83, 89, 97.
•
Cwiczenia
l. Stosując sito Eratostenesa, ułóż tablicę liczb picrwszych mniejszych od 200.
2. Znajdź naj mniejszą liczbę złożollą postaci 3" + 2.
3. Czy liczba 9991 jest pierwsza?
4. Znajdź rozkład kanoniczny następujących liczb:
(a) 443, (e) 6967664,
(h) 11849, (d) 61930099.
5. Anna i Jllaria zebrały cztery rodzaje kwiatów. Kwiaty te mogły rozdzielić ll1ię~
dzy sobą na 1363 sposoby przy zalożeniu, że jedna z nich ma co najmniej jeden
kwiat dowolnego rodzaju, a druga pozostaje kwiaty. Ile kwiatów było h!cznie?
6. Znajdź najmniejszą liczbę naturalną n taką, że f(n) jest Hczbą złożoną., je§li:
(a)f(n)=x'!+x+17,
(b) f(x) ~ x' + 21x + I,
(e) f(x) ~ 3x' + 3x + 23.
12 Wykład 2
7. Sprawdź, że dla każdego n E ]\i, {3} nie wszystkie liczby n, n + 2, n +4 są

pierwsze.
8. Niech c = (!4 + 4&\ a, b E Z, {O}. Sprawdź, że je@ (! oj:. ±1 lub &oj:. ±1, to c
jest liczbą zlożoną.
9. Wykaż, że 111" + 3m4 n - 5m 3 n 2 - 15m2n 3 + 4mn4 + 12n" oj:. 33 dla dowolllych
m,n E]\i.
10. Odpowiedz, jakie liczby są "pierwsze" w nastQpuj1lcych zbiorach:
(a) {1,3,5,7,9, },
(b) (2,4,6,8, 10, ),
(e) (l,4, 7, 10, 13, ).
'vV którym z tych zbiorów zachodzi twierdzcnie analogiczne do twierdzcnia 3.2?
11. Niech p będzie liczbą pierwszą. Wykaż, że liczby 2P +3P nie można przedstawić
w po:;taci x m, gdzie x, Ul E N, Ul> 1.
12. (a) Udowodnij, że jeśli m, n E ]\i U {O}, m oj:. n, to
(2 2'" + 1,22" + 1) = 1.
(b) Korzystając z (a), podaj inny dowód twierdzenia 3.8.
Zadania
1. Wykaż, że każdą liczbę naturalną n można przedstawić

jednoznacznie w postaci
i
n = 3;' ±3 ± ... ±3;', gdzie i],~, ... ,i, E Nu {O}, i 1 > i2 > ... > i,.
,
2. Wykaż, że każdą liczbę naturalną n można przedstawić jednoznacznie w postaci

n = dl . l! + ... + (h· k! ,
gdzie di E ]\i U {O} oraz O er;;;; d,. er;;;; i dla każdego 1 er;;;; i er;;;; k.
3. Niech funkcja f: Z2 ----; 'Z'} będzie określona wzorem f(x, y) = (ax+ by, cx+ liy),
gdzie a, b, c, d E Z. Udowodnij, że f{Z2) = Z2 wtedy i tylko wtedy, gdy ad - be
= ±1.
4. UdO\vodnij, że dla żadnych k, n E N liczba ±t±k~1 ± ... ± k~" niejcst całkowita.
5. (a) \'Vykaż, że liczba naturalna, która nie jest potęM liczby 2 może być przed-
stawiona w postaci sumy dwóch lub więcej kolejnych liczb naturalnych.
(b) Sprawdź, że przcdstawicuie, o którym mowa w (a) jest jednozuaczuc wtedy
i tylko wtedy, gdy liczba naturalna ma postać 2up, gdzie a E Nu {O}, P E p, {2}.
6. Udowoduij, że dla każdej liczby uatnralncj 11 i dla każdej liczby llaturalncj
nieparzystej k zachodzi wzór
I k +2 I; + ... +n.k
1+2+ ... +111
3. Liczby pierwsze 13
7. (a) Niech (a, b) = d, (a', b') = d'. Wykaż, żc
(aa', ab', ba', bb') = dd'.
(b) Sprawdi, że jeśli n E H, to (a, b)" = (a", b").

(c) Sprawdź, że jeśli n E H oraz a" Ib", to al b.
8. Niech a, b, c, d E N oraz ab = cd. \Vykaż, że
(a, cHa, d)
= a.
(a, b, c, d)
9. \Vykai, że dla każdego n E N istnieją liezby calkowite a,,, b" takie, że liczba
kroków przy obliczaniu (a,,, b,,) za pomocą algorytmu Euklidesa jest równa n.
10. Wykaż, że dla m, n E H, jeśli x m - l, x" - l E K[x], gdzie K jest ciałem, to
N\VD(x m - l, x" - l) = x(m,,,j - 1.
11. Sprawdź, że dla m, n E N moc zbioru
{( i,j) E N 2 : 1 ,;;;; i ,;;;; m, 1 ,;;;; j ,;;;; n, prosta y = :~ x przecina kwadrat
o wierzcholkach (i - l,j - l), (i,j -1), U -1,j), (i,j)
przynajmniej w dwóch punktach}
jest rówIla m+ n- (m, n).
12. Wykaż, że jeśli
k, l E N, k f- l, to istnieje nieskOlkzenie wiele liczb n E H takich,
że(k+n,l+n)= l.
13. (a) Opieraj,!c sil( na definicji 2.5, podaj definicjo;; nujwil(kszego wspóluego dziel-
nika elementów nieskOlkzonego podzbioru zbioru Z.
(b) l\"iech S będzie lliepustym podzbiorem zbioru N zamknil(tym nil dochiwa-
nie i niech (S) będzie największym wspólnym dzielnikiem elementów zbioru S.
Wykaż, że (S) > l wtedy i tylko wtedy, gdy dla wszystkich u, v E S zachodzi
nierówność (u, v) > 1.
14. Dla n E N, n > l, funkcje j, g określamy wzorami:
g(n) ~ [f(~J
gdzie [x] OZllacza część całkowitą liezby x. Sprawdź, że:
g(n)~{"0, jeśli
jeśli
n E !fI',
n 9t !fI'.
15. Wykaż, że
lilII Sllp(]i,,_l - p,,) = 00,
"..... ""
gdzie ]i" oZllw;za n-t,! z kolei liczbl( pierwszą.
" '*"''''', co ul "" i " " ""'"
14 Wykład 2
16. Niech n będzie liczbą naturalną nicparzystą większf! od 3,

k = min{x E N: nx +l jest kwadratem},
t = min{.1: E N: nx jcst kwadratcm}.
Wykai, że n jest liczbą pierwszą wtedy i tylko wtedy, gdy k > J oraz t > J'
17. Niech n = TITJ,EPl,~i oraz f(n) = 1 + L:~1 O;' Pi. Udowodnij, że dla każdego
n > 6 istnieje liczba naturalna k, taka że
(Jo ... of)(n)~8.
'--v--'
k '''''Y
I '4 I Równania diofantyczne

DEFINICJA 4.1
Równaniem diofantycznym nazywamy dowolne równanie mające postać
f(x\, ... , x,,) = 0, gdzie f jest funkcją n zmiennych, szukane rozwiązania zaś mają
być liczbami całkowitymi.
Nazwa tego typu równa{\ pochodzi od imienia greckiego matematyka Diofalltosa

(III w. n.e.). Znany jest epigram o długości jego życia:
t życia zajęła mu m/odo§ć, potem po /~ życia wyrosła mu broda, następnie
po ~ życia ożenił się, po 5 latach urodził mu się syn, syn żył połowę krócej
od ojca, ojciec zmarł 4 lafa po synu.
\Viek Diofantosa znajdziemy z równania
l l l l
6 x + 12 x +7 x + 5 +2"x+4=x,
które ma rozwiązanie dla x = 84.
Przykladem równania diofantycznego jest równanie liniowe nx + my k,
o którego roz\viązaniach mówi następne
TWIERDZENIE 4.2
Równanie diofantyczne nx + my = k ma rozwiązanie wtedy i tylko wtedy, gdy dlk,
gdzie d = (m, n). Jeśli pam liczb X(), 1AJ jest pewnym rozwiązaniem tego równania,
to wszystkie rozwiązania dane są wzorami:
m n
x = X() + d . t, y = Yo - d . t, t E Z.
4. Równania diolantyczne 15
Dowód
Istnienie rozwiązania wynika z twierdzenia 2.6. Załóżmy, że pary liczb 7b, Yo i x,
y są dwoma rozwiązani<uui tego rówIlania, to zllaczy n:.IQ + mYo = k = nx + my.
Wtedy
(J) n(x - X{)) = -m(y - Yo).
Jeśłi d = (m, n), to n = rJ, 111 = sd oraz (r, s) = 1. Wstmviając ostatnie równości
do (1), otrzymujemy
r(x - 'b) ~ -,(y - Yo).
Z twierdzenia 2.11 wiemy, że slx ~ 7b, czyH x = 7b + s· t X{) + ~' . t, a stąd
Y -!Al = -rt oraz y = 110 - rt = !Al - J . t. D
Najsłynl1iejszym równaniem diofantycznym jest
RÓWNANIE FERMATA
Okolo 1637 roku Pierre de Fermat studiując łaciilski przekład dziel Diofantosa, na
marginesie rozdziału o trójkach pitagorejskich zaHotował, że dla n ;;.;. 3 równanie
(2) x" + y" = z"
nie ma rozwi::!zall w liczbach całkowitych różnych od zera. Fermat napisał też, że
znałazł wspaniały dowód tego twierdzenia, który niestety nie zmieścił się na mar-
ginesie książki Oiofantosa. Wielu wybitnych matematyków próbO\vało udowodnić
twierdzenie (hipotezę) Fermata, nazywalle często Wiełkim Twierdzeniem Fer-
mata (patrz Uwagi 4.7). Dziś, z przymrużeniem oka, można powiedzieć, że historia
matematyki wygh!cłałaby wpełnie inaczej, gdyby egilempłarz ksif!żki Fermata mial
większe marginesy.
W przypadku n = 1 równanie (2) ma oczywiście nieskoJlczenie wiełe rozwią
zm'l. Dla n = 2 równanie to lIosi nailwę równania Pitagorasa, a jego rozwiązania
będące liczbami naturałnymi nazywamy trójkami pitagorejskimi. Równanie Pi-
tagorasa ma lIieskoliczellie wiele rOZWif!Za{l - fakt tell był zllany Pitagorasowi
i jego uczniom (VI w. p.n.e.), którym przypisuje się następujące
STWIERDZENIE 4.3
Istnieje nieskończenie wiele trójek pitagorejskich - liczby x = 2n+ l, y = 2n 'l. +2n,
z = 2n 2 + 2n + l spełniają równanie Pitagomsa.
Następujące twierdzenie charakteryzuje trójki pitagorejskie:
TWIERDZENIE 4.4
Wszystkie całkowite rozwiązania równania Pitagomsa
x 2 +y2=z2,
spełniają.ce warunki (x, y, z) = 11 y, z> 0, dane są wzommi:
21xI Xl
x=2st, y=i_t 2, Z=S2+ t 2,

gdzie s, tE1:, s> t> O i (s, t) = 1 oraz 2fs - t.
ll_148~S_J. ObyWN PWN 2006
16 Wykład 2
Dowód
Z warunku (x, y, z) = l wynika, że dokladnie jedna z liczb x, y jest parzysta oraz
liczba z jest nieparzysta, w przeciwnym razie 4łx2 + y2 i 41z 2 lub na odwrót.
Niech x = 2c. Ponieważ x 2 = (z + y)(z - y) i liczby z + Y, z - y są parzyste,
więc z + y = 2a, z - y = 2b, czyli z = a + b, y = a-b. Z równości c2 = ab, gdzie
(a, b) = 1, wynika, że a = S2 i b = t2 . Ostatecznie x = 2st, y = S2 - t 2 , Z = S2 + t 2 .
Oczywiście x, y, z określone pO\vyższymi "..'Zorami spelniają równanie Pitagorasa.
\Varunek 2ł s - t jest spełniony, gdyż w przeciwnym przypadku liczby x, y, z
bylyby parzyste. D
Korzystając z powyższych rozważaiI, można udowodnić następuhce
TWIERDZENIE 4.5 (Fermat)

Równanie diafantyczne
x4 + y4 = z2
nie ma rozwiązań różnych ad zera.
Dowód
Patrz zadanie 24, s. 28. D
Z twierdzenia 4.5 wynika
WNIOSEK 4.6
Równanie diafantyczne
gdzie m>- l,
nie ma niezerowych rozwiązań.
Dowód
\Vystan:zy zauważyć, że równanie x4m + y4m Z4m mozemy zapisać w postaci
(x"') I + (y"')'l = (z2"'f. D
Uwagi 4.7
1. Zauważmy, że sluszność hipotezy Fermata wystarczy wykazać dla liczb pierw-
szych nieparzystych (postępuje się podobJlie, jak w dO\vodzie wniosku 4.6).
2. Jak podaje P. Ribcnboim l, hipotezę Fermata dla n = 3 potwicrdzili niezależnie
L. Euler i K. Causs, dla n = 5 dowód znalazł P. C. L. Dirichlet w 1825 roku,
dla n = 7 dowody podali G. Lamć i V. A. Lebcsquc w 1840 rokn. Wielki krok
naprzód w pracach Iład hipotezą Fermata zrobił E. E. Kummer, który w la-
tach 1847-1850 udowodnił sluszność hipotezy Fermata dla tak zwanych liczb
pierwszych regularnych (jedyne liczby pierwsze nieregularne mniejsze od 100
to 37, 59, 67). S. S. \Vagstaff jr \V 1976 roku za pomocą maszyn cyfrowych
sprawdził sluszno.ść hipotezy FeI"luata dla liczb pierwszych n < 125000. Prze-
10m w pracach Bad dowodem Wielkiego 'I\vicrdzenia Fermata nastąpiI dopiero
w ostatnich dwudziestu kilku latach. \V 1983 roku G. Faltings udowodnił, ic
dla Każdego n >- 3 równanie Fermata ma sKOIkzellie wiele rozwiązali \V 1993
4. Równania diolantyczne 17
roku na wykładzie
w Instytncie r\ewtona uniwersytetn w Cambridge A. Wiles
ogłosił, że udowodni! Wielkie 1\vierdzenie Fermata. Jednak dopiero po dwóch
latach, w 1995 roku, po usunięciu luk w dowodzie, ukazały się dwie prace \Vi-
łesa 2 zawierające pelny dowód.
,
Cwiczenia
1. Znajdź wszystkie rozwiązania w liczbach całkowitych następujących równa6:
(a) 3x + 5y = 1, (c) 999x - 49y = 5000,
(b) 1.72x+20y=100, (d) 903x+ 731y = 2107.
2. Znajdź wszystkie rozwiązania w liczbach naturaluych następujących równałl:
(a) 5x + 3y = 12, (c) 21x + tiy = 15,
(b) L5x+7y~111, (d) 40x+63y~521
3. Znajdź wszystkie trójki pitagorejskie x, y, z, takie że z < 30.

4. Sprawdź, że 1712x + 3y wtedy i tyłko wtedy, gdy 1719x + 5y.
5. Smok ma 2000 głów. Rycerz może ściąć jednym cięciem 33 głowy łub 21 głów,
lub 17 głów, lub 1 glowę. Smokowi odrasta natychmiast odpowiednio 48 glów
łub O głów, lub 14 głów, łub 349 głów. Smok zostanie zabity, gdy wszystkie
głowy będ,! ścięte. Czy rycerz może zabić smoka?
6. Znajdź wszystkie rozwiązania w liczbach całkowitych równania danego wzorem

15:1: + lOy + 6z = 61.
(\Vskazówka: 1'lożna skorzystać z zadania 3., s. 12)
7. Znajdź wszystkie trójki pitagorejskie tworzl!ce:
(a) ciąg arytmetyczny,
(b) ciąg geometryczny.
8. Znajdź wszystkie trójkąty prostokątne o bokach całkowitych a, h, c, takie że

(a, h, c) = 1 oraz:
(a) wartość liczbowa poła takiego trójkąta jest równa wartości liczbowej jego
obwodu,
(b) wartość liczbO\va poła takiego trójkąta jest dwa razy większa niż wartość
liczbO\va jego obwodu.
9. Niech SI = {(x, y) : x2 + y2 = l} będzie okręgiem jednostkowym. Wykaż, ze
(x, y) E SI n Q2 wtedy i tyłko \vtedy, gdy
2mn m2 _ n2
x = m2 + n 2 ' ll1b x= y=
m2 + n2 '
2 \Viles. A, Modli/ar c1lip/i,; C1<11JeS awf Fffl1WI'.~ /a.~t Ihwrem, Annals of IdathClIli\tica, ],1], nr :.1-
1995; Taylor R, Wilcs A., Ring llieo'"elic propcrties 0/ certai71 Ilecke algebms, AUlłals or Uathclllatics,
141, nr 3,1995.
l<" ~ ,_j.
L"VZ)'<ki. El"••,",""",
ll_148~S_J. C> by WN PWN :!OOb
I~-:b. W........... 2Q(l()
18 Wykład 2
dla pewllych liczb całkowitych m, n.

10. Znajdź wszystkie rO'~wiązallia w liczbach całkowitych równania x2 + y'!. = 2z'l.
11. Niech x, y, z będzie trójki} pitagorejską. Wykaż, że dla każdej liczby llaluralllcj
fl ~ 3 zachodzi x n + yn < zn.
nierówność
12. Zalóżmy, że x, y, z, n E N oraz x n + y" = z". Udowodnij, że min {x, y} ;ot: fl.
13. Rozwiąż w liczbach całkowitych następujące równania:

(a) 3' ~ 4y + 5, (e) x' + 3!l ~ 7x, (e) x(x + l) ~!l,
(b) 2' - 3' = I, (d) x' + 3!l ~ 31x, (f) x(x + l)(x + 2)(x + 3) = y'.
14. Rozwiąż w liczbach naturalnych następujące równau.ia:
(a) n"" + n' = n:, (h) x! + yl = z!.
15. Udowodnij, że jeśli p E P ..... {2}, to istnieją dokładnie dwie różne liczby naturalne
x i y spełniające równanie
2 l l
- = - +-.
p x y
Wykład 3
I '5 I Liczby Fibonacciego

Leonardo z Pizy, zwany Fibonaccim, na pewno nie spodziewaj się, jaką zawrotną
karierę zrobi!! liczby, które pojawiły się w jego słynuym dziele LibeT Abaci (Księga
Rachunków), wydanym \V 1202 roku. Liczby Fibonacciego naclal budzą duże zain-
teresowanie, li wide problemów zwilp;anyeh z nimi do dzisiaj nic zostało rozwiąza
nych. Nie wiadomo na przykład, czy istnieje niesko!lczenie \"iele liczb pierwszych
f'ibonaccicgo.
DEFINICJA 5.1
Ciągieln Fibonacciego nazywamy ciąg liczb naturalnych określony wzorem rc-
kurcucyjuylu
fi = l, h= l, /"+1 = i" + /"-1 dla n = 2,3, ...

Elementy tego ciągli uail)'w1\my liczbami Fibonacciego. poczl!tkowe liczby eil!gll
to: l, 1,2, 3, 5, 8, 13,21,34, 55, 89, 144, 233, 377.
TWIERDZENIE 5.2
Niech /" będzie n-tą liczbq Fibonacciego. Wtedy
(j", /,,+d = 1 dla n:;;;' 1.
Dowód
Jeślidl/"+I oraz (11/,,, to dl/"-h gdyż /"-1 = /"+1 - f". Rozumując tak samo,
otrzymamy dl/n - 2 , dl/,,_;l, ... , i W kOl'leu dl/l, Ale /1 = 1, czyli d = 1. O
TWIERDZENIE 5.3
Dla liczb Fibonaccicgo zachodzi równość
/m-H. = /"'-1 /n + /m /"+1 .

Dowód
Stosujemy indukcję ze względu na u, przy ustalonym m. Dla u 1 wzór jest
prawdziwy,
/"'-1/1 + /",!t = /"'-1 + /m = /"'+1'
Wykład 3
I '5 I Liczby Fibonacciego

Leonardo z Pizy, zwany Fibonaccim, na pewno nie spodziewaj się, jaką zawrotną
karierę zrobi!! liczby, które pojawiły się w jego słynuym dziele LibeT Abaci (Księga
Rachunków), wydanym \V 1202 roku. Liczby Fibonacciego naclal budzą duże zain-
teresowanie, li wide problemów zwilp;anyeh z nimi do dzisiaj nic zostało rozwiąza
nych. Nie wiadomo na przykład, czy istnieje niesko!lczenie \"iele liczb pierwszych
f'ibonaccicgo.
DEFINICJA 5.1
Ciągieln Fibonacciego nazywamy ciąg liczb naturalnych określony wzorem rc-
kurcucyjuylu
fi = l, h= l, /"+1 = i" + /"-1 dla n = 2,3, ...

Elementy tego ciągli uail)'w1\my liczbami Fibonacciego. poczl!tkowe liczby eil!gll
to: l, 1,2, 3, 5, 8, 13,21,34, 55, 89, 144, 233, 377.
TWIERDZENIE 5.2
Niech /" będzie n-tą liczbq Fibonacciego. Wtedy
(j", /,,+d = 1 dla n:;;;' 1.
Dowód
Jeślidl/"+I oraz (11/,,, to dl/"-h gdyż /"-1 = /"+1 - f". Rozumując tak samo,
otrzymamy dl/n - 2 , dl/,,_;l, ... , i W kOl'leu dl/l, Ale /1 = 1, czyli d = 1. O
TWIERDZENIE 5.3
Dla liczb Fibonaccicgo zachodzi równość
/m-H. = /"'-1 /n + /m /"+1 .

Dowód
Stosujemy indukcję ze względu na u, przy ustalonym m. Dla u 1 wzór jest
prawdziwy,
/"'-1/1 + /",!t = /"'-1 + /m = /"'+1'
20 Wykład 3
Zakh:u::łaj11e prawdziwość tezy dla n ,;;;; k, wykazujemy, że jest ona prawdziwa dla
n= k + 1. Z zalożenia indukcyjnego
oraz i"'+k-l =im-IA-I+i",A·
Dodaj'lc te równości stronami, otrzymujemy
i"'+1:+1 = im+k + im+k-1 = im-lUk + ik-d + i",(j1:+1 + id

= im-J!1:+1 + imA+2 . D
TWIERDZENIE 5.4
Liczba i"", jest podzielna przez im dla m, n >- l.
Dowód
Stosujemy indukcję ze względu na n przy ustalonym m. Oczywiście im li",. Ponieważ
i"'(k_l) = iml:+m = imk-l im + i",kim+h więc Z założenia indukcyjnego otrzymujemy,
że liczba im(k+l) jest podzielna przez i",. D
LE/I.'IAT 5.5
Jeśli 1ft = qn + 1', to Um,j,.) = (j",j,.).
Dowód
Korzysta.j,!C z twierdzenia 5.3, mamy
Um'f,,) = (ją"+r,i,,) = (ją,,-J!r + i'l'Jr+I,J,,).
Zauważmy, że jeśli to (a + c, b) = (a, b). Z
bl c, warnnku i" lią"
otrzymujemy za-
tem (j,,,, i,,) = Uą"-l in i... )· Wystarczy więc wykazać, że (jq,,_ h 1,,) = 1, gdyż jeśli
(a,c) = I, to (a,bc) = (a, b). Niech (fą"-l,i,,) = d. Ponie'vaż dlf" i i"lią ", ,vięc
d If,[ll , a jeduocześnie dli,,"-I, czyli d dzieli kolejne liczby Fibouacciego i zgoduie
z twierdzeniem 5.2 li = l, co dowodzi sluszności lematu. D
TWIERDZENIE 5.6
Dla liczb Fibonacciego (1"" 1,,) = 1", gdzie d = (m, n).
Dowód
Przyjmujemy, że m>- n. Z algorytmu Euklidesa
m=lJln+1'I, O<1'I<n,
n = 1h1'l +
1'2, 0<1'2 < 1'1,
Tt_Z = qkTk_1 + T"k,

T"k_1 = IJk_IT"J;+O.
Z lematn 5.5 otrzymlljcmy ciąg równości (im,f,,) = (f,,,ir,) = (jr'J,j"1) = ...

= (jl)._I' irl)' ale Tk' I 1'J:-1 , więc z twierdzenia 5.4 wynika, że (jl) _1' i",,) = j,~. Równo-
cześnie TJ, = (m,n), co kOl'ICZY dowód. D
Z twierdzenia 5.6 wynika bezpośrednio następuj'lcy
WNIOSEK 5.7
Jdli Ul, n >- 3, to dla liczb Fibonacciego im li" wtedy i tylko wtedy, gdy mln.
5. Liczby Fibonacciego 21
W 1843 roku J. BilLet:1 podal wzór ogólny na n-ty wyraz cil}gU Fibollacciego.
WZÓR BINETA
Jeżeli U,,) jest ciągiem Fibonacciego, a = !(l + JS) oraz {j = !(l- JS), to
a" -
/.. =.j5
rr dla n = 1,2, ...
Wyprowadzenie wzoru Bineta

RozpatrLlIIy t07-SalnQŚĆ
(I) /,,+, - xl" = (I - x)(I" - x/,,_,) + (I + x - "')/"_,,
gdzie n = 2,3, ... Liczby a = !(l + J5) oraz {j = !(l - JS) są pierwiastkami
równania 1 +.:t - zZ = 0, zatem ~ + (3 = I. Wstawiając -do to7.samOŚCi (l) w miejsce
z liczby o oraz tJ, Olrlymlljemy ciągi równości
/ ..+! - a/.. = I3V" - a/.. _I) = (j'1U.. _I - / .. -'1) = = {j"-IU'l - aM = (3",
/"+1 - J3/" = aU.. - /"-1) = 02V"_1 - (J/n-Z) = = a"-IUz - (J/I) = o".
Odejmując :stronami równości
/"+1 - 0/" = {J".
/"+1 - fJ/n = o",
olr-tymujemy /n = JS .
et " ." D
Postępując podobnie jak prJ;y wyprowadzeniu wzoru Binela, mO'L:na znaleźć
wzór ogólny na JH"y wyraz ciągu rekurencyjnego (a,,) określonego pr7.ez warunki:
al = s, a'l = t, a,,+2 = aa,,+1 + ba" dla n = 1,2, ...
Poda.my teraz kilka tO'L:samości związanych z liczbami Fibonacciego:
(a) /?; =/.. +1/..-1 +(-1)"-1,
Iłk = hł+lfzk-l - l ,
(h) U"f,'+3)'l + (2/"+ 1 /"+'1)'1 = /ł.'+3'
(c) wzór Lucm:ia:
/" =("o') + ("~') + (",') + . + G~{) + ("T'), gd'ie j = [",'],
(d) /1 + 2h + + tlf" = (n+ 1)/,,+2- /"H + 2,
(e) /1 +13 + +12"-1 =12",
(f) h + f, + + h" = /",+, - I.
•
Cwiczenia
1. Znajdź dWlldzieSll! liczb~ Fibonaccicgo i razló;,: ją na czynniki pierwsze.
2. Korzj'stając wyłącznic z definicji ciągu Fibonacciego, wykaż, że 51/';n dla każ
dego n= 1,2, ...
22 Wykład 3
3. Udowodnij tożsamości (a)-(f) ze s. 21.

4. Wykaż, że jeśli A = [~:], fo = O i U,,) jest ciągiem Fibonacciego, to dla n E N
j" ]
f"+1 .
5. Wykaż, że jeśli f" E !fI', to n E IP'" {2} lub 11,=4 (U,,) - ci,!g Fibonacciego).
Czy prawdziwe jest twierdzenie odwrotne?
6. Wykaż, że kaida liczba naturalna może być przedsta\viona jako skOl1czona Sllma
elementów ciągu Fibollacciego, w której każdy element występuje uie więcej niż
jeden raz.
7. Sprawdź, żc jeżeli U,,) jest ci,!gicm Fibollaccicgo, k dowohll! liczbl! naturalną,
to
U"-!2k+f", f"+3k+f"+I) = l.
S. Znajdź wzór ogólny na n-ty wyraz ciągu rekurencyjnego (a,,), określonego przez
waruuki: al = s, U2 = t, a,,+2 = ao.,,_1 + ba." dla 11 = 1,2, ...
(Wskazówka: Skorzystaj z tożsamości
(1.,,+ 1 - La" = (a - x)( a." - xa.,,_ d + (b + ax - 2
:r ) a,,_1 .
Rozpatrz dwa przypadki w zależności od tego, czy wielomian b + ax - x 2 ma

dwa różne pierwiastki, czy jeden dwukrotny.)
9. Korzystając z poprzedniego ćwiczenia, podaj wzór ogólny na n-ty wyraz ciągu
rekurencyjnego (0.,,) określonego przez warunki:
(a) a"+2 = 5a"+1 - 6a", al = 2, G2 = 5,
(b) a,,+2 = 2a"+1 - a", al = O, G2 = 4.
I '6 I- -,U: .:łc=a.:. :m.:.:.k, -i'-'ła:. :.ń.:. :c =u-=-c:. :.ho: .:w:. :.e=- - ~
Możliwość przedstawienia liczby rzeczywistej w postaci ulamka la(lCuchowego
znana już była matematykom greckim. Fibonacci (XIII w.) zapisywał ułamki
w postaci podobnej do zapisu liczb wymiernych w fonnie ulamka laiJcuchowego. Za
właściwy początek rozwoju pojęcia ułamka ła6cuchowego należy uznać jednakze
wydanie w 1572 roku książki matematyka wioskiego R. Bombelliego L'Algebra
Opern. \V dziele tym autor stosuje ułamki łańcuchowe do obliczania pierwiastków
kwadratowych z pewnych liczb calkowitych.
6. Ułamki fańcuchowe 23
DEFINICJA 6.1
SkOllczonym ułamkiem łallcuchowym arytmetycznym nazywamy ulamek
j
"" + - - - - - ' - - c j c - - - -
a, + ------'----
a,+ l
.. +-~~
l
a,.,-I +-
a"
gdzie: O{) E Z oraz al,U<l,···,a" E N. Liczby al,a-l, ... ,a" nazywamy luianowni-
kami częściowymi.
Do zapisu powyższego ulamka używa się często symbolu
Uwaga 6.2
Wartość skollCzoncgo ulamka laócuchowego arytmetyczuego jest Iiczbll wymierllą.
Prawd.ziwe jest również stwierdzenie OdWl'Otlle.
TWIERDZENIE 6.3
Każdą liczbę wymierną moma przedstawić w postaci skończoncgo ułamka łańcu
chowego arytmetycznego.
Dowód
Niech x = %' gdzie a, b E Z I b > O, będzie liczb::! WYllllerną. Stosując algorytm
Ellklidesa, otrzymujemy
a = bil{) + 1'[, O<1'[<b,
b=rla\+12, O<rz<r\,
TI = rzl1J] + 13, O < 13 < '2,
T,,_Z = T,,_Ia,,_1 + T",

1',,_\ = r"a" + O,
gdzie T], 12, ... , Tr, > O oraz al, ~, ... , u" > O. Z powyższych rówIlości mamy
a r, l
",,+-~
b b ao+T'
b 1'2 "1
ad - = al +-,
T, "
" "
11_ Wl5'l_i. fi 111% WiN iOO6
24 Wykład 3
skąd
a j
b= (lo + -----'-c-j - - - -
ad - - - - - = - - - -
Przykład 6.4
Przedstawimy liczbę WYUllerną ~ w postaci skoóczonego ułamka Imkuchowego
arytmetycznego.
Ponie\vaz
8=1·5+3,
5 = 1 . 3 + 2,
3=1·2+1,
2 = 2·1,
WięC
83111 1
-=1+-=1+..-=1+-"',0, =1+ , = 1 + - - -,, -
5 5 ~l'+
:l :i 1+"3 1+ l
z 1+ z
DEFINICJA 6.5
LiczbęSI,; = [ao; al, (Lz, ... , ak], gdzie k = 0,1, ... ,11, nazywamy reduktem k-tego
rzędu lub krócej k-tym reduktem ułamka łallcuchowego [ao; al, 1l'2,···, a"I.
Liczby rzeczywiste niewymierne ró\vnież można przedstawić w postaci ułamków

laócllchowych, ale w tym przypadku uieskollCzonych.
TWIERDZENIE 6.6
Każdaliczba niewymiema a rozwt]a Stę w nieskończony ułamek ła1icuchowy aryt-
mdyczny
l
'" + ----''-,-,-
al + l
a, +-
to znaczy, że a = lim,,_<x> 0'" gdzie 0" = [ao; al, (Lz, ... , a,,].
Dowód
Niech ao = [a] będzie największą łiczbą całkowitą nie większą od a;
1
a = ao +-, gdzie al > 1.
a,
6. Ułamki lańcuchowe 25
Analogicznie otrzymujemy
l
01= a, + , Oz > l,
a,
l
Oz= a, + , 0';\ > 1,
O':j
0:, > 1.
Poniewa2 O' jest liczbą niewymierną, więc żadna z liczb a; nie może być wymierna.
Powyższe postępowanie można więc kontyuuować w nieskOllczoność.
Zauważmy dalcj, że liczbę
l
; ~ "" + - - - - " - - , , - - -
a, + - - - - - = - - - -
a,+
otrzymuje się z liczby 6"_1 poprzez zmianę w przedstawieniu la{lCucbowym 6"_1

ostatniego mianownika częściowego a,,_1 na a,,_1 + ~. Oznaczmy licznik i mianow-
nik reduktu 6" odpowieduio przez P" i Q,,; przyjmijmy ponadto, że P-I = l oraz
Q-l = O. Kolejne redukty możemy \vówczas przedstawić w następującej postaci:
6_
0-
ao -_ Po
,
1 00
110+1. al Po
P_I + P,
"' aIQo+Q_1 Q,
azP I + Po P,
azQI+QO Q,
i indukcyjnie
J" = -
,a~"~Pc""-"'_+~p",,"-~2 P"
a"Q"_l + Q"-2 Q,,'
W ten sposób możemy obliczać liczniki i miauowniki l'eduktów wedlug nastQpują
cych wzorów:
P_I = 1, Q-I = O, Po = 110, Qo = 1,
(1)
P" = a"P,,-l + P,,-'z, Qn = UnQll-1 + Qfl-2 dla n = 1,2, ...
Korzysta.jąc ze wzorów (1), latwo wykazać indukcyjnie, że dla każdej liczby natu-
ralnej n :zachodzą następujące :zależności:
(-1)"-'
(2)
QflQ"-I'
(-1)"(1,.,
(3) P"Q,,-'l - P"-2Q" = (-l)"a,,, J" - J"_2 =
Q" Q"-2 '
26 Wykład 3
(4) (P,,, Q,,) ~ l.
Ze wzorów (3) wynika, że ciąg (Ci 2 ,,) jest rosnący, 11 ciąg (Ciz,,-d jest malejący.
Zauważmy, że
1
O' = (/{I + -a, > (.I(),
l ]
Q= (/{I + l < (/{I+-,
a,
ad-
a,
l ]
0'= (/{I + 1 1 '
ad--], (lI +-
a,
a,+-
a,
więc widać, że dla n nieparzystych Q < Ci,,, a dla n parzystych Q > Ci". Zatem
z powyższych rozwuża1'ł i ze wzorów (2) otrzymujemy następujące oszacowanie:
Ze wzorów (1) wynika, że lim Q" = 00 i \vobec tego lim,,_OCl Ci" = Q. D

Przykład 6.7
Liczba ł{1 + v'5) jest pierwiastkiem rÓ",'Jlallia x - 1 + ~, zatem ł(1 + v'5) -
[1; 1, 1, 1, ... 1.
Uwaga 6.8
Równość P" Q"-l - P"-l Q" = (-1) ,,-l (wzór (2), s. 25) można wykorzystać do
znalezienia rozwiązania szcl\ególnego równania ax + by = c. Na przykład, niech
(I = 17, b = 14, c = L
Liczbę i~ przedstawiamy w postaci ulamka łallcuchowego [1; 4, l, 2] i obliczamy

kolejne rcdukty tego ulamka:
Po (.I() 1 Pl al Po + P_I 4·1+1 5
- - - - -
Qo l Ql
l' ILIQO+Q_1 4·1+0 4'
P2 azP 1 + Po l .5+1 G Pa (laP2 + Pl 2·6+ 5 17
- - - -
Q2 azQl+QO 1·4+1 5' Q:l (laCh + QI 2·5+ 4 14
St<!d 17· 5 - 14 . 6 = (_1)2, to znaczy poszukiwane rozwiązania to: x = 5, Y = -6.
Uwagi 6.9
l. l\vierdzenie Lagrange'a orzeka, że liczba algebraiczna ma stopieli równy dwa
wtedy i tylko wtedy, gdy można ją przedstawić w postaci nieskOllczonego ulam-
ka hlllcuchowego okresowego (por. ćwiczenie 7., s. 27).
2. Znane są przedstawiellia w postaci niesko1'łczonegoułamka lallcucbowego aryt-
metycznego niektórych liczb przestępnych, na przykład sam Euler wykazał, że
c = [2; l, 2, l, 1,4, 1, l, 6, ... 1.
6. Ułamki fańcuchowe 27
3. 'W 1978 roku R. ApĆry wykazał, że wartość «(3), gdzic «(8) = E:l ,:" s> 1,
jest funkcją dzeta Riemanna, rozwija się w niesko6czony ulamek la6cuchowy
gdzie W- r#7 - ... - :u" +:;;',:. "'Z7,,+:> - •.• oznacza ulamek lal1cuchowy
6
l
5 - -;-c:;-----------;;------
117- n{l
34n3 +51n z +27n+5
vVynika st<1fI, że «(3) jest liczłn! Iliewymierlll~. Warto~ki «(2k) dla k = 1,2, ...
SIl znane i są to liczby niewymierne. Problem wymierności liczb «(2k + 1) dla
k = 2,3, ... pozostajc nadal nicrozwi'p;any.
,
Cwiczenia
1. Przedstaw w postaci ułamka ła{lCuchowego arytmetycznego następujące liczby

,y",,'e""c' 17 3 l2~ -5:191
\ . 3' 17' 92' :197{l'
'
2. Przedstaw w zwyklej postaci następuj/!ec ulamki laócllchowe:
(a) [2; 1,4], [-3; 2, 12], [O; 1, 1, 100],
(b) [a; a, a, a, aj, [aj b, a, b, aj,
(c) [2;3,7], [2;3,6,11.
3. Pn>;edstaw w postaó nieskOllczollego ułamka bUlcuchowego arytmetycznego na-
stępujące liczby: J2, ,)3, JS, /7, Jll, Jj3.
4. Oblicz wartości:
(a) [1;1,1, ], (e) [1;2,1,2],

(b) [2; l, l, ], (d) [1; 1,2,31.
(Zapis [l; 2, 1, 2] oznacza ulamek [lj 2, 1,2,1,2, l, 2, ... J.)
5. Korzystając z uwagi 6.8, rozwi}~ż uast\:pującc równania:
(a) 43x+5y=1,
(b) 18x + 3y ~ 24.
6. \Vykai, że jeśli [ao; al, ... , am] = [boj bl , ... , b,,] oraz a"" b" > 1, to m = n oraz
aj = bj dla i = O, 1, ... , m (por. ćwiczenie 2(c)).
1. UdO\.. . odnij, że jeśli a = [ao; a\, /lz, ... , anJ, to a jest liczbą algebraiczną stopnia
drugiego (por. uwaga 6.9.1).
" '*"''''', co ul "" , "" ""'"
28 Wykład 3
8. Sprawdź, że jeśli 6" = -if,; = [Go; al, ... , ar,], to:

(a) P PH
II
= [a,,; a,,_\, ... , al, Go],
(b) ~
OH
-- la . ari-l,···, ".
lI, '-"~, " lI·
9. Odpowiedz, z jaką dokladności~! przybliża liczbę e ulamek lat'wuchowy sko6-
czony [2;1,2,1, l ,4,1,1,6] (por. uwaga 6.9.2).
10. Wykaż, że jeśli () = [Go; al, 02, ...], to
_() = {[-(1<)- l: l, al -1,02, a:J""J,
[-U(J - l, az + l, a3,14, ... J,
gdy al>l,
gdy al = L
Zadania
18. Wykai, że jeśli a,b E N oraz (a, b) = l, to każdą liczbę naturalną n > ab-a-b
można pr;-.{.'{\stawić w postaci n = ax + by, gdzie x, y E N U {O}.
19. Niech A = {aln+az:n E N}, B = {bln+b:!:n E N}, gdzie a], az, al,b:! E N oraz
(aJ, az) = 1 i (aJ, b:!) = L Wykaż, że A n B = 0 albo istnieją liczby Cj, C2 E N
takie, ~.e (Cl,C2) = 1 oraz An B = C = {cln+ C2:n E N}.
20. Udowodnij, że zbiór SI n Q2 jest gęsty w zbiorze SI (SI = ({x, y) : x2+ y2 = l}).
21. Udowodnij, że dla każdej liczby naturalnej n równanie x 2 + y 2 = z" ma rozwią
zauie w liczbach naturalnych.
22. "Vykai, że równanie A'I + S-l = C-I ma nieskot'tczenie wicie rozwiązali w zbiorze
M2X2 (Z) takich, że A 4 , B\ CI są macierzami niezerowymi (Mzxz(Z) - zbiór
lnacierzy kwadratowych stopnia drugiego o wspólczynnikach całkowitych).
23. Udowodnij, że wszystkie rozwif!zania w liczbach naturałnych równania x 2 +
2 yz = ZZ spełniające warunek (x, y, z) = l dane są wzorami: x = luZ - 2v 2 1,
y = 2uv, z = u 2 + 2v 2, U, 1) E N, 2 ł u oraz (u, 1)) = 1.
(\Vskazówka: Zmodyfikuj dowód twierdzenia 4.4.)
24. Udowodnij twierdzenie 4.5.
(Wskazówka: Zalóż, że istnieje pewne rozwią;-.anie :ZO, Yo, Z{l E N, dla którego
(1\), '!lo, 20) = l, przy czym 20 jest najllllliejsze z możliwych. Stosując twier-
dzenie 4.4, skonstruuj rozwiązanie Xl, YI ,Zl E N, takie że (Xl, Yl, Zl) = l oraz
Zl < -Zo.)
25. Wyh-u, że jeśli Xl,Yl jest rozwiązaniem rówll8uia Pełła x 2 - dy 2 = 1 (d E N, d
-liczba bezkwadratO\va), to ciąg par x,,, y", określony następująco: x" + y,,/d
= (Xl + Yl V,,"
d) , n = 1,2, ... , spełnia to równanie.
26. Niech Xl = 2, YJ = 1, XJ;+l = 2Xl; + 3YJ;, YHl = Xl; + 2YJ;, k = 1,2, ... Sprawdź,
że dla każdego k E N para XJ;, Yl; spelnia równanie x 2 - 3 y 2 = l.
21. Udowodnij, że istnieje nieskOllczenie wiele liczb naturalnych spełniających rów-
lianie 6x 2 + 3x = 2y 2 - 2y.
11_ t:m5_J. tllij'WN I'WN iOOS
6. Ułamki lańcuchowe 29
28. Znajdź wszystkie rozwiązania w liezbach całkowitych równania

x2 + 3 y2 = 1998x.
29. Niech r będzie dowolną liczbą llaturalną. Udowodnij, ze Cł1!g reszt modulo r
kolejnych wyrazów ciągu Fibollacciego jest okresowy.
30. Wykaż, że równanie JX+ /Y = VP1P'2 nie ma rozwiązaÓ w liczbach naturalnych
(PhP'l - różne liczby pierwsze).
31. Niech 110, al, ... , a", bo, bl , ... , b", b"+l E H. Kiedy
32. Wykaz, że jeśli o = [11oj at,~, ... J, to:

(a) 02" < J 2m + 1 dla dowolnyeh rn, n E H,
.-,
(h) Ql/ ;? 2"- dla n;? 2,
(e) (P n , P,,-d = 1 oraz (Q", Q,,-d = 1 dla 11;;;-' O.
33. Niech o = [Go; al, U'l""] i niech bl , b'l,'" będzie dowolnym sko6czonym cią
giem liczb lIatllralnych. Udowodllij, że lim'l--+oo [ao; al, 1l2, ... , a", bl , ~, ... j = 0:.
34. Sprawdź, że:
(a) Jn'l +1=

2n] dla n = 1,2, ... ,
[n;
(b) vn~+2=[n; n,2n] dlan=1,2, ... ,
(c) vn 2 1=[n-l;1,2n 21 dlan=2,3, ... ,
(d) vn 2 2=[n-l;1,n 2,1,2n 2] dlan=2,3, ...
35. Udowodnij, że jeśli o = [110; al'~""J, to dla każdego n ;? O przynajmniej
P , 6"+1 = QP. tl spełnia nierówność
jedna z liczb O" = -'-""Q
• "~l
P 1
0-- <-,
q 2 q'l
gdzie za p wstawiamy P" (Pl/H), za fi zaś wstawiamy Q" (Q,,+d·
36. Mówlmy, że liczba wymierna ~ (q E H) dobrze aproksymuje liczbę niewy-
mierną o, jeśli
10q-pl=min{loy-xl: XEZ, y=1,2, ... ,q}.

vVykai, ż;e każ;dy rcdnkt liezby o dobrze ją aproksymnje.
Wykład 4
I'7 I Kongruencje (1)
Pojęcie kongruencji, czyli przystawania, zostało wprowadzone przez Ganssa w jego

słynnym dziele Disąuisitioncs Arithmeticae (wydanym w 1801 1".) do baclania po-
dzielności liczb całkowitych przez iune liczby całkowite.
DEFINICJA 7.1
Niech m będzie liczbą naturalllą. ł\llówimy, że liczba caikowita a przystaje do
liczby całkowitej b moduło m, i piszemy a = b (mad m), jeśli mla - b. Tak
okrcśloną rda<.:ję nazywamy kongruencją. Liczbę fIL nazywamy modułem kon-
gruencJI.
STWIERDZENIE 7.2
Relacja przystawania (koagruencjt) modulo m jest 7'elacją n)wnoważnościw zbi07'ze
liczb całkowitych Z. Warstwy tcj relacJi nazywamy klasami reszt rnodulo m.
Każdą liczbę całkowitą a możemy zapisać w postaci a = qm + r, O ,,;;; r < m,

więc każda liczba całkowita przystaje modulo m do jednej z liczb O, l, ... , m-l.
Ponieważ żadne dwie liczby spośród liczb 0,1, ... , m-l nie przyslają do siebie
moduło m, \vięc zbiór {O, l, ... , m- l} tworzy pelny układ reprezentantów warstw.
STWIERDZENIE 7.3
Kongruencje mają następujące własności:

(l) Niech a, b, c, li E fE oraz m E N. Jeśli a = b (mod m) i c = li (mod m), to:
(i) a+ b = b+ li (mod m),
=
(ii) a - c b - d (mad m),
(iii) ac = bd (mad m).
(2) Niech W(Xl, X2, ... , 3;,) = L(o],,,,.o~) U(Oj, ... ,o"}xf'x-f'··· X~" będzie wielomia-
nem n zmiennych o współczynnikach całkowitych. Jeśli dla każdego wielo-
wska,źnika (Oh 01,"" O,,)
b(o], .. ,o"} - U(Oj, .. .,o.l (mad m) oraz

Ci = d, (mad m) dl(! każdego i, 1 C2,···,C,,)= L b("t,_ .. ,()~)df',···,d~~ (mod m).
(Ol, ... ,On)
(3) Jeśli a· d ~ b· d (mod rn) i (d, m) = l, to a ~ b (mad rn).

(4) Jeśli k jest (/owolną liczbą natumlną, to a = li (mad m) wtedy i tylko wtedy,
gdy ak ~ bk (mad 7Ilk).
(5) Jeśli a = b (mod md i a = b (mad Tn:!), to a =
b (mod [m], 1712]), gdzie
[mi, rT12J oznacza najmniejszq wspólną wielokrotność liczb mi, 7Tt2.
=
(6) Jdli a li (mod m), to (u,m) = (b, m).
Dowód
(1) Udowodnimy własność (iii). Jeśli mi a- b, to mi (a- b)e, czyli ae be (mod m).
Analogicznie, jeśli mi c - d, to mi b( c - d), czyli be = bd (mod m). Z przechod-
lliości relacji przystawuuia ae bd (mad m).
(2) JL"St to wniosek z poprzedniego punktu, bo jeśli c, = d, (mad m), to z wlru;JlOści
(iii) lllamy et _ d7; (mod m), a następnie Illo:ina korzystać z pozostałych
własności \v (1).
(3) Ponieważ ml(ad - bd) = (a - b)d i (d, m) = l, więc wystarczy skorzystać
z twierdzenia 2.11.
(4) Zauważmy, że mla -
b wtedy i tylko \vtedy, gdy mkl(a - b)k.
(5) .Jeśli mIla - b i ntzla - b, to z określenia nujllllliejszej wspólllej wielokrot-
ności (patrz ćwiczenie l1(a) ze s. 7} wynika, że [mi, 111211 a - b, czyli a = b
(mod [mi, ntz]).
(6) a = mt + b i wystarczy skorzystać z lematu 2.12. D
Bezpośrednią konsekwencją elementarnych wlasllości kongruencji są cechy po-

dzielności
CECHY PODZIELNOŚCI PRZEZ LICZBY 3, 9, 11
Niech a E N oraz a = a,,10+a"~11O"-1+ ... +ao, gdzie O < a; < 9, będzie zapisem
liczby a w ukladzie dziesiętnym.
(1) Ponieważ 10 l (mod 3),więc na mocy 7.3(1) a a,,+a,,~l+"'+ao (mod3)
i wobec tego a = O (mad 3) wtedy i tylko wtedy, gdy a" +... + ao = O (mad 3).
(2) Podobnie, ponieważ 10 - 1 (mod 9), więc a - a" + ... + ao (mod 9) i wobec
tego a = O (mod 9) wtedy i tylko wtedy, gdy a" + (!'-,_I + ... + ao = O (mod 9).
(3) Rozumując podobnie, otrzymujemy: ponieważ la = -1 (mad 11), więc a =
(al + a3 + ...) - (az + U4 + ...) (mod 11) i wobec tego liczba a jest podzielna
przez 11 wtedy i tylko wtedy, gdy różnica sumy cyfr liczby a na miejscach nie-
parzystych i sumy cyfr liczby a na miejscach parzystych jest podzielna przez 11.
DEFINICJA 7.4
Pełnym układem reszt modulo m nazywamy pelny układ reprezentantów klas
relacji przystawania moclulo m.
H. ~ lN'ZI'<tI. l""""""riIii I"" Id li< J). .. sm•• 1006
11_148SS_J. (l by WN PWN 2006
32 Wykład 4
Poda.liśmy jużprzyklad pc!nego llkladu reszt modlllo m: 0, l, ... : m-l. Są

to Ilajmniejsze Ilieujemne reszty. Jeśli chcemy, aby reszty były najmlllejsze co do
wartości bezwzględnej, to trzeba. wzi,!(; - m;-I, ... , -1,0, 1, ... , "';-1, gdy m jt."St
nieparzyste, oraz - '; + 1, ... , -1,0, 1, ... , '; lub - ;' , ... , -1,0, 1, ... , '; - 1, gdy
m jest parzyste (bo r r - m (mod m)). =
STWIERDZENIE 7.5
Jeśli(a, m) = 1 i x przebiega pełny układ reszt 7fwdulo m, to wyrażenie ax + b też
przebiegu pełny układ reszt modulo m.
Dowód
Liczb ax + b,
gdzie x przebiega pelny uklad reszt modlllo ni,jest m. Wystarczy
więc wykazać, że jeśli OXI + b =
aJ/2 + b (mod m), to Xl = 3/2 (mad m). :Jiech
aXI + b ~ aX2 + b (mad m). \Vtedy aXI ~ 1l.X2 (mad m), a ponieważ (a, m) = 1,
więc z 7.3(3) mamy XI X2 (mod m). = D
DIWINICJA 7.6
Zredukowanynl układem reszt moduło m llazywamy układ t'eprezentautów
tych kłas relacji przystawania modulo m, które składają się z liczb względnie pierw-
szych z m.
Na mocy 7.3(6) definicja 7.6 IM seus, bo jeśli (a, m) = 1 i a _ b (mad m), to

(b, m) = l. Liczbę reszt modulo m względnie pierwszych z m oznaczamy przez iP( m)
i nazywamy funkcją Eułera. Zauważmy, że jeśli m jest łiczbą pierwszą, to ip(m)
= m-L
STWIERDZENIE 7.7
(1) Dowolny układ ip( m) liczb pammi nieprzystajqcych modulo m i względnie pierw-
szych z m tworzy zredukowany układ reszt mooulo m.
(2) Jeśli (a,m) = 1 i elementy Xl,X2, ,X<p(m) tworzq zn,dukowany uklad reszt
madula m, to także elementy a."l:j, 1l.X2, , ax",(m) tworzą zl"Cllukowany uklad reszt
mad'ulo m.
Dowód
Część pierwsza stwierdzenia wynika bezpośrednio z definicji 7.6. Dla dowodu (2)
wystarczy, uwzględniai;lc (1), wykazać, że (UXi, m) = 1 oraz UXi "I- UXj (mod m),
o Ile i =F j. Ponieważ (x;, m) = l oraz (a,m) = l, więc (ax;, m) = L Załóżmy, że
aX; _ a:I:j (mod m). Zc stwierdzeuia 7.3(3) wynika, że Xi _ Xj (lJIod 1Ft), a więc
Xi "'" Xj, czyli 1: "'" j. D
W klasycznej teorii kongruencji podstawową rolę odgrywają następujące dwa

twierdzenia:
TWIERDZENIE 7.8 (Euler)

Jeśli 1ft > 1 i (a, m) = l, to
al"(m) =1 (mod m).
Dowód
Niech uklad
(I) rl,1'2, •.• ,r'f'(m)
będzie zredukowanym układem reszt modulo m składającym się z najmniej szych

nieujclImych reszt. Ku mocy stwicrdzcnia 7.7(2) uujmnicjsze lIieujcnlllc reszty PI,
... ,P",,(m) liczb aTI, aTz,.··, aT'f'(m) tworzą pennutację układu (1). l'vlnożąc stronami
kongruencje aT; _ p; (mod m) dla O < i ,,;; '1'( m), otrzymujcmy kongruencję
(2) a'f'{'n)rl ... T'f'(m) PI'" P",,(m) (mod m).
Ponieważ (r;, m) = 1 dla każdego i, O < i";; <p(m), więc
(Tl'" r",,(m) , m) = 1,
a stąd ta.kże (Pl'" P"'(m)' m) = 1. r-,'Iożemy teraz skorzystać ze stwierdzenia 7.3(3)
i podzielić kongruellcję (2) przez T] ... T<p(m) = PI ... P'f'{m)' Otrzymamy wtedy
a<p(m} ~ 1 (mod m). D
W szczególnym przypadku, gdy m = p jest liczbą pierwszą, z twierdzenia Eulera

wynika
TWIERDZENIE 7.9 (ll1ale twierdzenie Ferll1ata)
Dla wszystkich a E Z i P E IP' takich, że pł a zachodzi kongruencja
a,,-I - l (mod p).
Dowód
Jeśli p E IP i pł a, to (a, p) = l. Wiemy też, że <p(p) = p - l i wystarczy skorzystać
z twierdzenia Eulera. O
WNIOSEK 7.10
Dla wszystkich a E Z i P E IP' zachodzi kongruencja
al' - a (mod p).
Dowód
Ponieważ p E IP, więc
(a,p) = l albo pla. W pierwszym przypadku korzystamy
z małego twierdzeuia Fermata, IUnoż,!c kO!lgruellcję przez a, w drugim przypadku
a"=a=O(modp). D
,
Cwiczenia
l. Korzystając z własności kongrucncji, sprawdź, że dla każdej liczby naturalnej n:
(a) 31 1t'" -I, (b) 1311 +33"+1 +93"+1, (c) 13j42"+1 +3"+2.
2. Oblicz resztę z dzielenia 2006 2007 przez 11.
3. Czy 5 1984 = 1983 (mod 25), 7 10:> =5 (mad 27)7
Oc>.. P Z'''Z)'<ki. El..""",,,,,,,, """0 Iu-..b, "'..m .... 200ó
ll_148~S_J. tl by WN PWN 2006
34 Wykład 4
4. Znajdź ostatnie dwie cyfry Hczb 99 ", 7 9łJ.

5. Niech a = a"IO" + a"_110,,-1 + ... + allO + 00, gdzie O ,;;;;; aj ,;;;;; 9, aj E Z,
i = O, l, ... , n. \Vykaż, że 71 a wtedy i tyłka wtedy, gdy 71100az + lOal + 00
~ lODa" - IOIl.] - a3 + lOOa,; + lOa7 + łJl3 - •..
6. UdO\vodnij, że jclli m E fi oraz a =. .

b (mad m),
,
to dla dO\vołnej liczby całko-
witej n;;;' O zachodzi kongruencja am _ b'" (mod m"+ ).
7. Wykaż, że jeśH m, n E fi i m, n są nieparzyste, to
l" + 2" + ... + (m - 1)" O (mad 1Ft).
8. Które z na.stl,?pujących zbiorów stanowią pełny układ reiOzt mocllllo 11:

(a) {O,1,3,3', ... ,3"}, (b) {O,l',2', ... ,lO'}?
9. Znajdź pełny układ reiOzt moduło 17 złożony z wielokrotności łiczby 3.
10. Znajdź zredukowany układ reszt moduło:
(a) 16, (b) 47.
11. Sprawdź, że jeśli dła 00, al",,) a" E Z zbiór {oo + alXI + ... + a"xl', 00 + al:D./
+ ... + a".T~', , il(I + alXm + ... + a"x,',',} jest pełnym układem reszt modlllo m,
to zbiór {Xl, , X m } też jest pełnym układem reszt moduło m.
12. Niech m bl,?dzie liczbą nieparzystą, {XI,:D./, .. ", x",} pełnym 1lkladcm reszt mo-
duło m. Sprawdź, że L7~1 Xi O (mad m).
13. Dla m > 2 Iliech zbiór {.T], .'V2, ... , X",(",j} tworzy zredukowany układ reiOzt.
Sprawdź, że Li~~j Xi - O (mad m).
14. Zbiór {XI,:D./, ... ,X",(mJ} jest zredukowanym układem reszt lllodulo m, takim że
O <Xj<n~, l -- . l, ,if' (m,

) S pław
" di; l ",",'P(m}.
z,ze 'P(mjL..i=1 - m
Xi-2"'
15. Załóżmy, że S = {Xl, , x,.,} C Z. Wykaż, że istnieją różne wskaźniki i], 12, ... ,
ik E {l, 2, .. , , n}, takie że ni Xi, + Xi, + ... + Xj,"
16. Udowodl1ij, że jeśli (m, m') = l oraz a przebiega pełny (zredukowany) układ
reszt moduło m, a' zaś przebiega. pełny (zredukowany) układ reszt moduło m',
to am' + a'm przebiega pełny (zredukowany) uklad reszt moduło m· mi.
Wykład 5
I'81 Kongruencje (2)
Następnym faktem związanym z teorią kongruencji jest twierdzenie postulowane

przez J. \Vilsona, a udowodnione przez J. L. Lagrallgc'a.
TWIERDZENIE S.l (Wilson)

Jeśli p E P, to
(p-l)!--l (modp).
Dowód
Dla p = 2 twierdzenie jest oczywiste, bo I = -1 (mad 2). Zalóżmy więc, że p > 2.
Dla każdego 1 , ;;;; x";;; p - l istllieje dokładnie jedno (moduło p) l'Oilwiązunie x' kon-
gruencji x· x' = l (mad p). Rzeczy",dście (x, p) = I, więc na mocy tv.derdzenia 2.9
istnieją takie t, x' E Z, że xx' + tp = l. Jeduoznaczność moduło p rozwiązania x'
wynika z t\vierdzenia 4.2.
Zauważmy dalej, że x = x' wtedy i tylko wtwly, gdy x = 1 albo .T = 11 - 1.
Istotnie, ZZ - 1 (mad p) wtedy i tylko wtedy, gdy (x - l)(x + l) O (mod p),
zatem x = 1 (mad p) i wobec tego x = 1 albo x = -1 (mod p), czyli x = p-l.
Ivlnożl!c kongI"ltencje x· x' 1 (mod p), dła wS:tystkich par rozwią:tat'l x, x' takich,
że x #- x', otrzymujemy 2·3··· (1) - 2) = t (mod p). lVTnożąc ostatnią kongruencję
przez kOllgruellcję 1 . (p - 1) _ -1 (mod p), otrzylt1ujemy 1 . 2 . 3· .. (p - 1) _ -1
(Inodp). D
Uwaga 8.2
Kongrncncja 1 . 2 . 3 ... (p - l) = -1 (mad p) chumkteryz\lje liczby pierwsze, to
znaczy zachodzi ona wtedy i tyłka wtedy, gdy p jest liczbą pierwszą. Rzeczywiście,
j(,~li p = fi· T, gdzie 1 < fi < p, to q jest czynnikiem w iloczynie 1 . 2 . 3· .. (fi - 1)
i kongruencja (p - l)! + 1 O (mad q) nie jest prawdziwa, a więc i kongruencja
(p - 1)! + l = O (mod p) nie może zachodzić.
Wiemy już, że jeśli (a, m) = l, to kongruencja ax = c (mad m) ma dokładnie
jedno rozwiązanie moduło m (por. twierdzenie 4.2). Będziemy badać, ile rozwiąZali
moduło p ma kongruencja
(1 ) iJ(lX" + U1X,,-1 + ... + a" = O (mod]l),

36 Wykład 5
gdzie aj E Z, n E N i p E Ifl'. Zauważmy od razu, że tych rOZWif!Za{l jest eo uajwyżej

p, bo tyle elementów ma pelny uklad reszt modula p. Możemy zakladać, że n < p,
gdyż z Wlliosku 7.10 wyuika, że dla każdego n;;;;' p istnieje takie 111 < p, że x" xm =
(mod p) dla dowolnej liczby całkowitej x.
Przykład 8.3
1. x~ - 3 O (mod 7) nie ma rozwiflzaó.
2. x/)-[ - 1 O (mod p) ma p-l rozwiąza{i, co wynika z malego twierdzenia
Fermata (twierdzenie 7.9).
TWIERDZENIE 8.4 (Lagrange)

Kongruencja
UQx "+ alx ,,-1+ ... + _(l
a" = (mad p), gdzie (UQ,p) = 1,
ma co najwyżej n mzwiqzań modulo p.

Dowód
Stosujemy indukcję ze względu na n. Dla n = l twierdzenie jest prawdziwe, gdyż
(UQ,1)) = 1. Zalóżmy, że jest OIlO prawdziwe dla TI - L
.Jeśli kongruencja
(2) GoX" + a[x"-I + ... + a,'_I;l; + a" - O (mod p)

nie ma rozwiązaJl, to teza jest prawdziwa. Zalóżmy więc, że istnieje rozwiązanie XI,
cilyli
(3) (mod p).
OdejJllnj::!c stronami (3) od (2), otrzymujemy
(4) lJo ( X " - Xl")+ al (,,-1
x - x["-1)+ ... + (
(1.,,-1 X - Xl )-0
= (mod p).
Kongruencja (4) jest spelniona przez każde rozwiązanie kongruencji (2). Korzysta-
jąc ze wzoru x k - xf = (x - xJl(X k - 1 + x k - 2Xl + ... + xx~-2 + X~-l), kongruencję
(4) możemy ilapisać w postaci
(5)
gdzie b1 , b:!, ... , b"_1 są
liczbami całkowitymi zależącymi tylko od XI oraz UQ, al,· .. ,
a,,_I. Stąd każde rozwiąilanie kongruellcji (2) powinno albo spełniać kOllgruencję
x = Xl (mod p), albo być rozwiązaniem kongruencji
b ,,-2
UQX ,,-1 +lX b - O ( mOll'.
+ ... +,,-1= j)
Na mocy zalo:;ienia indllkeyjnego ostatnia kOllgruellcja nic ma wi~cej niż n-l

rozwiązań, a więc kongruencja (2) nie ma więcej niż n rozwiązań, co dowodzi praw-
dziwo~d twierdzenia. D
Z twierdzenia Lagrange'a można otrzymać kryterium na to, kiedy liczba cal-
kowitll a jest tak ZWaIH! resztl! kwadratawf! modulo TJ.
DEFINICJA 8.5
Niech p będzie liczbą pierwszą. rVlówimy, że liczba całkowita a jest resztą kwa-
dratową ll1odulo p, jeśli (a, 1') = 1 oraz istnieje liczba całkowita x taka, że a x2 =
(mod p). Jeśli kongruencja ta nie ma rozwiązania, to liczbę a nazywamy nieresztą
kwadratową modulo p.
Niech p będzie liczbą pie7wszą nierHl7'zystą i a E Z. Kongruencja
a~ _ 1 (mod p)
jest pmwdziwa wtedy i tylko wtedy, gdy a jest resztą kwadmtową 7fwdulo p.
Dowód
Przypuśćmy,że istnieje x takie, że a =
x 2 (mod 1'). \Vtedy (x, p) = l, bo (a, p) = 1.
Podnosząc obie strony ostatniej kongruencji do potęgi 1';1, otrzymujemy
1 Ł.=..!
x Jl - - a' (mod p).
Z twierdzenia Fermata wiemy, ze X!J-l - l (mod p), a 'vięc a~ - 1 (mad p).
Na odwrót, zalóżmy, że kongruencja ae;' - 1 (mad p) jest prawdziwa. Z twier-
dzenia Lagrange'a (twierdzenie 8.4) wilotdomo, że kongruencja x-,
=l
1 (mod 1') =
może mieć co najwyżej 1';1 rozwiązail moduło p. Ale istnieje dokładnie r;l reszt
kwadratowych spełniających to równanie, a mianowicie 12,22,32, ... , (r;I)2. Rze-
czywiście, liczby te uie pt'zystaj'l do siebie modulo p, bo jeśli l' i- s i 1'2 S2
(mod p), to albo l' =
s, albo l' =
-s (mod p), co nie jest możliwe, gdyż l ,,;;; T,
S ,,;;; r;l. Wynika stąd, że kongruencja xŁT- _ 1 (mad p) ma tylko rozwiązuuia
będące resztami kwadratO\vymi, co kOIlczy dowód twierdzenia. D
Następne twierdzenie o kongruencjach jest trochę innego typu niż poprzednie.

łvla ono charakter bardzicj ogólny w tym scnsic, żc może być przcfoflłmłowanc na
twierdzenie o wlasnościach ideałów w pierścieniu.
TWIERDZENIE 8.7 (chińskie twierdzenie o resztach)

Niech n będzie liczbą naturalną n ;. 2, mI, m2, ... ,m" zaś ukladem n liczb natu-
ralnych, taJ."ich źe (mi, mJ = 1 dla i i- j, oraz al, Q.z, •.• , a" dowolnym ukladem n
liczb calkowitych. Wówczas istnieje wspólne rozwiązanie kongruencji
x = ai (mod mi) dla i=1,2, ... ,n.
Uozwiązanie to jest jedyne modulo mI ... m".
Dowód
Oznuczlny 7ft = l1tl'" Tn". Ponieważ (~,
m, rni) = 1, WięC na mocy lwierdzenia 4.2
istnieje liczba x, taka, że
'" = 1 (mad m;).

-Xi
mj
Oczywiście ::.~ Xi - O(mod mj) dla j i- i. Przyjmując 7b = L:'=I ,: Xi aj, otrzymu-

Jcmy
38 Wykład 5
m
",=-x,a;=a; (modm;), i=1,2, ... ,n,
m;
co dowodzi pierwszej części twierdzeuia.
Załóżmy, że Xl jest innym rozwi~!zanicm rozważanego układu kongruencji.
Ponieważ:11:) XI (mod m;), dla i = 1,2, ... , n, więc ze stwierdzenia 7.3(5)
otrzymujemy :lO =
Xl (mod utl'" m,,), co dowodzi prawdziwości drugiej CZęsCl
twierdzenia. O
,
Cwiczenia
1. Sprawdź, że dla dowołnej łiczby całkowitej n:
(a) ,,7 ,,(mod 42),
(b) tn5 + kn + 17:; n jest liczbą całkowitą.
3
2. Oblicz resztę z dzielenia:

(a) 5 138 przez 11, (b) n lOO przez 125.
3. Sprawdź, że:
(a) 2· 26! -1 (mod 29), (b) 18! -1 (mod 437).
4. Załóżmy, że p, 1/ E ]P" {2} oraz 1) - 111/ - 1. Wykaż, że jeśłi ((1,1)1/) = 1, to
aq - l
- l (mod pq).
5. Niech p, q będą różnymi liczbami pierwszymi oraz al' a (mad q) i a'l a

(mod p). Wykaż, że a1"1 = a (mod pq).
6. Przyjmując a = 2, p = 11, q = 31 i korzystając z Ć\viczenia 5., sprawdź, że
twierdzCllic odwrotllC do małego twierdzCllia Fcnnata (twierdzcnic 7.9) nic jcst
prawdzl\ve.
7. Udowodnij, że jeśli p jest liczbą pierwszą nieparzystą, to dła k = 0,1, ... ,p - 1
zachodzi kongruencja (Pk l) (_l)k (mod p). =
8. Sprawdź,ze dła dowołnej liczby pierwszej p zachodzi kongruencja (p - l)! _
l)-l(mod 1+2+ ... +{p-1)).
9. Nk"Ch Xl,X2, ... ,XI'-l b,dzie zredukowanym ukladem reszt lllodulo p, gdzie
p E P. Sprawdź, że Xj nrl
-1 (mod p).
10. Udowodllij, że jeśli p jest Iiczb~l pierwszą postaci 4k + 3, to (!(p - l))! 1
(mod p) albo O(p-l)) -l (mod p). =
11. Wykaz, że 511" + 2" + 3" + 4" wtedy i tyłko wtedy, gdy 4fn.
12. WykaZ, że jeśli p E IP" {2, 5}, to p dzieli uieskOliczenie wiele wyrazów ci11gu 1,
11,111,1111, ...
13. \Vykaz, że w CIągu 10" + 3, n - 1,2, ... , istnieje niesko6czenie wiele liczb
złożonych.
l'_148SS_J. (l by WN PWN 2006
14. Sprawdź, że jdli (a, m) = 1, to x = b· a",,(m)-l jest rozwiązaniem kongruencji

ax - b (mad m).
15. Rozwią,;; rw.st~plljące kongmencje:
(a) =
2gx 1 (mad 17),
(b) 21x + 5 O (mad 29),
(c) =
3x 4 (mod g),
(d) 6x 14 (mad 22),
(e) (a + b)x =
a2 + b2 (mod ab), (a,b)~I,
(f) (a 2 +b2)x a-b (modab), (a,b)~I,
(g) (a + b)2 X =
a 2 - b2 (mod ab), (a,b)~L
16. Sprawdź, że jeśli Yo jest rozwil!zaniem kongruencji my -b (mod a), to wtedy

:l{) = "'!'!~+b jest rozwiązaniem kongruencji (IX b (mod m). =
17. Zastosuj ćwiczenie
16. do rozwiązania następujących kongruencji:
(a) 863x 8S0 (mad 2151),
(b) 5Sgx = 509 (mad S17),
18. Znajdź najmuiejszą liczbę naturaluą, która przy dzieleniu przez
(a) 3,5, 7 daje odpowiednio reszty 2, 3, 2,
(b) 3,5,7,9, J l daje odpowiednio reszty 1, 2, 3, 4, 5.
19. Korzystając z chiliskiego twierdzeltia o resztach (twierdzenie 8.7), rozwiąż kon-
gruencję 19x = l (mod 140).
20. Wykaż, że kongruencje x a (mad m) oraz x b (mod u) mają wspólne
rozwiązanie \vtedy i tylko wtedy, gdy a = b (mad (m, n)).
21. \Vyznacz reszty kwadratowe dla

(a) p ~ 13, (b) p ~ 23.
22. Niech p E lP'" {2}, a, b, c E Z, (a, p) = 1. Sprawdź, że kongrllencja ax 2 + bx + c
= O (mad p) jest równowa,;;na kongruencji (20x + b)2 = b2 - 4ac (mod p).
23. Zbadaj, czy następujące kongruencje mają rozwiązania:
(a) x 2 _ 3 (mad 31), (d) 4x 2 + 2x + 1 _ O (mad 5),
(b) x 2 - 2 (mad 257), (e) 2x 2 + 7x - 10 - O (mod 11),
=
(c) x 2 5 (mad 23), (f) x 2 + x - 1 O (mad 13). =
24. Rozwiąż kongruencje
(a) x + 7x + 11 - O (mad 5),
2
(c) x 2 -1 (mod 29),
(b) x 2 -3x+3=O (mod 7), (d) x 2 = -1 (mad 37).
25. Wykaż na przykladzie, że twierdzenie Lagrange'a (twierdzenie S.4) nie jest
prawdziwe dla modulów złożonych.
26. (a) Udowodnij tożsamość xp- l
- 1 (x - 1)(x - 2)··· (x - p + l) (mad p),
gdzie p E rP'.
(b) Korzystając z (11), podaj inny dowód twierdzenia \Vilsona (twierdzenie S.l).
40 Wykład 5
Zadania
37. Znajdź wszystkie trójki a, b, e E N spcłniaj~!ce kongrucm;je: a =b (mod e),

b c (mad a), e a (mad b).
38. Udowodnij, że każda liczba calkowita spelnia co najmniej jedną z sześciu kon-
=
gruencji: x O (mad 2), x =
l (mad 4), x 3 (mad 8), x =
l (mad 3), x 3 = =
(mad 12), x =
23 (mod 24).
39. Dla dowolnej liczby naturalnej n Zllajdź trzy ostatnie cyfry liczby n HXJ •
40. Wykaz, że jeśli al, 1»2, .•. , ar, E Z, m E N, m > n, to istnieje r E N takie, ze
rnła;+r,i=1,2, ... ,n.
41. Wykaż, ze dla każdego n E N istnieje takie k E N, że w zapisie dziesiętnym
liczuy n . k występują tylko cyfry 1 lub o.
42. Liczba naturalna n ma tę własność, że wśród dowołnie wybranych n liczb na-
turałnych znajdą się dwie, których suma łub różnica jest podzielna przez 111.
Jaka jest najmlliejsza liczba naturalna o takiej własności?
43. Dla a, b E N, a > b, (a, b) = l, ciąg SI, S2, .•. konstruujemy następująco: SI = a,
dla k = 1,2, ...
Sk+ a. gdy Sk < b,
S~'+I = .
{ Sk - b, gdy Sk;;;;' b.
Wykaż, 7.e zbiór {Si>""aa+b} jest pełnym układem reszt moduło a + b.
44. Niech a, b E N, a = 2°S P m, (m, 10) = 1. Udowodnij, ze rozwinięcie dziesiętne
ulamka ~ ma okres, którego długoM: dzieli liczbl( If'( 111). Sprawdź, że jdli ulamek
ten nie ma okresu o dl ugości mniejszej niz m ~ l, to m jest liczbą pierwszą.
45. Dla p E IP funkcję f(x) = (1- X)-I) rozwijamy w szereg Maclaurina (1- X)-I) =
Co + Cl x + C2X2 + ... Wykaż, że
c. =
,-
{l (mod p),
O (mod l)),
gdy
gdy
pl i,
pł i.
46. Niech ]I będzie liczbą pierwszą. większą od 3 i niech

f(x) ~ (x - 1)(x - 2) .. · (x - p + 1).
47. Dane są dwa llicskOl'ICZOllC ci~!gi roslll/ce liczb naturalnych: geometryczlly o ilo-
razie q i arytmetyczny o różnicy r. Udowodnij, ze jeśli (q, r) = l oraz ciągi te
mają przynajmniej jcdell wyraz wspólny, to mają nicskOl1czenie wiele wyrazów
wspólnych. Pokaż na przykladzie, że założenie (q, r) = 1 jest istotne.
48. Wykaż, że jeśli p E IP" {2}, to:
z=..!
(a) 12·3 2
.. (p-2) 2 -(-1)' (mod p),
(h) 2 2 .4 2 "'(p_l)'=(_1)'" (mod p).
l<" ~ ,_j.
L"VZ)'<ki. El"••,",""",
I~-:b. W........... 2Q(l()
49. Wykaż, że jeśli 1) jest lIieparzystą liczrn! pierwszą oraz a + b = p-l, to
a!b! + (~l)" - O (mod p).
50. Udowodnij, że dla wszystkich n E N i P E P
(n;) = n (mod p') .

51. Wykaż, że ciąg ostatnich cyfr liczb nil• jest okresowy.
52. Udowodnij Ilast~plljl!ce uogólnienie twierdzcnia Eulera (twierdzenia 7.8): Jeśli
a E Z, m E N, to a'" = a"'-';("') (mod m).
53. Udowodnij nast~pujące uogólnienie twierdzcnia Eulcra (twierdzenia .6): Jeśli
p E P, (a,p) = J, n E N, to kongruencja z" - a (mod l') ma rozwiązanie
wtedy i tylko wtedy. gdy a7! = l (mod p). gdzie d = (n. p - l).
54. Kor.l)·stając Z faktu, że jeśli K jest cialem, to pierś<:ieiJ KizI jest dziedziną
calkowitości, podaj iuny dowód twierdzenia Lagrange'a (twierd....cnie 8.4).
55. \\'ykBŻ, żekongruencja f(x) =

O (mod p), gdzie p E P, f(x) = ao + alX +
... + x" E Zlxl, degf < 1', ma n rozwiązali wtedy i tylko wtedy, gdy x P - z
= f(z)q(z) + pr(x), gdzie q, r E Z(xJ oraz deg r < n.
Wykład 6
I '91 Rozwiązywanie kongruencji
Przedstawimy teraz metodę rozwiązywania kongruencji f(x) O (mad m), gdzie

f jest wielomianem o współczynnikach całkowitych. l'vletoda ta opiera się na al-
gebraicznych własnościach zredukowanego układu reszt. Przez Wrn oznaczać bę
dziemy zredukowan}' układ reszt modulo nt, który składa się z elementów zbioru
{O, 1, ... ,m ~ l} względuie pierwszych z JIt.
TWIERDZENIE 9.1
Zbiór W m Z mnożeniem mot/ulo m jest. grupą przemienną.
Dowód
Przez 'm oZIl1\czać będziemy lllllożellie ll1odulo m. Oznacza to, że dla elementów
a, b E Wrn element a' m b jest resztą z dzielenia a· b przez m. Oczywiście a'", b E Wrn.
Działanie "fil jest h!czne:
(a·",b)·",c=(a·b)·c (modm),
(L,,,,(b'mc)-a·(b·c) (modm),
W\(;I;
(a·", b)·", c-a·",(b·",c) (modm).

Poniewa~ (a '", b) 'm c, a'", (b 'm c) E W"" to (a '", b) 'm C = a',,, (b ',,, c). Elementem
neutralnym działania'm jest liczba I. Jeśli a E W"" to (a,m) = 1, wobec tego
istniej'l liczby calkowite x, y takie, ~e ax + my = 1. Łatwo sprawdzić, ~e reszta
z dzielenia x przez m jest elementem odwrotnym do a. Przemienność działania 'm
jest oczywista. O
TWIERDZENIE 9.2
Dla dowolnej liczby pienvszej p gntpa (Wp, '1') jest cykliczna.
Dowód
Dla l) = 2, Wp = {I}. Niech p > 2; ponieważ rz<!d grupy Wp wynosi p - l, WięC
wystarczy znaleźć w Wp ełement rzędu p - \.
Dla dlp - l przez Sd oznaczmy zbiór
S,J={xE W,,:rz'1Ox=d}.
9. Rozwiązywanie kongruencji 43
\Vystarczy SI'_I -=I=- 0.

wykazać, że
Zauważmy, że zbiory Sd mają dwie oczywiste własności:
(I) d" d' ",. Sd n Sd' ~ 0,
(2) Udll'-l Sd = Wp.
Załóżmy, że zbiór Sd jest niepllsty. Znajdziemy liczb~ elementów takiego zbioru.

Łatwo sprawdzić, że jeśli 211 E Sd, to elementy 1,211,:tJ, , xi-I są różne i spel-
niają równanie x - l = o. Wiadomo, że zbiór {O, 1,
d , p - l} z dodawaniem
i ltlllOŻelliem madula p jest cialem, stąd wielomian Xii - 1 ma w tym ciele co naj-
wyżej d pienviastków. \Vynika stąd, że pierwiastkami tego wielomianu są elementy
1,.11),:rJ, ... ,xi-l. Ponadto, z określenia rzędu elementu, otrzymujemy
5,1 C {l, IQ, 115, ... , xi-l}.
Sprawdzimy teraz,,;;e rZ11d elementu TJ wynosi li wtedy i tylko wtedy, gdy (k, d) = 1:
jeśli (k, d) > 1, to znaczy k = kl(k, d), d = dl(k, d) oraz dl < d, wówczas
(TJ)'" = (~),(k.d})d' = (~)k, = 1;
jeśli (k, d) = 1, to z (~r = 1, gdzie s"-;; d, wynika, że dlks;
zatem dis, czyli uajllllliejsze s jest równe d.
Otrzymaliśmy
jeśli Sil 0, -=I=-
jeśli Sd = 0.
(I) p~l~ IV,~ U Sd~ I: Sd<; I: ",(d),

dlp-l dlp-I dlp-I
Wykażemy teraz, że L:dll'-I If'( d) = p-l. Kieell k E {l, ... , p-l}, (k, 1)-1) = d.
Wówczas (~, Pd"I) = 1, zatem ~ E W 7- i k = d . ~ E d· W 7-" gdzie zbiór d· W ~
powstaje ze zbioru W 9 przez pomnozenie każdego jego elementu przez d. Ponadto
{l, 2, ... ,p - 1) ~ U d· IV'7"

dll'-l
gdzie ostatnia SUllla jest rozłączna. \Vynika stąd, że
(2)
Z (1) i (2) otrzymujemy
p-I ~ I: Sd <; I: ",(d) ~ p-l.

d p-l dlp-I
Zatem 51'-1 = I.{!(p - l) -=I=- O, a to zw:u;zy, że grupa Wp jest cykliczna. D

44 Wykład 6
Uwaga 9.3
Korzystaj'lc z twierdzenia 9.2, podamy inny dowód małego twierdzenia Fennata
(twierdzenie. 7.9).
Ponieważ (a, p) = 1, wi~ a = al (mod p) dla pewnego al E Wp' Niech g b~lzie
generatorem grupy Wp' Wówczas al - g' (mod p) oraz
1
aP- = a\,-l = (g')I'-1 = (gl'-lr = l' = J (mod p). D
INDEKSY
Kongruencja ar ~ l (mod m), gdzie rn E H, a E Z, posiada rozwiązanie wtedy
i tylko wtedy, gdy (a, m) = l; w tym przypadku roZ\vi<F,wiell1 jest na przykład
x = rp(m) (por. twierdzenie Eulera 7.8). ,1e~eli !p(m) jest najmniejszą liczbą na-
turalną, spelniającą powyższą kongruencję, to mówimy, że a jest pierwiastkiem
pierwotnym modulo m.
Zauważmy, że stwierdzenie, i~ istnieje pierwiastek pierwotny modulo mjest rów-
noważne twierdlleniu, że grupa Wrn liczb wllględnie pierwszych z m i nie większych
od m z dzialauielll uwożenia modulo ut jest cykliezlla. Następuj'lce twierdzellie
podaje pełną charakterystykęmodułów, dla których istnieją pierwiastki pierwotne:
TWIERDZENIE 9.4
Grupa Wrn jest cykliczna wtedy i tylko wtedy, gdy m = 1,2,4, p", 2p", gdzie p jest
dowolną, liczbą pierwszą, nieparzystą" n dowolną, liczbil nat'ILm1ntl'
Dowód tego twierdzenia można znaleźć w [1] (rozdzial 8., t\vierdzellie 8.10) lub
w [51 (rozdział 2., twierdzenie 2.25), lub w [12] (rozdzial 6.).
Zalóżmy, że dla liczby naturalnej m istnieje pierwiastek pierwotny r modulo
m, niech a E Z, (a, m) = l. Z cykliczności gmpy Wrn wyuika istniellie najmniejszej
liczby n E N U {O} takiej, że r" - a (mod m). Liczbę tę nazywamy indeksem
liczby a modulo m przy podstawie r i oznaczamy przez inora.
WLASNOŚCI INDEKSU
(1) indrl = 0, lndrr = 1,
(2) ind,.(ab)=indra+indrb (mod!p(m)),
(3) indr(a k) = kindra (mod rp(m)), k E N.
Zauważmy, że indeksy mają własności podobne do logarytmów.
Podamy teraz przykład ilustmj,!cy zastosowanie pojQóa indeksu przy rozwią
zywaniu kongruencji.
Przykład 9.5
Kongruencję x 9 - 12 (mod 13) rozwiązujemy w następujący sposób:
1. W tablicy indeksów ([12], s. 197) znajdujemy następujące dane: pierwiastek
pierwotuy modulo 13: r = 2, ind z12 = 6.
2. Z wła~;uości illdeksów wynika, że kongmetlcja x 9 _ 12 (mod 13) jest rówIIO-
ważna kongTuencji 9 ind 2 x - ill(h12 = 6 (mad 12). Wystarczy teraz rozwiązać
kongruencjI( 9 incl2x = 6 (mod 12).
9. Rozwiązywanie kongruencji 45
3. Podstawiamy y = ind 2 x; 9y =6 (mod 12) <=} 3y =2 (mod 4) <=} Y =2

(mod 4).
Zatcnłindzx = 2,6,10, a stl~d, odezytuj,!e z tabłicy indeksów, otrzymujemy
x 4,12,10 (mad 13).
,
Cwiczenia
1. Znajdź pierwiastki pierwotne modliło 13 :l.awarte w zbior:l.e {l, 2, ... , 12}. Ko-
rzystając z ta blky iIHira dla a = l, 2, ... , 12, wykaż że:
l (mad 13), gdyn=4k,

5" _ 5 (mad 13), gdy n = 4k+ 1,
(a)
12 (mod 13), gdy 11 = 4k + 2,
8 (mod 13), gdy 11 = 4k + 3,
l (maci 13) , gdy n = 3k,

(b) 29" ={ 3 (mad 13), gdy n = 3k + l,
9 (mad 13), gdy n = 3k+2,
2. Znajdź wszystkie pierwiastki pierwotne moduło 111 oraz oblicz ich iloc:l.yn mo-
dulo m, gdzie m jest równe:
(a) 3, (b) 5, (e) 7, (d) 11, (e) 17, (f) 25.
3. Roz\viąż kongruencje:
(a) 4x 9 = 7 (maci 13), (e) 9xs = 8 (maci 17),
(b) x:J = 4 (mod 13), (f) 8x 5 = 10 (mad 17),
(c) x 8 - la (maci 11), (g) 7' - 7 (mod 17),
(d) x lZ = 13 (mod 11), (h) 9' = 2 (mod 17).
4. Wykaz, że liczba pierwiastkó\v pierwotnych modula m jest albo równa O, albo
'P ('P(m)).
Wykład 7
10 Własności liczb pierwszych (l)
W wykladzie pierwszym wykazaliśmy, że zbiór liczb pierwszych ]J jest nicskoó-

czony (twierdzenie 3.8.). Teraz opiszemy szereg innych własności liczb pierwszych,
Na począ.tku podamy pCWllC podzbiory zbiorn liczb naturalnych zawierające nic-
skOllczenic wiele liczb pierwszych,
TWIERDZENIE 10.1
Istnieje niesk01iczenie wiele liczb pierwszych lJoslaci 4k - L

Dowód
Załóżmy przeciwnie, że {q], Q2, . , . , ąr} jest zbiorem wszystkich liczb pierwszych
postaci 4k - 1. Przyjmijmy
N = 4qllJ'l ... qr - 1.
Ponieważ N jest liczbą nieparzystą, więc dzielniki liczby n są nieparzyste. Ale każda
liczba nieparzysta ma postać 4k - 1 lub 4k + 1. lloczyll liczb postaci 4k + l jest
tez Hczbą postaci 4k + l, więc n musi mieć dzielnik pierwszy q postaci 4k - 1.
Oczywiste jest, że ql ł N, lJ2 ł N, ... , qr ł N, zatem q fJ: {ql, 1J2, ... , q,.}. Otrzymana
sprzeczność dowodzi słusznośd twierdzenia. D
Liczbami pierwszymi postaci 4k - 1 Sft: 3, 7, 11, 19,23, 31, ... :'-Jieco tmdniej
jest udowodnić tę samą własność dła zbioru liczb postaci 4k + 1.
TWIERDZENIE 10.2
Istnieje nieskoliczenie wiele liczb pierwszych lJOstaci 4k + l.

W dowodzie wykorzystamy lła.';t~p\ljące twierdzenie, którego dowód podamy
w wykładzie 10.
TWIERDZENIE 10.3
Jeśli n, A E N i nlA 2 + l, to istnieją takie liczby całkowite s oruz t, źe n = S2 + e,

przy czym (s, t) = 1.
Dowód twierdzenia 10.2

Załóżmy przeciwnie, że {ql, (I':!, ... , q,.} jest zbiorem wszystkich łiezb postaci 4k + 1.
10. Wlasności liczb pierwszych (l) 47
Przyjmijmy
N = (2q1fJ2'" qr)2 +L
Ponicważ N jcst liczbą nicparzyst<h wil,?c dzielniki liczby N są też nieparzystc.
Z twierdzenia 10.3 wynika, że każdy dzielnik pierwszy p liczby N można przedstawić
w postaci p = S2 + t 2 . Ponieważ liczba p jest nieparzysta, to jwlna z liczb s, t musi
być parzysta, a druga nieparzysta. Niech na przyklad s = 2i, t = 2j + 1. \Vtedy
p = 4i 2 + 4P + 4j + 1 = I (mod 4), więc każdy dzielnik pierwszy p liczby N
ma postać 4k + 1. Ponieważ IJI ł N, ą.2 ł N, ... , IJr ł N, zatem 1) 1:- {ql, fJ2, ... , qr}'
Otrzymana sprzeczność dO\vodzi słuszności twierdzenia. D
Twierdzenia 10.1 i 10.2 są szczególnymi przypadkami następującego twierdze-

ma:
TWIERDZEN18 10.4 (Dirichlet)

Jeśli 1ft E N, a E Z omz (a, m) = l, to W ciągu a7ytmetycznym a + mk, gdzie
k = 1,2, ... , istnieje nieskończenie wiele liczb pierwszych.
Dowodu tego twierdzenia nie podajemy, jest on trudny i nieelementarny. :V[ożna
go Jlualcźć np. w [2] (roJldział 10.) lub w [4] (rozdzial 5.).
Innym zagadnieniem zwi,panym z liczbami pierwszymi jest problem oszacowa-
nia wielkości liczby Pll, gdzie l)n jest n-tą z kolei liczbą pierwszą.
STWIERDZENIE 10.5
Niech P" będzie n-tą z kolei liczbą ln:erwszą. Wtedy
dla n ;" 1,
1)TZy czym
dla n > L
Dowód
Załóżmy indukcyjnie, że Pl';;;; 2, 1'2';;;; 2 2 , P'J';;;; 2 1, ... , P,,';;;; 22"-1. Wtwly z przy-
toczolIego dowodu twiel'dzellia Euklidesa o uiesko1łczollości zbioru liczb pierw-
szych (twierdzenie 3.8) v,'iemy, że
1)"-1 ,;;;; P", ,;;;; Pl ... P" + l,
gdzie PUl jest liczbą pierwszą dzielą<':l! Pl ... lJ" + 1. Stąd
P"+1 ,;;;; Pl ... p" + 1 < 21+2+ .. ·+2"-1 + l < 2 2",

co na mocy zasady indukcji dowodzi słuszności naszej tezy. D
Oszacowanie w stwierdzeniu 10.5 moina trochę polepszyć, u.żywajllc liczb Fer-
mata.
DEFINICJA 10.6
Niech n E N. Liczbę
F" = 2 '" + l, gdzie n ;;. 1.
nazywamy n-h! liczb,! Fermata.
48 Wykład 7
Fermat zauważyl, ze FI = 5, F2 = 17, F:J = 257, F4 = 65537 są liczbami

pierwszymi i postawił hipotezę, że F" E lP' dla n ;" l (byłby to efektywny wzór na
nieskolk7.0ny ciąg liczb pierwszych). Euler wykazal jednak, że F5 dzieli się przez
641. Obecnie, w dobie komputerów, rozkład liczby F s na czynniki pierwsze (Fs =
641 ·6700417) najprostszym komputerom zajmuje kilka sekund. Jednakże w XVIII
wieku wynik Eulera byl sensacją. Przedstawiamy dowód tego faktu podany przez
G. Benneta.
STWIERDZENIE 10.7
Liczba Fermata F5 jest liczbą złożoną.
Dowód
Liczba F s = 22 " + l = 2:12 + l = (2· 2i )4 + 1. Przyjmując 2i = a i 5 = b,
otrzymujemy Fi) = (2a)4+1 = 24a 4 + I. Dalej 24 = I +3b = 1 +b·(a- b:l), a więc
F5 = (1 + ub - b4) . a4 + l = (1 + ab)[a 4 + (1 - ub)(1 + a 2b2)J. Stąd liczba 1 + ab
(równa 64 I) dzieli Fs . D
Liczby Fermata F" są zlożone dla 5 OS;; n OS;; 24 (por. [3], s. 27-31). Istnieje przy-
puszczenie, że tylko dla sko!lczellie wielu liczb naturalnych n liczba F" jest pIerw-
sza. nlktol"yzacja (rozkład na czynniki pierwsze) liczb Fermata stała si~ swoistym
testem dla różnych algorytmów faktoryzacji liczb całkowitych (por. [13], podroz-
dział 2.3).
vVspomniane oszacowanie n-tej liczby pierws.-.ej }I" ma następuj,!cą postać:
TWIERDZENIE 10.8
Jeśli p" oznacza n-tą liczbę pierwszą, to p" OS;; 22 "-'1 + I.
Dowód
Dla n = l otrzymujemy Pl = 2 .;.;:; J2 + l, dla n = 2 mamy P2 = 3 .;.;:; 2 1 + 1.
Załóżmy, ,;;e n :;;;. 3. Zamvażmy, że jeśli i =I:- j, to (Fi, Fj) = l (por. ćwiczenie 12( a) na
s. 12). \Vynika stąd, że każda z liczb Fermata FI, F2, . .. , F"_2 jest podzielna przez
lic.-.bę pierwszą niepar.-.ystą, która nie d.-.ieli pozostałych liczb Fermata. Ponieważ
2"-2
2ł Fl, F2, ... , F"_2 oraz 3ł Fl, F2, ... , F"_2, więc p" .;.;:; F"_2 = = 2 + 1. D
Jeszcze innym zagadnieniem związanym z liczbami pierwszymi jest problem
ilości liczb pierwsLlych nie więbzych od dallej liczby naturalnej n.
DEFINICJA 10.9
Przez 1T(X), gdzie x jest dowolną liczb,! rzcczywistJ:!, oznaczamy ilość łiczb pierw-
szych mniejszych lub równych x.
Nie jest znany prosty wzór, pozwałający wyznaczać wartości funkcji 1T{X) w za-
leżności od x, ale istuieje głębokie twierdLlellie opisujące asymptotyczne zachowauie
się 1T(X), czyli szybkość wzrostu 1T(X), przy x _ 00, w porówJlaniu z szybkością
wzrostu pewnych klasyczllych funkcji. Twierdzeuie to zostało sformulowane przeLI
P. Czebyszewa w 1849 roku, a pelny dowód podali niezależnie J. Hadamard oraz
Ch. de ła Vallće Poussin w 1896 roku.
l<" ~ ,_j.
L"VZ)'<ki. El"••,",""",
I~-:b. W........... 2Q(l()
10. Własności liczb pierwszych (1) 49
TWIERDZENIE 10.10 (o rozmieszczeniu liczb pierwszych)
!im
.(x) - l
z-ocxjlogx- ,
gdzie log x jest logarytmem lJrzy lxxlstawie c.
Dowód tego twierdzcnia, w którym korzysta się z wlasności fuukcji analit)'c~
nych i twierdze!'1 o trausfonllacic Laplacc'a, można znaleźć w [21 (rozdział 11.) lub
w [41 (rozdział 5.). \\' 19·19 roku A. Selberg i P. Erdós niezaleinie podali elcmcn·
tamy dowód twicrdzcnia o rozmieszczeniu liczb picnvsz)'ch.
Wykład 8
11 Własności liczb pierwszych (2)
Jednym z kroków w rozważaniach Czcbyszcwa dotyczących twierdzenia IQ.10 był,

udowodlliony przez niego, tak zwany postulat Benranda.
TWIERDZENIE 11.1 (postulat Bertranda)

Dla każd~j liczby nalumlnej n istnieje laka licz/m ]Jienllsza P, że n < 1) :os;; 2n.
Dowód tego twierdzenia, choć może być przeprowadzony elemelltarnie (por. [7)
rozdział 3., § 3, [21 rozdział 7., twierdzenie 4.), jest dość skomplikowany. Piękny
dowód postulatu BertralIda podal P. Erdos, można go znaleźć w [61. Zauważmy,
ze postulat Ilertranda pozwala otrzymać znacznie lepsze oszacowanie n-tej liczby
picrwsLlcj niż oszacowauic ze stwierdzenia 10.8.
STWIERDZENIE 11.2
Niech p" będzie n-tą liczbą pierwszą. Wtedy p" < 2" dla n;;' 2.
Dowód
Stosujemy indukcję ze względu na n. Jeśli n = 2, to P2 = 3 < 22 , Zaló:!;my praw-
dziwość tezy dla n. \Vykażemy, że Pn+l < 2 n +l. Z postulatu Berhanda wynika
istnienie liczby pierwszej p takiej, :!;e 2" p" i wobec tego p:;' P,,+I' Ostatecznie otrzymujemy
1),,+1 ~ I' < 2,,+1. O
\Viadolllo, że szereg harmoniczny L"EN ~ jest rozbieżny. Jeśli rozpatrujemy

szeregi typu L"EA~' gdzie A C Fi, to okazuje się, że na przykład szereg L"EP ~
jest rozbieżny. łI'lówi o tym następne twierdzenie, którego dowód jest także lHlali-
tycznym dowodem nieskOllczoności zbioru liczb pierwszych.
Sumu LpEP * iloezyn nrEP (1 - *) -I są rozbieżne.

i
Dowód
\Vykażemy najpierw, że iloczyn nPEP( 1 - *) -I jest rozbiciny. Niech P(x), S(x)
JI_ ,4on_j,e 8j' WN rw H ROS
11. Wlasności liczb pieIWszych (2) 51
będ}! fun kejami zmiennej rzeczywistej x określonymi następująco:
P(x) ~ II (,- pl)~' S(x) ~ L-pl dla x ;;;. 2.

p~x p~x
I'EP I'EP
Dla liczby rzeczywistej u, takiej że O ':",;--,':".-= 1 +u+ 11.
2
+ ... + 'lt m.
Przyjmując u = f" gdzie TJ E IF', otrzyumjemy
Jeśli m jest tak duże, że 2'" ;;;. x, to

l 1
' ') l.t -,
II ( l + -TJ + ... + -TJ'" ~ '"
~ n
I'~:r "",,1
gdyż każda liczba naturalna l < n :s;;; [x] ma w swoim rozkladzie kanonicznym
tylko liczby pierwsze p :s;;; .T, a nierówność 2'" ;;;. .T gwarantuje, że po rozlożeniu
lewej strony na sumę, kaidy skladnik prawej strony wystąpi także jako składnik
lewej strony tej nierówności. Tak więc
[xJ+l
[xl 1
P(x) > L -n > J•
dn
- > log x,
,,=1
II (1 - -
p
') -, = lim P(x) =
x--+oo
00.
I'EP
Wykażemy teraz rozbieżność szeregu LI'EP f,. Dla O Jog
p
(1)-'
l~-
p
1
2TJ(p
Sumuj'lc tcraz powyższą nierówność po wszystkich p O;;; x, uzyskujemy
00
l 1 1 1
S(x) > log P(x) - - ' " ( ) > log P(x) - - ' " ( )
2~Pl)-1 2~nn-l
~ lo" P(x) - -.
, p~x ,,=2
o 2
52 Wykład 8
gdyż
1
'\' -1
~n(n-1) - .
,,=?
Stąd S(x) > log log x - ł i LPEP f, = lim"'...... "" S(x) = 00. o
Zauważmy, że w dowodzie nie skorzystaliśmy z faktu, że zbiór li" jest nieskoll-
Cllony.
Rozpatrzymy różne typy liczb pierwszych.
DgFINICJA 11.4
Liczby pierwsze p i q = 1) + 2 nazywamy liczbami pierwszymi bliźniaczymi.
Przykladami par liczb bliźniaczych są: 3, 5; 11, 13; 1949, 1951; 4967, 4969;
1000000000061,1000000000063. Do dziś (2006) nie wiadomo, czy istnieje nie-
skOllczenie wiele liczb picrwszych bliźniaczych. Wiadomo, że jcst 27412679 par
liczb mnicjszych od 10 10 • Największą znaną parą liczb picnvszych bliźniaczych
tworzą liczby 16869987339975.2 171000 ± l, "odkrytc"' w 2005 rokll. Każda z tych
liczb ma 51779 cyfr. Wiele ciekawych informacji o liczbach pierwszych bliźniaczych
można znaleźć w Internecie na stronic: http://primes . utm. edu/top20/.
'IN 19HI roku V. Bruu udowodnil, żc L/lEP' f, < 00, gdzie P' = {p E !P' : p + 2
jest liczbą pierwszą}, a więc na mocy twierdzenia Eulem (twierdzenie 11.3) jest
"znacznie mniej" liczb bliźniaczych niż wszystkich liczb pierwszych.
DEFINICJA 11.5
Liczbami Mersenne'a nazywamy liczby postaci M" = 2" - l, n ;;;. L Jeśli liczba
Jo,'lersenllc'a M" jest pierwsza, to mlZywamy ją liczbą pierwszą Mersenne'a.
M. :\t1ersenne postawil następujl!Cą hipotezę: MI' jest liczbą pierwszą, dla 1) =

2,3,5,7, 13, 17, 19,31,67,127,257, a liczbą zlożoną dla pozostałych liczb pie7'Wszych
l) < 257. Hipoteza okazala sil( nieprawdziwa: M G7 i Af'!:>7 nic Sł! liczbami pierwszymi,
natomiast MG!, M 8'] i M W7 są pierwsze. (F. N. Cole w 1903 roku wykazał, że 267 ~ l =
193707721 . 761838257287.)
Z liczbami Jo,Icrscnne'a związana była hipoteza, że jeśli M" jest liczbą pien/J-
szą, to MAt. jest też liczbą pierwszą. Jednahe \V 1953 roku za pomocą komputera
sprawdzono, że 111).[11 = 2 Afn - 1 = 28191 - 1 jest liczbą złożoną. Przypuszcza się, że
istnieje niesko(lCzellie wiele liczb pierwszych !vlerselllle'a. Największa taka liczba,
231J.l02<l57 _ l, zostaJa odkryta w 2005 roku przez S. R. Bonne'a, C. Coopera i grupę
GIMPS (ang. Great Internet Mersenne Prirne Search by Woltman & KUl'Owski).
Jest to 43. liczba pierwsza lVlersenne'a i "rekordzistka" wśród największych znanych
liczb pierwszych. Poniżej przŁ'<Jstawiamy w tabeli listę dziesięciu najwięksilych zlla-
nych liczb pierwszych. Listę tę zaczerpnęliśmy z internetowej strony poświęconej
liczbom pierwszym (http://primes . utm. edu/largest. html).
11. Wlasności liczb pietwszych (2) 53
Rok
Liczba pierwsza Liczba cyfr Odkrywcy
odkrycia
l 2:W IOH~7 _ l 9152052 Boonc, Coopcr, Glr,IPS 2005
2 22-~964 9:;1 ~ l 7816230 Nowak, GU....!PS 2005
3 2Z,l WG 5SJ - l 7235733 Findlcy, GTT\fPS 200·1
4 220996011 - l 6320430 Shafcr, GltllPS 2003
5 21HG6917 ~ 1 4053946 Cameroll, Kurowski, cn,IPS 2001
6 +l
27653 . 29167 1:J3 2759677 Gordon 2005
7 28433. 27!l30457 + l 2357207 Team Prime Rib 2004
8 2(i.972~9~ _ 1 2098960 Hajratwala, KlIl"OWski, GIMPS 1999
9 +1
5359 . 250:;1502 1521561 Sundquist 2003
10 4847. 2JJ2106J + 1 999744 Hassler 2005
Do sprawdzenia, czy dana liczba :Vlcrscnne'a jest pierwsza, służy algorytm

Lucasa Lehmera. Poszukiwanie dużych liczb pierwszych przestało mieć w ostatllich
latach wyłącznie "sportowy" charakter. Okazalo się, że znajdują one zastosowanie
w teorii kodowania.
Od dawna matematyków interesowało istnienie formuły dającej nieskończony
dl!g różnych liczb pierwszych. VV średniowieczu rozpowszechnione było przekona-
nie, że wzór f( n) = n 2 + n + 41 jest taką formułą. Rzeczywiście dla n = 1,2, ... ,39
warto~ci f(n) są liczbami pierwszymi, ale f( 40) = 40·41 + 41 = 41 2 . Jednak do dziś
(2006) nie wiadomo, czy ciąg f(n) zawiera nieskOllczenie wiele liczb pierwszych.
\Vykażemy teraz, że fornndy takiej nie można zbudować za pomocą wielomianu
o współczynnikach calkowitych.
TWIERDZENIE 11.6 (Goldbach)
Nie istnieje wielomian f(x) = aoXk + alxk - l + ... + ak', k;" 1, a; E Z, ao f:- O, taki
że f(n) jest liczbą pierwszą dla każdego n E N.
Dowód
Niech dla n = 11() \vartość f( no) = p będzie liczbą pierwszą. Dla każdego całkowitego
t wyrażellie f(71fJ + tp) IIlOżlla przekształcić nastę)Jl1.i~lco:
f(11() + tp) = (I()(n{) + tp)k + + Uk-l (no + tp) + ak
1
= Qo7//{ + al7/t'- + + ak_I 7/0 + ak + pq(t)
~f("o) + pq(t) ~ p+ "'1(') ~ pl' + q(t)),
gdzie q( t) jest wielomianem o współczynnikach całkowitych. Stąd l) If( 11() + tp), więc
albo f(11() + tp) jest liczbą złożoną, albo f(1I0 + tp) = ±p lub O. Ale t jest dowolne,
a wielomian stopnia k o współczYllllikach calkowitych może przyjmować tę samą
wartość w co najwyzej k argumentach, więc istnieje to takie, ze f(1IfJ + top) jest
liczb}! złożom!. D
54 Wykład 8
l\vicrclzcnic 11.6 można uogólnić (por. zadanic 70., s. 56).

W. H. r-,'liIIs 4 w 1947 roku wykazal, że istnieje liczba rzeczywista r, taka ze
fr(n) = [1'3"] E IP' dla każdcgo n:;) 1 (por. zadanic 75.). Jt."dnak występuj,/ca w tcj
formule liczba r nie jest dana explicite. \Viadolllo, że istnieje niesko6czenie wiele
takich liczb r. Niedawno (2005) C. K. Caldwdl i Y. Cheng udowodnili, że przy
zalozeniu prawdziwości hipotezy Riemallna r:;) 1,3063 ...
Ostatnim omawianym zagadnicniem związanym z liczbami pierwszymi jest hi-
poteza postawiona w 1742 roku przez Ch. Goldbacha w liście do Eulera i do dziś
(2006) ani niepotwierdzolla, ani nieobalona.
HIPOTEZA 11.7 (Goldbach)
Każda parzysta liczba naturalna większa niż 4 może być Zal)isana jako suma dwóch
liczb pierwszych nieparzystych.
Do dziś (2006) sprawdzono, ze hipoteza Goldbacha jest prawdziwa dla n ~ 10 17 .
Z wyników opisuj,!cych ten problem przytoczymy bez dowodu następuj,!cy rezultat,
pochodzący od J. C. van der Corputa:
TWIERDZENIE 11.8
Niech A{n) oznacza ilo.§ć tych liczb parzystych m ~ n, które nie są sumą dwóch
liczb pierwszych. Wtedy
lim A(n) = O.
" ..... 00 n
Zauwazmy, ze ze słuszności hipotezy Goldbacha wynika prawdziwość następu
jącej hipotezy:
HIPOTEZA 11.9
Każdą liczbę nieparzystą większą od 7 można przedstawić w postaci sumy trzech
liczb pierwszych.
Dowód wynikania tej hipotezy z hipotezy Coldbacha zostawiamy jako ćwIcze
nie. W 1937 roku I. Winogradow wykazał, że hipoteza 11.9 jest prawdziwa dla
wszystkich liczb naturalnych większych od pewnej, bardzo dużej liczby natural-
ncj 1l(). Później udowodniania, żc 11{) < 3,33. 1O-1H1OO .
,
Cwiczenia
1. Wykaz, że w ciągu 6n + 5 jest niesk06czenie wiele liczb pierwszych.

2. Znajdź trzy ostatnie cyfry uajwiększej zlJallej obeCllie liczby pierwszej (patrz
s. 53).
3. Udowodnij, że jeśli p" jest n-tą liczbą pierwszą, to l)" > 2n dla n:;) 5.
4 A lJ11nJc.rel'reHcnti"y !""dio.., null. AIllr:r. ~Iath. SOI;., mI. 53, 19·17.

11. Wlasności liczb pieIWszych (2) 55
4. Udowodnij, że dla dowolnej liczby rzeczywistej x> 1 istnieje liczba pierwsza p

taka, że x < p < 2x.
5. Jaka jest największa liczba naturalna k, dla której 2k l(2")!?
6. Wykaz, ze jeśH n jest liczbą ZIOZOllą, to M" tez jest liczbą zJoŻoną.
7. Wykaz, że dla każdego n E N liczba Fermata P" jest pienvsza lub pseudopierw-
sza (liczbę a uazywamy pseudopierwszą,jeśli a jest zlożona i a12° - 2).
8. Lagrange postawi! w 1775 roku następującą hipotezę: Każdą liczbę nieparzystą
n> 5 można przedstawić w postaci p + 2q, gdzie p, q E P. Sprawdź tę hipotezę
dla n < 100.
9. Sprawdź, że hipoteza 11.9 wynika z hipotezy 11.7.
10. Sprawdź, że liczba M:IO_102457 ma 9152052 cyfr.
11. Nie korzystając z tabeli logarytmów, wykaż, ze liczba Fł915 ma więcej niz 10582
cyfr.
Zadania
56. Korzystając z cykliczności grupy WJ" podaj inny dowód twierdzenia Wilsona
(twierdzenie 8.1).
57. Niech p b",dzie liczbą pierwszą llicparzyst~!. \\tykaż, że iloczyn wszystkich pier-
wiastków pierwotnych moduło p przystaje do (_l)",,(p-l) modulo p.
5S. Wykaz, że dla dowolnej liczby rzeczywistej x >- 2 zachodzi nierówność
IIp<4'.
59. Udowodnij, że liczba F" jest pierwsza wtedy i tylko wtedy, gdy F,,13 !Il,=l
. +L
60. Wykaż, że każdy dzielnik pierwszy liczby Fermata F" ma postać 2"+1 k + 1,
gdzie k E N.
61. Wykaż, że:
(a) (M"" M,,) = M(",.,,),
(b) M",IM" <=? mln.
62. Udowodl1ij, że jeśli q, l) E lfl'" {2} orali ql21' - 1, to IJ = 2kp + 1, gdzie k E No
63. Udowodnij, że każda liczba naturalna jest dzielnikiem sumy pewnycll dwóch
liczb pierwszych.
64. Wykaż, że wykladnik, z którym liczba pierwsza p wchodzi w rozkład kanoniczny
m!, jest równy [f,t] + [f,f] + ...
""_ P Z.'l"'ydi. n"",",,,,,,,, ,..."i. /0.». w..""..·• 2006
ll_148~S_J.CbyWN PWN 2006
56 Wykład 8
65. Kor'lystając z popr'lcdniego zadania:

(a) znajdź rozkład kanoniczny liczby WG!,
(b) oblicz, ile zer ma na kOłlcU liczba 1000!.
66. Wykaz, że nie istnieją Hczby rn, n, k > l takie, że u! = rn k
67. Sprawdź, <ie dla al, (12, ... , (1." E N liczba (al+~';"'+~)!
aJ.":! .. _.a,,.
jest naturalrw.
68. Udowodnij, ze twierdzenie 10.10 jest równoważne warunkowi lim"..... oo "r,~ "= l
(TJ" - n-ta 'I kolei lic'lba pierws'la).
69. Niech !1,Jz, ... ,i", będą wielomianami stopni dodatnich o współczynnikach bę
dących liczbami uaturalnymi. Udowodnij, że istllieje lic'Iba llaturalna n taka,
że wszystkie liczby Ii(n),h(n), ... , i,." (n) są zlożone.
70. NiecII !
b\!d'lie wielomianem stopllia niczerowego, którego współczYlllliki są
liczbami naturalnymi. Wykaż, że dla każdej liczby naturalnej k istnieje taka
liczba naturalna n, że liczba i(n) ma co najmniej k dzielników.
71. Wykaz, ze hipoteza istnienia llieskoIlczenie wielu liczb pienvszych bliźniaczych
jest równoważna na.o;t\!puhcej hipotezie: równanie p + q = T ma nieskOllczenie
wiele rozwiązali w liczbach pierwszych p, ą, T.
72. vVykai, <ie istnieje nieskoóczenie wiele lic'lb pierwszych JI takich, <ic TJ +2 nic
jest liczbą pierwszą.
73. (a) Udowoduij, <ic każda liC'lba naturalna> 6 jest sunu! dwóch wzgl\!dnie pierw-
szych liczb naturalnych> 1.
(b) Korzystając 'I (a) sprawdź, <ie dla n;;;' 3
1'''_1 + 1'''+2'';;; PIPz'" p".
74. \Vykai, że równanie 1'" + ą" = r", TI> 1, nie ma rO'lWią:all'l w liczbach pIerw-
szych p, q, r.
75. Wykaż, że jeśli a = L::l p'llO-t", gdzie 1'1,1"2, ... Sl! kolejnymi liczbami pierw-
szymi, to
p" = [102"]
a - l a 2"-' . [10-,,'-' a.
]
(Liczba a nosi nazwę liczby Sierpillskiego.)
Wykład 9
Aproksymacja liczb niewymiernych

12 liczbami wymiernymi (l)
Niech ~ b(,;dzic liczbą rzeczywistą uicwymicrną. Zbiór liczb wymiernych jest g~sty
na prostej, więc dla każdego E> O istnieje Hczba wymierna ~ taka, że I~ < c. - il
Celem tego rozdziału jest badrUlie różnicy I( - I
% jako funkcji k. W S7.czcgólności
okazuje się, że różnica ta może być nie większa niż p, gdzie c jest pewną stalą
dodatnią. Będziemy dalej zakładać, że ułamek ~ jest nieskracalny i k > O oraz że
0«<1.
TWIERDZENIE 12.1
Jeśli ~ jest liczbIl nie1lJ'!/1Ttiemą, N liczbą naturalną, to i.~tnieje liczba wymierna ~
o mianouJ'"niJ..--u k . .;;; N taka, że
h
Ę --
k
Dowód
Z nicwymicl"llości liczby Ę wynika, że {) < TlĘ - tnĘ] < 1. Jdli n przyjmuje wartości
1,2, ... , N, to otrzymujemy N różnych liczb n(- [nĘ], które leżą w przedziale (O, l).
Rozważmy N przedziałów (O, ~), (j~' ~,) ,... , (N"Nł , l). Każdy z tych przedziałów
zawiera dokładnie jedną z liczb n,Ę - [n,Ę] ałbo istnieje przedział zawierający co
najmniej dwie takie liczby. W pierwszym przypadku przedział (~, L)
zawiera liczbę
m.Ę - [m.Ę] dła pewnego m, 1';;;; m';;;; N. Tak więc O < IĘ - 17~{11 < h!'" i wystarczy
przyjąć ~ = J';~{l. W drugim przypadku istnieje przedział l
eN
, ,~), gdzie l';;;; i';;;;
N, zawieraj}!cy co najmniej dwie liczby nĘ - [nĘ] i mĘ - [mĘ], gdzie O < 1ft < n (, N.
Wynika stąd, że jeśli przyjmiemy n - m = k i [n,Ę]- [m€] = h, to otrzymamy
gdzie k < N. D
Aby podać kołejne łepsze przyblizenia liczb niewymiernych, wprowadzimy

i omówimy pojE,;cie ułamków Fareya.
l'_148~S_J. ObyWN PWN 2006
58 Wykład 9
DEFINICJA 12.2
Ciągiem ułamków Fareya rZfi:du n, gdzie n jest liczbą naturalną, nazywamy
uporządkowany rOSlH!CO ciąg F'I wszystkich nieskracalnych ułamków %' takich że
1 :s;; k :s;; n, O :s;; h ~ k.
Przykład 12.3
F 011121:12:141
5 = l'::;' 4':i'~' 2' 5':i' 4' 5' l'
TWIERDZENIE 12.4 (Cauchy-Farey)
Jeśli ułamek L nastwuje bezpośrednio po ułamku % w ciągu ułamków Fan'.ya F N ,
to
lk-hm=l,
Dowód
Dla N = l twierdzenie jest oczywi~eie prawdziwe, gdyż = ~ i ~, = Zalóżmy i t.
więc, że N ;;- 2. Niech ~, ,:, będą kolejnymi elementami ciągu :F.... , Możemy założyć,
że %:f:. ~, gdyż w przypadb. %= ~ lllamck ~ = ~ i teza twierdzenia jest oezywi~cie
spelniona.
Rozważmy zbiór S = {(.T, y) E Z x Z: kx - hy = l}. Wykażemy, że (1, m) E 5.
Zauważmy, że jeśli (x, y) E 5, to NWD(x, y) = l oraz obydwie liczby x, y są
Ilieujellllle lub niedodatnie. Z twierdzenia 4.2 wynika, że wszystkie elementy zbioru
S mają postać (lb + hl, Yo + kt), gdzie t E Z oraz ("b, Yo) E S. Istnieje więc taka
para (Xl> yd E 5, że
O:S;; N ~ k < YI . .;.; N.
Wykażemy, że .!L E F"I' Ponieważ YI > O i XI ;;- O, więc .!L ;;- O. Zauważmy, ze
l' . II
Xl"';'; YI' Załóżmy bowiem, że .TJ > Yl' Ponieważ k ~ h i .TJ > O, więc
1= kx l - hYJ > kxl - hXI = (k ~ h)XI ;;- O.
Stąd k = h i ułamek ~ = + nie
ma w F N uastępnika, jest to więc sprzeczność.
Zatem O < XI ...;.; YI . .;.; N oraz N\VD(XI, ytl = l, czyli .!l. E FN· ,.
vVykażemy teraz, że !I. = .1.. Ponieważ !l - 1;, = ~ ~ O i nłamek .1. jest
11 m I" I'''' fil
nastę,mikiem ułamka 1; więc.!l. - .1. ;;- O. Prz)' założeniu że .!l. --I- .1. ostatllia
k' 11 '" ' 11 r fil'
nierówność jest ostra. !vlalllY wtedy -r.- - ,:, ;;- 1,1",. Ponieważ ponadto L- i ;;- "~k'
więc dodając pO\vyższe dwie nierówności stronami, otrzymujemy
1 XI h 1 1 k+YI N 1
-'1-~1 = -YI - k ~ -,-,,-" + -",-k = YI mk > -,,--,y-,'k ;, -'1/-' '
a więc sprzeczność. Zatem .!L
,.
= .1..
m D
Zauważmy, że
w powyższym dowodzie została przedstawiona metoda konstru-
owania następllika ułamka w ciągu FN. i
DEFINICJA 12.5
Ulamek kh:t~ nazywamy medianą ułamków i i,:,
12. Aproksymacja liczb niewymiernych liczbami wymiernymi (l) 59
TWIERDZENIE 12.6
JeśliN ;;. 1, to w ciągu ułamków Fareya :FN me ma dwóch kolejnych ułamków
o tym samym mianowniku.
Dowód
Niech k > L Jeśli ~ następuje bezpośrednio po % w :FN , to h + l ::;;;; h' < k
i mielibyśmy ,k < _h_
t-l
,,;:: f{. Tak więc _h_ leiy międ,y !! i f{ w ciągu F . ,·, co
< h+k l "" I; t-l t k
przeczy llasllemu założeniu. D
TWU::RDZENI812.7
'·h""h'
Jesf1 I' kil' k' są kolejnymi ułamkami 1J) ciągu ulamków Fareya :FNI to
h" h+ h'
-
k" k+k'
Dowód
Z twierdzeuia 12.4 wynika, że khl/ - hkl/ = 1 oraz kI/h' - h"k' = 1. Odejmuj'lc te
równości stronami, otrzymujemy h"(k + ki) = kl/(h + h'). D
TWIERDZENIE 12.8
JdU %, .~ sq dwoma kolejnymi ułamkam.i w ciqglt ulamków Fareya :FNI to
k+m;;' N+1.
Dowód
Ponieważ i < ::~, < ~, więc mediana i i ,~ nie nalciy do :F N, czyli k + m > N. D
Z powyższych twierdzell wynika natychmiast następujące twierdzenie, pozwa-
lające utworzyć ciąg :FN + l z ciągu :FN;
TWIERDZEN1E 12.9
Ulamki należące do :FN + 1 , a nienależące do:FN są medianami sąsiednich ułamków
z ciągu :F,v.
Z powyższych informacji o ciągach ułamków Fareya wynika taki rezultat:
TWIERDZENIE 12.10
Jeżeli f. jest liczbq niewymienu} i N liczbą. naturalnq, to istnieje liczba wymierna ~
o mianowniku k ::;;;; N taka, że
Dowód
Oczywiste jest, że dla kaidego k E Ii liczba ~ ~ h. Liczba ~ leiy między dwoma
"<'<, < u+r.

*J
kolejnymi ulamkami i należącymi do F N . Rozważmy d,va przypadki:
J 'b b+d'
2. b~~ < ~ < ~.
11_ i4.,§_J. C by WN ffilN !006
60 Wykład 9
Mediana :1~ 1- f N, wi~ b+ d ~ N + 1. W przypadku 1. mamy
Wystarczy wtedy wzil!ć ~ = %.

W przypadku 2. mamy
a+c
c c bc- ad l
O<d-~<tl-b+tl "";-,,,<;",,,-;-,,
d(b+d) d(N+l)
i wystarczy przyj'lć i = -;]. \V obydwll przypadkach nlamek i spełnia tez~ twier-
dzenia. D
Jdli ~ jest liczbą wymierną, to można otrzymać podobny rezultat, z tym że
wtedy nierówność nie jest ostra.
TWIERDZENIE 12.11
Dla każdej liczby wymiernej ~ = ,:" gdzie (l, m) = l i każdej liczby naturalnej N
i
takiej, że m > N, i5tnieje nieskraco.lny ułamek o mianowniku k ~ N, dłn którego
spełniona jest nierówność
Dowód
Liczba ~ ,:, 1- fN. Postępujemy podobnie jak w dowodzie poprzedniego twier-
dzenia, z tym jednak, że może siC; zdarzyć, iż ~ = :t~, a wiC;e nierówności muszą
być nieostre. D
Z twierdzeniu 12.1 wynika nust..,pująee
TWIERDZENIE 12.12
Jeżeli ~ jest liczbą. niewymienuJ:, to istnieje nieskorlczenie wiele liczb wymiernych
% takich, że
h
Ę- -
k
Dowód
Z twicn.lzClJia 12.1 wicmy, ŻC dla dowolncj liczby llatllralucj N istnicjc liczba wy-
mierna % taka, że k < N oraz I~ ~I < k~" stąd I~ ~I < - -
Z dowolności liczby p.
N i z tcgo, że limN--+oo k~ O wynika, żc takich ulamków jcst llicskOllcZCllic i
wiele. D
Uwaga 12.13
Ponicważ ~ - i
można zapisać w postaci ~ + n - h-;.hl, gdzic n E Z, więc twierdze-
nia 12.1,12.10,12.11,12.12 SI! prawdziwe bez założenia, że O < ~ < l.
11_ i4.,§_J. C by WN M<'N !\Alb
Wykład 10
Aproksymacja liczb niewymiernych

13 liczbami wymiernymi (2)
Udowodnimy teraz sformułowane w wykładzie 7. twierdzenie 10.3: Jeśli n, A E N

i ni A'.? + 1, to istnieją, takie liczby calkowite s oraz t! dla których n = s2 + t 2, lJrzy
czym (s, t) = 1.

Dla n = l twicrdJlCllic jest oCJlywi~cie spcłniollc. Załóżmy, żc n ~ 2 i nicch N =
[JUJ; oczywiście n > N. Z warunku nlA 2 + l wynika, że (n, A) = l, stąd ~ jest
ldamkiem nicskracalnym z mianownikiem n > N. Z twierdzenia 12.1] wYllikil,
że istnieje ułamek nieskracalny ~ taki, że ~I I:' - :;;
.l()+I}' O < s ::;;;; N, czyli
lAs - mi ,;;;; N:l
= IA+l < ITi· LieJlba t = As - 171 jest calkowita oraJl zachodzi
równość
(1)
Liczba n dJlicli pn\wfl stronI( równości (1), więc ni s'.? + t 2 . POlladto O < s';;;; N ,;;;; ITi
oraz Iti < jn, skąd O < S2 + t 2 < 2n i wobec tego n = S2 + t Z.
Zauważmy, żc (s, t) = 1. RJlccJlywi~cie (s, t) = (s, As- m) = (.~, m), a z nicskra-
calności ułamka ~ wynika, że (s, t) = (s, n). Ponieważ n = s'.? + t 2 , więc z równości
(l) otrzymujemy 1 = .,'(A"' +l) - 2Asr + r 2 n.
Poniewai nlA2 + l, więc (s, n)11, skąd ostatecznie (s, t) = (s, n) = 1. O
WNIOSEK 13.1
Jeśli n jest liczbą naturalną i ulA 2 + B2 , gdzie (A, B) = I, to istnieją takie liczby
calkowite s i t, że n = s2 + t 2.
Dowód
Skorzystamy z tożsamości (A 2 + B 2)( C'.? + D2) = (AD + BCf + (AC - BD)2.
Pouiewai (A, B) = 1, więc na mocy twierdzenia 2.9 istnieją liczby calkowite
C, D takie, że AC - BD = 1. Liczba n dzieli sumę (AD + BC)2 + l i wystarczy
teraz skorJlystać z twierdzenia 10.3. O
l\vicrciJIcnic 12.12 lllożlla wzmocnić w następuj,1CY sposób:

62 Wykład la
TWIERDZENIE 13.2
Jeśli ~ jest liczbą niewymierną, lo istnieje niesko7iczenie wiele nieskmcalnych ułam
ków i takich, że
-
h
k
,-
Dowód
:FI\' będzie
Niecił ciągiem ułamków Fareytl rz\>du N > l. Liczba ~ łeży między
dwoma kolejnymi ułamkami i i ~ tego ciągu, to znaczy i < Ę < ~. \Vykażemy, ze
(2) łub
Załóżmy, że nie zachodzi żadna z nierówności (2). Poniewaz liczba ~ jest mewy-
Hncrna, \Vl~C
a 1 c 1
Ę- b> 2112 oraz d - Ę > 2d2'
Dodając te nierówności stronami, otrzymujemy
c a l 1
d - b > 2b2 + 2rj2'
r\'lnoząc
obie strony ostatniej nierówności przez b2 d 2 oraz korzystając z warunku
be - ad = 1, dostajemy bd > !d 2 + !b 2. Stąd ostatecznie (b - d)? = b2 + d2_
2bd < 2bd - 2bd = Q. Otrzymana sprzeczność dowodzi, że przynajmniej jedna
z nierówności (2) jest prawdiliwa. Wystarczy teraz przyj,!ć = %lub = fl. i i
Zauważmy, ;i;e
h c alI
Ę-k<d-b=bd';;;;b+d 1
Z twierdzellia 12.8 wynika, że b + d ;;;. N + 1 i wobec tego
h I
, - k < N·
Wielkość N możemy zmienia{:, ZiltCUl istniejc llieskOllczellic wiele ułamków i speł

niających tezę twierdzenia. D
\V twierdzeniu 12.12 wykailaliśmy, że każdą liczbę

niewymienH! mo;i;na przy-
bliżać nieskollczoną ilością liczb wymiernych z dokładnością do i Następnie -b.
pokazaliśmy (twierdzenie 13.2), '-'e taka aproksymacja jest możliwa z dokładnością
do 2k.
Powstaje pytanie, czy można ten wynik polepszać to znaczy, czy istnieje
taka stała c > 2, że każdą liczb~ nicwymiel"lH! można przybłiżn.{: nieskOllczcnie wie-
i
loma Hczbami wymiernymi z dokładnością do~. Pełną odpowiedź na to pytanie
daje następuj,!ce
TWIERDZENIE 13.3 (Hul'witz)

Jdli Ę jest dowolnq liczbq nieJllymiemą, to istnieje nieskorlczenie wiele liczb 1mJ-
13. Aproksymacja liczb niewymiernych liczbami wymiernymi (2) 63
miernych i spełniających nierówność
Jeśli zaś c jest liczbą rzeczywistą dodatnią, spełniającą nierówność c > 15, to
istnieją liczby niewymieme~, dla ktÓ1ych nierówność
h 1
~-k<ck2
jest spełniona tyłko dla skończonej ilo.§ci liczb wymiemych i.

\V dowodzie tego twierdzenia, pochodzącym od A. Chiuczyna, wykorzystamy
następujący lemat o czysto technicznym charakterze:
LE~lAT 13.4
Je.§li k, l są liczbami naturalnymi, to 1)rZ'i/1Iajmniej jed7la z nierówności
l 15l (1 +"'fil) '

kI ";? k2 k(k+
l I) ~ V51(1 + l) k' (k+ I)'
jest fałszywa.
Dowód lematu 13.4

Załóżmy, że zachodzą obyd,vie nierówności. Po przekształceniach otrzymujemy
V5k(k + l) ~ k' + (k + I)'.

oraz
Dodając te nierówności stronami, otrzymujemy J5(k 2 + 2kl) ";? 3k 2 + 2kI + 2l 2,
skąd 2[2 - 2{ 15 - 1) kl + (3 - 15) k 2 O;;; O. Ostatnia uierówność jest równoważna
nierówności [21 ~ (J5 - 1)k]2 O;;; O, która nie jest prawdziwa, gdyż liczba ~-1 jest
mewymicrlla. O
Niech :FN będzie ciągiem ulamków Fareya rzędu N > l i niech Z; będą sąsiednimi i,
i
wyrazami w tym ciągu, takimi że < ~ < Z;. Wykażemy, że przynajmniej jedna
z liczb %' Z1Z;, :< spelnia pierwszą nierówność twierdzenia 13.3.
Możliwe Sf! dwa przypadki: f. < ~1Ż; lub f. > R.ozpatrzymy pierwszy Z1Z;.
przypadek, postępowanie w drugim przypadku jest analogiczne. Załóżmy więc, że
~ < ~.1Ż; i żadna z trzech wymienionych liczb nic spclnia tej nierówności, to jest
h + h' 1
k + ki - ~";? 15(k + k')2'
Oodaj,!c te nierówności stronami (pierwsz,! i trn."Cią oraz pierwszą i drugi!), otrzy-
mUJemy
h+h' h
k+k ' -k";?J5
l (l l)
k 2 +(k+kl }2 .
64 Wyklad 10
Z twierdzenia 12.4 mamy wiQc
, J5'(' + I)
kk' ;;" k2 (ki)?
oraz
k(k
I " _1_
+ k')
(_1 + -.:--cl"",,)
J5 k' (k + k')' '
r
co daje sprzeczność z lematem 13.4.

Aby wykazać nieskOlkzollość zbioru rozwiązali pierwszej nierówności twierdze-
nia 13.3, postQpujcmy tak samo jak \V ostatniej części dowodll twicrdzcuia 13.2.
UdO\vodnimy teraz drugą część twierdzenia. :Jiech ~ = 1
i przypuśćmy, że 4+
nieskoóczeuie wiele liczb wymierllych ~, k" > 0, spełnia llierówllość
hn l
(3) --{<-"
k" ck"
gdzie c jest stałą dodatnil!. Wykażemy, że c <; V5. Z llierówllOŚci
l l
k"Ę, - ~ < h" < k"Ę,+ ~
c~, c~,
wynika, że danej wartości k" odpowiada skoJlczona liczba wartości h", więc
lim".. . . oo k" = 00. Zauważmy, że (x - Ę,)(x - ł-l15 ) = :1: 2 -:r - 1, stąd dla liczb
całkowitych h, k, gdzie k > O, otfl'.ymujemy
h h ~
(4) --{ --{+v5 = kl 2 h - hk - k
k k 1' 'I :;. kl Z '
Z nierówności (3) i (4) wynika, że
h" -(+J5 <k\(k\+J5),

k" c" c"
czyli
l
c< k2+J5.
,"
Stąd c ~ lim,,---<ooo (ftr + J5) = /5. D
Przykład 13.5
\Vykażcmy, że nicrówność IJ2 - ~ 1< :ih
uie ma rozwiązmi w liczbach naturalnych
a, b. Po pomnożeniu obu stron tej nierówności przez .j2 + %i jej przekształceniu,
otrzymlljcmy
12b'- a'l < ~1J2+ ~I ~ ~ (J2+ ~).

Jeśli b = l, to nierówność 1J2 - al < 111ie ma rozwiązaó w liczbach calkowitych.
Załóżmy więc, ze b > 1. Wtedy 1,,12-%1 < I~ oraz A(J2+ 7D< 1. Stąd 12bz-az l = 0,
ale to równanie nie ma rozwiązaó w liczbach naturaluych.
13. Aproksymacja liczb niewymiernych liczbami wymiernymi (2) 65
•
Cwiczenia
1. Wypisz ciągi ulamków Fareya F G,F7 ,Fs.

2. Podaj najlepsze przybliżenie wymierne %liczb:
(a) 71, gdzie k ~ 10,
(b) hll0 = 2,3026" .. , gdzie k ~ 20,
(c) n=3,1415 ... , gdziek~30.
3. Korzystając z zadania 35., s. 29, podaj inny dowód twierdzenia 13.2.
4. Wykaż, że liczba wyrazów ciągu ulamków Fareya F" jest równa l + L:~=1 tp(k).
5. Niech F" = O, ... , i, ~, ~;, ... ,l, gdzie n :;? 2. Wykaż, że k = ki = l + 2 ["1"1]
oraz h + h' = k.
6. Wykaż niewymierność następl.lhcych liczb:
(a) lag lO 2,
(b) vIk, gdzie 11/, k E N, m, k:;? 2 oraz kopr'" dla r E N-
7. Udowodnij, że jeśli n> 1, to:
min {hlk '_kII k: h,kh'' sąsiednie F,,}
elementy = (
nn
l l),
max {h' _ II: h, h'

k'kkk'
sąsiednie elementy F,,} = ~.
n
8. Niech ~ = \+2'8 oraz e,a E lR+, o' > 2. \:Vykaż, że nierówność I~ - il < cl", ma
skOllczenie wiele rozwillzarl w liczbach wymiernych i.
9. Zalóżmy, że liczby calkowite h,k spelniają nierówność Ik~ ~ hl < Ak' gdzie ~
jcst liczbą niewymierną. Udowodnij, że liczby nh, nk spełniają tę nierówność
tylko dla skollczenie wielu liczb naturalnych n.
Zadania
76. vVykaż, że jeśli dh k, k' > O liczby wymiel"llc i,
~; należące do odcinka [0,1]
spełniają równość h' k- hk' = 1, to są one sąsiednimi elementami ciągu ulamków
Fareya F", gdzie n = max{k, ki}.
77. N"1L"C,Il :F, ,-- Q _.!!J. 0.. !1 - 1. Spta\\
1 - k,' 1",' ... , kI -
"' ,cliz, ..ze ~I-l _1_ -
L..-j=l k kj+l -
1.
J
78. Udowodnij, że jeśli a > l oraz dla liczby rzeczywistej f3 istnieje nieskOliczenie
i
widc liezb wymiernych %takich, że 1f3 - I < k~" to {3 jest liezbl! niewymicl"llli'
l<" ~ ,_j.
L"VZ)'<ki. El"••,",""",
I~-:b. W........... 2Q(l()
66 Wykład 10
79. Wykaż, że liczby:

(a ) "ro
L...j""
2-" '
. .
sil IlICWYUlIerltc.
80. Udowodnij, że następujące liczby są niewymierne:
(a) J3 - )2, (d) e,
(b) L,.. 10-', (e) c", l,
(c) 0.2357111317 ... , (f) sin l.
81. Podaj przykład takich liczb nicwymiernych o, {J, że:
(a) a(J jest liezb.1 wymierną,
(b) a(j jest Iic-.lbą nicwymierną.
82. Udowodnij, żcjcśli fi '# 4, to nie istnieje ciąg (x" y,), (X'], lII),···, (x", y,,) punk-
tów płaszC'".lyzny R 2 o obu współrzędnych wymiernych tworl.ący n-kąt rorellllly.
83. Liczba nC jest calkowita dla n = 1,2, ... \\·ykaż. że c E N U {O}.
Wykład 11
Przedstawienie liczby naturalnej

14 jako sumy kwadratów (l)
Zajmiemy się następuj'1Cym problemem:

Czy daną (każdą) liczbę naturalną można
przedstawić w postaci sumy dwóch, trzech lub ogólnie k kwadratów liczb całkowi
tych? Poznaliśmy już pewien warunek dostateczny na to, aby liczba n była sumą
dwóch kwadratów (twierdzenie 10.3), a mianowicie: jeśli nlA 2 + l, to fi, = S2 + (2.
Naszym celem jest podanie warunku koniecznego i dostatecznego na to, aby dana
liczba naturalna była sumą dwóch kwadratów liczb całkowitych orali wykazanie
prawdziwości twierdzenia, że każdą liczbę naturalną można przedstawić jako sumę
czterech kwadratów liczb całkowitych. W pouiiszej definicji wykorzystuje się poję
cie reszty kwadratO\vej moduło p (patrz definicja 8.5).
DEFINICJA 14.1
Niech p E IP" {2}, m E Z, (m,p) = l. Symbol Legendre'a C;) określamy
1łastępuj~lco:
jeśli m jest resztą kwadratową modlllo p,

jeśli m nie jest resztą kwadratową modulo p.
Symbol Legendre'a dla przypadku plm definiuje się, przyjmując (;") = o.

TWIERDZENIE 14.2
Jeśli p E Jr" {2} i m E Z, to
mz..y!=(;) (modp).
Dowód
Dla 1ft podzielnego przez JI równość jest oezywiśt:ie spclniona. Jeśli (m, JI) = l,
to m/ J
-
1
l (mod p). Zrówności mjJ-l - 1= (mz..y! - 1) (m"i' + l) wynika,
m' = l (mod p) albo = -1
l.=..!. l.=..!.
że m' (mad p). Wystarczy teraz skorzystać
z twierdzenia Eułera 8.6. D
STWIERDZENIE 14.3
Symbol Lege1ll1re'u. mu. następujq,ce własności:
(1) jeśli mi 7r/2 (mod p), to U;) = (-7-),
68 Wykład 11
(2) (m,,:*,) ~ (';'). (';'),
(3) (-;') ~ {_:: jdli p_l (mod4),

jeśli p 3 (mod 4),
L..",.1 (m)~o.
(4) ""-, jJ
Dowód
Własności (I), (2) wynikają natychmiast z definicji. Zamvażmy, że wlasność (2)
oznacza, że iloczyn dwóch reszt kwadratowych albo dwóch niereszt kwadratowych
moduło 1) jest resztą kwadratową moduło p, natomiast iloczyn reszty k\vadrato-
wej i lliereszty kwadratowej Illodulo ]i jest nieresztą kwadratowf! ll1odulo p. Wła
sność (3) jest wnioskiem z twierdzenia 14.2. Wlasność (4) wynika z faktu, że kon-
grucncja x9 _ 1 (mod p) ma dokladnic 1';1 rozwiązaI'l modulo]i: wystarczy tutaj
skorzystać z twierdzenia 9.2, biorąc dowolny generator g grupy Wp; elementy l,
g2, g4, ... , gp-3 są rozwiązaniami tej kongruencji. \Vynika stąd, że istnieje 1';1 reszt
kwadratowych moduło p, powstale skladniki sumy L~~II (;) są równe -1. D
LEr.'IAT 14.4 (GAUSS)

Załóżmy, że p = 2n + 1 jest liczbą pierwszą, zbiór G = {±u\, ±u.z, ... , ±un } jest
u-edukowanym układem reszt Tlwdulo p, m taką liczbą całkowitą, że (m, p) = 1.
Wówczas (;) = el'" en, .lidzie dla j = 1,2, ... , n mamy filUj eju)' (mod p),
przy czym ej = ±J oraz uj' E G.
Dowód
Zauważmy, że jeśli j t-
k, taj' f- k'; w przeciwnym przypadku bowiem mUj ±muk =
(mod ]i), a więc Uj _ ±lJk (mod p), a to jest sprzeczue z definicją zbioru G. Gdy
pomnożymy stronami kongruencje mUj - eju), (mad p) dla j = 1,2,.,., n, otrzy-
mamy m"(uI'" 11,-,) =
(el'" e")(UI'" u,,) (mod p), zatem m" =
el'" e" (mod p)
lub inaczcj mS! - el'" e" (mad l))' Teza lematu wynika z twicrdzenia 14.2. D
Z lcmatu Gaussa wynika nastl(pującc:
STWIERDZENIE 14.5
Jdli p jeBt liczbą pierwBul nieparzystą, to
(2)
p ~ (-1) ~
, .
Dowód
Zbiór G = {±1,±2, ... ,±/';I} jest zredukowanym ukladem reszt modulo l). Z le-
matu Gaussa wynika, że wystarczy policzyć liczbę tych elementów ciągu 2 . 1,
2 . 2, ... , ')- ' t=.!
2 ' kt'ore S,!
. Wlę
··k· Z' z·,l1em (')
SZCO(l i d p -- (- 1)' ,gd,'· \.
ZICA.lCSt I·ICZ
··b·'!
c1emcnt6w zbioru {8 E N: p~1 < s ~ /';I} i wobec tego A = k, gdy p = 4k + l lub
11_ t:m5_J. tllij'WN I'WN iOOS
A= k + 1, gdy p = 4/,; + 3. Ponieważ
1)2 ~ 1 = {kk+1(mad(mod2),
2), gdy 1)= 4k+ l,
8 - gdy p = 4k + 3,
w'Q' Gl ~ (~1)' ~ (~1)4'. D

Sformulujemy teraz twierdzenie odgrywające podstawową rolę w teorii reszt
kwadratowych. O "popularności" tego twierdzenia świadczy chociazby artykul
łvl. Gerstenhaben/', w którym podany jest sto piQĆdziesiąty dTllgi (1) dowód tego
twierdzenia. \V podręczniku P. Bachrnanna6 podano informację o 56 różnych
dowodach prawa wzajemności reszt kwadratowych.
TWIERDZENIE 14.6 (prawo wzajell1ności reszt kwadratowych)
Jeśli p, q są różnymi liczbami pie7wszymi nieparzystyrni, to
Dowód
Zastosujemy lemat Gaussa dla q = 2m + 1 i 1J = 2n + 1. Dla x = 1,2, ... , n
istnieją u ... E {1,2, ... ,n} oraz e:r = ±1 takie, że qx - e:ru... (mad p) lub inaczej
qx = e,.·Ux + py, przy czym dla ustalonego x wartości tl", e", li wyznaezone są
jednoznacznie. \V szczególności e:r = ~ 1 wtedy i tylko wtedy, gdy py = qx + u....
Z ostatniej równości wynika, że y > O oraz
1 q+ l
y<~n(q+l)< =m+1.
p 2
Innymi słowy e" = -1 wtedy i tylko wtedy, gdy istuiejc taka para (x, y) liczb
naturalnych, że l < x < n, l < y < m i l < py ~ qx < n. Niech SI oznacza liczbę
takich pa.r (x, y). Na mocy lematu Gaussa otrzymujcmy (f,) = (-1)". Analogicznic
można sprawdzić, że
G) ~ (~1)",
gdzie 82 oznacza liczbę takich par (x, y) liczb naturalnych, że 1<x < n, 1 < y < 1ft,
l ~ q:"C - py ~ m. Wobec tego
Rozbijemy teraz zbiór S = {1,2, ... ,n} x {1,2, ... ,m} na trzy rozhlcZlle zbiory,
a
. ..
mlaJl0WICle:
A = {(x, y) E S: -n';;;; qx - py';;;; ut},
B ~ {(x, y) E S, qx ~ PY < ~n},
C = {(x, y) E S: qx - py > m}.
5 Gcrstenhabcr :;"'1., The 152nd prooj oj IIle law 0/ quadm/ic recipwcity, Amcriclln ~Iathematical
Monthly,70(19(;3).
6 l3adanaTltl p" G,"1jlld/r1"1m der Nfllcren ZahiclIlhcm';c, Walkr de Grllyter, Ikrlill In\.
70 Wykład 11
Zauważmy, że moc zbiofll A jest równa 81 + 82, gdyż (fx - py -::j=. O dla (x, y) E S.
Ponadto zbiory B i C są równoliczne, gdyż przyporządkowanie
(x, V) !-----lo (n+ l-x, m+ 1- V)
jest różnowartościowymprzekształceniem zbioru B na zbiór C. Niech S3 i S.l oZlla-
eza.ją moce zbiorów odpowieduio B i C. Ostateczuie otrzymujemy
(~) (~) = (_l)"l+~l = (_lrJ+~+2~j = (_l)"J+~'+~+~ = (_1)m.". D
Ze st"wierdzellia 14.3(3) możlla wyprowadzić llastępujl!Ce
TWIERDZENIE 14.7 (Fermat)

Każdą liczbę pierwszą postaci 4k+ 1 można przed8tawić jako sltmę dwóch kwadratów
liczb całkowitych.
Dowód
Ze stwierdzenia 14.3(3) wiemy, że kongfllencja x 2 _ -1 (mod p) ma rozwiązanie,
to znaczy istnieje liczba naturalna A taka, ze pl A2 + 1. Z twierdzenia 10.3 wynika
istnienie liczb uilkowitych 8, t takich, że p = SZ + t Z. D
Nieefektywny, ale blyskotliwy i krótki dowód powyższego twierdzellia Fel'lllata

podal w ]990 roku D. Zagier 7 . Przedstawiamy tutaj nieco bardziej roz\viniętą wersję
tego dowodu.
Dowód twienlzenia 14.7
Dla liczby pierwszej p = 4k + l rozpatrzmy zbiór
S = {(x, y, z) E N, :.T
2
+ 4yz = p}.
Zbiór S jest niepusty (1,1, k) E S) oraz sko{H,:zoIlY. Wykażemy, że S ma nieparzy-
stą liczbę elementów.
Definiujemy odwzorowanie g; S ....... S w sposób następujący:
(x + 2z, z, y - x - z), jeśli x < y - z,
g(x,y,z)= (2y-x,V,x-V+z), jeśli y - z < x < 2V,
{
(x-2V,x-y+z,y), jeśli x > 2y.
Łatwo sprawdzić, ze odwzorowanie g jest poprawnie określone.
Ponadto g jest róż
nowartościowe, co najłatwiej wykazać, zauważając, że g jest inwolucją, to znaczy
g o g = id. Rzeczywiście, jeśli na przyklad x < V - z, to g(x, V, z) = (x + 2z, z,
y-x-z). Abyobliezyć g(g(x, V, z)), zauważmy, że x+2z > 2z, zatem g(g(x, y, z))
= !I(x + 2z, z, y - x - z) = (x + 2z - 2z, x + 2z - z + y - x - z, z) = (x, y, z).
Analogicznie sprawdzamy dla y - z < x < 2y i x > 2y.
Odwzorowanie g ma dokladnie jeden punkt stały, ponieważ tylko g(x, y, z) =
g(2y - x, y, x - y + z) = (x, u, z) ma rozwiązanie x = y. Ale wtedy p = x2 +
7 Zagier D" A olle-~enteuce prool Ihat evny pJime p == l (mod 4) is a sum ol two squares, The
Am"rica" i\latlocmatica) )'Iotlthly, \"01. 97, lir 2(1990), s, 14,1.
4xz = x(x + 4z), stąd x = y = 1, z = k. Z różnowartościowaści g i posiadania

przez nią dokladnie jednego punktu stalego wynika, że liczba elementów zbioru
S jL"St nieparzysta. Rozpatrzmy teraz odwzorowanie f : S -+ S określone wzorem
f(x, y, z) = (x, z, y). Z nieparzystości mocy zbioru S wynika, że odwzorowanie f ma
punkt staly (:li), !AJ, ZO), zatem f(:li), '!lO, ZO) = (:ro, ZO,!AJ) = (:ro, '!lU, ZO), czyli !AJ = Zo·
Stąd ostatecznie p = :eJ :eJ
+ 4yÓ = + (2y"f· O
Fakt, że jeśli p E P i P = 4k + 1, to plA 2 + 1 dla pewnej liczby naturaluej A
można wzmocnić w taki oto sposób:
TWIERDZENIE 14.8
Jeśli p jest liczbą naturalną pierwszą postaci 4k+ l, to istnieje taka liczba calkowita
x, że x 2 + l = rnp (ila pewnej liczby naturalnej m < p.
Dowód
Ponieważ ~ 1 jest resztll kwadratową
modulo p, zatem istllle.le liczba calkowita
x E {l, 2, ... , będąca rozwiązaniem kongruencji x 2 = -1 (mod p)j wówczas
,,;1}
x 2 + l = mIl dla pewnej liczby naturalnej 1/1. POllieważ x < !J, wi~c x 2 + l <
(!J)2 + 1 < p2 i wobec tego m < p. D
Podamy teraz pewien rezultat analogiczny do poprzedniego twierdzenia.
STWIERDZENIE 14.9
Jdli p jest liczbl} pienllszfl nie]JaTZysif}, to istniejl} liczily młkowite .T{I, 110 takie, ze
l + xJ + yJ = mp dla pewnej liczby naturalnej rn < p.
Dowód
Kwadraty x 2, gdzie x = 0,1, ... , 1';1, s(~ parami nicprzystaj(~cc modlIla p. Taką
samą własność mają liczby calkowite postaci ~ 1 ~y2, gdzie y = O, l, ... , P; l. Zbiory
te zawierają w sumie 11 + 1 elementów, muszą więc istnieć takie liczby calkowite
O::>;;:li), Yo::>;; 1';1, że xJ ~l~yJ (mad p). Inaczej mówiąc, istnieje liczba naturalna
m taka, że l +:rJ+yJ = mpo Ponieważ J{J, Yu :;;; 1';1, więc 1+:zJ+ yJ < l +2( !J)2 < p2
i wobec tego Ut < p. O
Znamy już dwa warunki dostateczne Ila to, aby liczba naturalna n byla sumą
kwadratów: ni A2 + l lub n jest liczbą pierwszą postaci 4k + l. W następnym
twierdzeniu podamy warullek kOllieczny i dostateczuy na to, aby liczba naturalna
byla sumą dwóch kwadrató\v liczb calkowitych.
TWIERDZENIE 14.10
Liczbę Tlaturalną. n można przedstawić w postaci sumy dwóch 1.:wadraMw liczb całko
witych wtedy i tylko wtedy, gdy w rozkładzie kanonicznym liczby n wszystkie dzielniki
pierwsze postaci 4k + 3 wIJstępują z wykładnikami p(lTzystymi.
Dowód tego twierdzenia opiera się na dwóch lematach.
DEFINICJA 14.11
Przedstawienie n = x 2 + y2 nazywamy pierwotnym, jeśli (x, y) = l, niepierwot-
nym za.~ w przeciwllym przypadku.
Oc>.. P Z'''Z)'<ki. El..""",,,,,,,, """0 Iu-..b, "'..m .... 200ó
72 Wykład 11
LEMAT 14.12
Jeślin dzieli się przez liczbę 1)ie7'Wszą postaci 4k+ 3, to n nie lJOsiada przedstawień
pierwotnych.
LEt.IAT 14.13
Jdli P jest liczbą pierwszą postaci 4k + 3 i o; jest taką liczbą naturalną nieparzystą,
że pC> I n oraz pc>+l ł n, to liczby n nie można przedstawić w postaci sumy dwóch
kwadratów liczb calkowitych.
Dowód twienlzenia 14.10
Konieczność (=». Z lematu 14.13 wynika, że jeśli n = s2 + t 2 , to każdy dzielnik
pierwszy liczby n, postaci 4k+3, występuje w rozkładzie kanonicznym n z wykład
nikiem parzystym.
Dostateczność ({=). Załóżmy, że liczba n ma tę własność, że każda liczba pierw-
sza postaci 4k + 3 wchodzi w jej rozkład kanoniczny z wykładnikiem parzystym, to
znaczy n mOŻlla zapisać w postaci n = nr·
TII:?, gdzie TlI:? nie ma dziełników pierwszych
postaci 4k + 3. Jeśłi liczba pierwsza p dziełi 1l.2, to p = 2 albo p = 4k + 1. W pierw-
szym przypadku p = 1'2 + 12, w drugim, na mocy twierdzellia 14.7, p = o$Z + t Z .
Korzystając z tożsamości (xr + yr)( xi + Yi) = (XI:Dl + Yl 112)2 + (Xl 112 - X2 YI)2, otrzy-
mujemy 1/,z = a2 + &2, u = nrUZ = (ula)2 + (n]b)2. O
>
Wykład 12
Przedstawienie liczby naturalnej

15 jako sumy kwadratów (2)
Udowodnimy teraz lematy \4.12 i 14.13 zamieszczone w wykładzie 11.

Dowód lematu 14.12
Załóżmy nie wprost, że Hczba n, podzielna przez liczbę pierwszą p postaci 4k + 3,
posiada przedstawienie pierwotne n = x'1. + y'l.. Zauważmy, że p f x oraz p ł y.
Ponieważ rłx, więc xl 1 (mad p) dla pewnego l. Stąd O t2 (X 2 + y2) (yl)'!. + 1
(mad p), a to znaczy, że -\ jest resztą kwadratową moduło 1J - sprzeczność ze
stwierdzeniem 14.3(3). O
Dowód lematu 14.13
Załóżmy nic wprost, że n = x 2+ y2, gdzie (x, y) = d. Wtedy x = dX, y = rlY, gdzie
(X, Y) = l, i n = (/'2(X 2 + y2) = d2N dla pewnego N. Jeśli pr jest największą
potęgą p, która dzieli d, to pCf~2r jest największ,! potęgi! p dzicll!cl! N. Tak wil,?c
otrzymujemy N = X 2 + y2, gdzie (X, Y) = 1 oraz plN, przy czym p ma postać
4k + 3. Otrzymaliśmy sprzeczność z lematem 14.12. D
Rozważania Oprilcdstawiauiu liczby naturalnej w postaci sumy kwadratów licilb
całkowitych zakOllczymy następującym kłasycznym rezultatem:
TWIERDZENIE 15.1 (Lagrange)
Każda liczba naturalna n jest sumą cztenoch kwadratów liczb całkowitych.
Dowód
POllieważ 1 = 0 2 +0 2 +0 2 + 12 , wi((c możemy założyć, że n > 1. Z tożsamości Eulera
( x 2l + -"1'l3 + x.z.\ + 2
1-.4 )(y'
1 + y~_ + y.'.l + y')
-1 = Z21 + z.i_ + z}.l + Z24'
gdilie:
Zl = XIYI + 3)1'!h + x~y~ + 34Y·t,
Zz = XI Y:! - 3'l2Yl + X3Yl - XtY:\,
Z3 = X1Y~ - X~YI + I.f!fl - ·7:2Y-I,
Z.I = XI Yl - XIYl + 3'l2Y:\ - X:l'!/l,

wynika, że ilocilyn dwóch licilb calkowitych, które można przedstawić w postaci
sumy czterech kwadratów liczb całkO\vitych, jest też liczbą o tej własności. Po-
nieważ 2 = 02 + 0 2 + 12 + 12, wi((c na mocy zasadniczego twierdzenia arytmetyki
ll_148~~_J.CbyWN PWN 2006
74 Wykład 12
(twierdzenie 3.2) wystarczy wykazać, że ka.żda liczba plcrwsza nicparzysta jest

sumą czterech kwadratów liczb całkowitych.
Niech p będzie liczbą pierwszą Ilieparzystą i Iliech mo będzie naj mniejszą liczbą
naturalną taką, że
(1 )
gdzie nie każda z liczb Xl, 1i;?, X3, xt dziełi się przez p. Istnienie takiej łiczby mo wynika
ze stwierdzellia 14.9. Ze stwierdzenia 14.9 wYllika też, że 11lo < p. Wykażemy,
co zltkoóezy dowód twierdzellia, że 1I/{l = 1. Załóżmy, że 1T/{l > 1. Udowodnimy
najpierw, że mo musi być liczbą nieparzystą. Rzeczywiście, jeśli 17/{l jest parzyste,
to łiczby Xl, ."1:2, X3, .T4 albo S'l wszystkie parzystc łub wszystkie nicparzystc, Itlbo
dwie z nich są parzyste, a dwie nieparzyste, na przykład Xl, 72 są parzyste, a Xa, X4
llieparzyste. Z równości
wynika, że ł1T/{lIJ jest sumą cztere<.:h kwadratów liczb ealkowitych niedzielących się
jednocześnie przez p (gdyż łmop < ł p 2), ale to przeczy minimalności 17/{l. Zatcm
mo ~ 3 i możemy zapisać, że
(2) X; = b;tr/{l + y;, i = 1,2,3,4.
Przy czym b i , y; E Z oraz Yi IllOŻUU wybrać tak, aby Iyd < T; jeśli bowiem Xi =
b;mo + yi, gdzie y; > T' to możemy zapisać X; = (b; + l)n/{l + (y; - lIlo) = b;lIlo + Yi,
gdzie -;fI{j
< y; < O.
Ponieważ nie wszystkie liczby Xl, 72, X3, XJ Si! podzielne przez mo, więc
'=
0< Yl
2
+ Y22 + Y32 + Y.l2 < 4 ( )
l
'2l1lo mo'2
Z (1) i (2) wyllika, że
y; + Y? + y;; + YI ~ O (mod 11/{l).

Otrzymaliśmy liczby całkowite X;, y; (i = 1,2,3,4), dła których
xl + xi + x.l + xf = T//{lp, gdzie 1 < 11lo < p,

Yf + y:; + yj + yi = 1nl11/{l, gdzie O < 1/11 < 1//{l.
Z tożsamości Eułera wyllika, że istllieją liczby całkowite Zl, 12, Z:), Zl takie, że
(3)
Co więcej,
" ,
Zl = 1: T-;Jf, = 1: Xi(T~ ~ b;1T/{l) -1: x; _ O (mod 111{));
;=1 ,=1 i=1
11_148SS_J. ł'> by WN PWN 2001>
analogicznie: Z2 = Z3 = Zł = O (mod nl(l). St'ld mhmy z, = Tfl(lt" gdzie ti E Z dla

i = 1,2,3,4. Podstawiając te wartości do równości (3), otrzymujemy
mlP = tf + ti + t.} + tJ, gdzie O < mI < mo,

a to jest sprzeczne z minimalnością mo. Zatem 111(1 = l i tym samym twierdzenie
Lagrange'a z05talo udowodnione. O
\V XVIII wieku E. Waring postawił następującą hipotezę zwalJą hipotezą

Waringa: Dla każdej liczby nat1tmlnej k > 2 istnieje laka liczba naturalna rek),
że każdą liczbę naturalną n można przedstawić tu postaci
n =
k
nj + 112i' + ... + nr(k)'
k
gdzie nI, 7/.2, ... , nr{k) E N U {O}. W pelnej ogólności hipotezę Waringa udowodnił
D. Hilbert w 1909 roku. Po jej potwierdzeniu powstal naturalny problem znalezienia
najmniejszej takiej liczby rek), którą oznaczać będziemy przez g(k).
Z twierdzenia Lagrange'a 15.1 wynika, że 51(2) ,,;;; 4. Ponieważ liczby 7nie można
przedstawić w postaci sumy dwóch lub trzech kwadratów liczb całkowitych, ,vięc
.q(2) = 4. Wiadomo, że g(3) = 9, g(4) = 19, g(5) = 37, .1(6) = 73. W 1957 !'Oku
K. ivlahler udowodnił, że dla dostatecznie dużych k prawdziwy jest wzór
g(k)~ [m'] +2'-2.

,
Cwiczenia
1. Oblicz m.l.St,<,pującc wartości symbolu Lcgcndrc'a:

(a) (;ol), (b) (;;), (e) (,;'), (d) (g),
(e) (;'i), (f) (,~'), (g) (,;;,), (h) (;~;~,)
2. Sprawdź, czy lli.l.Stępujące kongruencje mają rozwiązania:
(a) x2 3 (mod 31), (e) x 2 2 (mod 257),
(b) x2 = 3 (mod 73), (f) x 2 = 219 (mod 419),
(c) x2 _ 5 (mod 73), (g) 2x 2 + 5x - 9 _ O (mod 101),
(d) x2 = 7 (mod 97), (h) 3x2 + 6x + 5 = O (mod 89).
3. Przedstaw 'v postaci sumy czterech k''oladratów liczb całkowitych następujące
liczby:
(a) (1 2 + 22 + 32 + 42 )(5 2 + 62 + 72 + 8 2 ),
(b) (4' + 8')(1' + g' + 8' + 3').
4. Sprawdź, uie wykonując dodawania, że:
( a ) ,",21 '2 _
L...j=l) -
70' ,
(b) 2:::=0(3j + 2)' ~ 48'.

76 Wykład 12
5. "'Vykaż, żc jeśli p E J!l'" {2} oraz (a, p) = 1, to kongrucncja ax? + bx + c = O

(mad p) ma l + (b2I;la(") rozwiąza1'ł modula 1).
6. Korzystając z lematu Gaussa i twierdzenia 14.6 wykaż, że:
(a) (3) _{ l,
P - -1,
gdy p ±1 (mad 12),
gdy P - ±5 (mad 12);
(b) (3) = {_ (!),

p e) ,
gdy p - 1 (mad 4),
=
gdy p 3 (mad 4).
7. Oblicz L~:i (a>~+b), gdzie (a,J)) = l.

8. Sprawdź, że liczba 28 nie jest sumą trzech kwadratów liczb całkowitych.
9. \\Tykaż, że liczby naturalnej postaci 8k +7 nie można przedstawić jako sumy

trzl.'Ch kwadratów liczb calkowitych.
10. Wykaż, że liczba 23 nie jest sumą ośmiu sześcianów liczb calkowitych nieujem-
llych.
11. Wykaż, że liczba 79 nie jest sumą. osiemnastu czwartych potęg liczb całkowitych.
12. Wykaż, żedla każdego n E fi liczbę 2" można przedstawić w postaci sumy
dwóch kwadratów liczb całkowitych.
13. Udowodnij, że jeśli n - 3 (mad 9) lub n - () (mad 9), to n nie można przed-
stawić w postaci sumy dwóch kwadratów liczb ealkowitych.
14. Wykaż, że każdą liczbę całkowitą można przedstawić w postaci sumy pIęCIU
sześcianów liczb całkowitych.
Zadania
84. Wykaż, że jeśli p E JP',,{2}, n E fi, (a,p) = 1, to kongruencja x 2 a (mad p")

ma rozwi<!zanie wtedy i tylko wtedy, gdy (f,) = l.
Udowodnij, że w przypadku rozwiązalności tej kongruencji liczba jej l'Ozwiązail
jest równa 2.
85. Wykaż, że jeśli a jest liczbł~ nieparzystą, n ;;;.. 3, to kongl'Uencja x 2 - a (mad 2")
ma rozwi~!z~\llie wtedy i tylko wtedy, gdy a 1 (mad 8). =
Udowodnij, że w przypadku rozwiązalności tej kongruencji liczba jej rozwiązail
jest równa 4.
86. Korzystając z zadałl 84 i 85, podaj kryterium rozwiązalności kongruencji x 2 - a
(mod m), gdzie Ul;;;" 2, (a, m) = 1.
Oc>.. P Z'''Z)'<ki. El..""",,,,,,,, """0 Iu-..b, "'..m .... 200ó
87. Niech m > l. Znajdźliczb~clemelltówzbioru{a E {1,2, ... ,m-l}: (a,m) = l

oraz kongruencja x 2 - a (mod m) ma dokładnie n rozwiązali modulo m}.
(\Vskazówka: Rozstrzygnij najpierw, jakie wartości moie przyjmować m.)
88. Nk"Ch 11 E!P', {2}. Punkcja!: Z, {kp: k E Z} --+ Z ma następujące własności:
(l) f(a) ~ ±l,

(2) f(a· h) ~ f(a) f(b),
(3) a - b (mod p) "" f(a) ~f(b).
Wykaż, że [ _ 1 albo [(u.) = (~) dla każdego a E Z, {k1J: k E Z}.
89. Wykaż, że jeśli (! jest liczbą całkowibl różną od zera, p, q liczbami pierwszymi
nieparzystymi niedziclącymi a oraz p - q (mad 411.1.1), to (~) = (~).
90. Niech p E !P', {2}. Udowodnij, że:

(a) plx 2 - 2 =} p = 1 (mad 8) l11b p = 7 (mad 8),
(b) plx 2 + 2 =} p - l (mod 8) lub p - 3 (mad 8),
(c) plx'l + 1 =} p = l (mad 8).
91. Korzystając zpoprzedniego zadania, wykaż, ie istuieje nieskOlkzenie wiele liczb

pierwszych postaci: 8n + 1, 8n + 3, 8n + 5, 8n + 7.
92. (a) Udowodnij, że jeśli p E !P', {2}, to
I: (iU + l)) ~-1.

J=! P
(b) Sprawdź, ie jeśli p E !P', {2, 3, 5}, to istnieją takie liczby naturalne l ,;;;; a,
b <; p-l, ~ 'e W (";')
~ l, (~) ~ (b:') ~ -1.
93. \Vykaż, że każdą liczbę pierwszą można w co najwyżej jeden sposób rozlożyć
na sumę dwóch kwadratów liczb natlll"alllych (kolejność składników sumy nie
odgrywa roli).
94. \Vykał, że liczbęllatmahHl n można przedstawić w postaci sumy dwóch kwa-

dratów liczb całkowitych na tyle samo sposobów co liczbę 2n.
95. Udowodnij, ze liczba naturalna n ma postać n = 1.1. 2 - b2 , gdzie a, b E Z wtedy

i tylko wtedy, gdy n ~ 2 (mod 4).
96. Wykaż, że istnieje nieskoóczenie wiele liczb pierwszych postaci (!2 + b2 + c2 + 1,

gdzie al bl c E Z.
91. UdO\\lodnij, że dla. kazdego n E N liczba 2 2 "+1 nie jest sumą am trzech, am
,,,,,j.
• ~ L..-zy<ki. El"••,"",,,,,, I~-:b. \\".........~ 200()
148U_J. C byWN PWN 200()
78 Wykład 12
98. Udowodllij, że jclli 1t = 4 m (8k+ 7), to n nie można przedstawić w postaci sumy
trzech kwadratów liczb całkowitych.
(Uwaga: Prawdziwe jest też twierdzenie odwrotne.)
99. Udowodnij, że
[3'] +
g(k);) 2,1, 2.1; - 2.
(Wskazówka: PrL.c<lstaw 1iC'"L.bę 2.t[~] - 1 jako sumę k-tych pot~ Ijczb calko-
witych nieujemnych.)
Wykład 13
1 16 1 Funkcje arytmetyczne (l)
\\1 wykładzie 4. pojawiła si~ funkcja Eulera ip{m), jedna. z ważniejszych funkcji
rozpatrywanycb w matematyce. \V tym wykładzie przedstawimy inne funkcje aryt-
metyczne, odgrywaj<!ce kluczową rolę nie tylko w teorii liczb, ale i na przykład
\V kombinatoryce czy kryptografii.
OEFINIC.JA 16.1
Funkcją arytmetyczną nazywamy dowolne odwzorowanie f N ----Jo C, gdzie N
jest zbiorem liczb naturalnych, C zbiorem liczb zespolonych.
DEFINICJA 16.2
Punkcję arytmetyczną f nazywamy multiplikatywną,jeśli:
(l) f nic jest równa tożsamościowo zeru,
(2) f(m· u) =f(m) ·f(n) o ile (m,n) = 1.
Omówimy teraz kilka przykładów funkcji arytmetycznych. Przypomnijmy, że
dla n E N funkcja Elllem <p(n) oznacza, ile jest liczb naturalnych mniejszych lub
równych n i względnie pierwszych z n.
TWIERDZENIE 16.3
Funkcja Dułem r.p jest multipUkatywna.
Dowód
Dla m, n E N zbiór Z", = {O, 1, ... , m - l} z dodawaniem i mnożeniem modulo m
i zbiór Z" = {O, 1, ... , n~ l} z dodawaniem i mnożeniem modulo n są pierścieniami.
Łatwo wykazać, żc liczba elementów odwracalnych w Z", i Z,,, dla m, n> l, jest
równa odpowiednio ifl(m) i ifl(n).
Przeksztalccllie II : Z",,, __ Z", x Z"' (lit, fi) = l, okrcśloue wzorem h( a) =
({a)"" (a),,), gdzie (a)", i (a)" oznaczają reszty z dzielenia a odpowiednio przez
m i n, jcst izomorfizmem pierścieni. Wobcc tcgo liczba elemclltów odwracalnych
w Zm"" równa r.p{rn· n), jest taka sama jak liczba elementów odwracalnych
w .lm X Z"' która jest rÓWlla I.p(m)· ;o(n), więc ;o(m· n) = ;o(m)· ;o(n). D
1\vierdzenie 16.3 można wykorzystać do podania efekty\vnego wzoru na obli-
czanie warto~ci ;o( fi).
80 Wykład 13
STWIERDZENIE 16.4
Jeśli n = D'=l pf' jest rozkładem kanonicznym, liczby naturalnej n > l, lo
Dowód
Ponie\Va~ 11' jest funkcją multiplikatywną, więc !p(n) = n:~l <p(pf;). Wystarczy
teraz obliczyć i.p(pO), gdzie p E lP. Oczywiście t.p(p) = p - I; dla O' > 1 wśród liczb
1,2, ... , pO dokladuie p,.-1 ule jest wzglęJnie pierwszych z pU, są to mianowicie
liczby: J . p, 2· p, ... , pCf-l . p. Stąd
<p(p() = pO _ po-1 = po (1 _~)

i ostatecznie otrzymujemy wzór
Ważną whlSllOŚĆ funkcji 'P opisuje następujące
TWIERDZENIE 16.5
Dla dowolnej liczby naturalnej n zachodzi "ówność
Dowód
Dla n = l równość oczywiście zachodzi zalóżmy więc, że n > l oraz n = n~=l pf'.
Dzielniki liczby n mają postać pł', gdzie O .;;;; (3; .;;;; 0';, zatem -
n;=l korzystając
z twierdzenia 16.3 i stwierdzenia 16.4 - otrzymujemy
L~(d) ~
dl"
L
(tl,,···,tl,)
Hń P7 )) ~ (p~")ń~(p7'1
0";:/3,:;;0:; 0:;;/3,:;;0:,
,. fii r
~ II L" (p7'1 ~ IJ(~(1) + ,,(p,) +

;=1 /3,=0 ;=1
+ ,,(pr'))
,
r=l
= llpf; = n. o
;=1
Następną funkcją arytmetyczną, której własności omówimy, jest funkcja liczby

dzielników.
DEFINICJA 16.6
Dla liczby naturalnej n funkcja d(n) oznacza liczbę dodatnich dzielników liczby n.
TWIERDZENIE 16.7
Punkcja arytmetyczna d jest multiplikatywna.

Dowód
Jeśli (m, nl = l, to każdy dzielnik iloczynu m . n może być jednoznacznie przed-
stawiony jako iloc:'-;YIl dzielnika m i dilielllika n oraz na odwrót, każdy taki ilOC:.Iyll
jest dzielnikiem m· n. Stąd d(m· n) = d(m)· d(n). D
Także dla funkcji ci istnieje efektywny wzór na obliczenie jej wartości.
STWIERDZENIE 16.8
Jeśli n = IT=! p;i' jest rozkładem kanonicznym liczby naturalnej n > l, to
d(n) ~ TI(a, + l).

i=!
Dowód
Ponieważ ci jest funkcją lllultiplikatywną, więc
,
d(n) ~ TI d(p;").
;=1
Dodatnimi dzielnikami pf' S~! liczby: l, Pi, 1)7, ... ,p!; 1 sb!d
,
d(n) ~ TI(a, + I). D
i ... l
Kolejnymi przykładami funkcji arytmetycznych są: funkcja eT sumy dzielni-
ków oraz funkcja O'k sum k-tych potęg dzielników, gdzie k E IR.
DEFINICJA 16.9
Dla liczby naturalnej n funkcja
a,(n) ~ 2:>'. gdzie k E IR.
dl"
Zauważmy, że ao = d, al = a.
TWIERDZENIE 16.10
Dla każdego k E IR funkcja ak jest multiplikatywna.
Dowód
Jeśli (rn, n) = l, to każdy dzielnik d liczby m· n ma postać d = dl . rh, gdzie dl
jest dzielnikiem 111, dz dzieluikiem n. Stąd
L(d,.d,)k~ Ld',
d, lm dlm"
d, I"
czyli ak(m)· ak(n) = adm· n). D

,,,,,j.
• ~ L-..zy<ki. El".""",,,,,, I~-:b. \\'.........~ 200()
148U_J. C byWN PWN:!OOb
82 Wykład 13
Jak dla poprzednich fUllkcji, tuk i teraz można podać cfcktywlIY wzór IU\ obli-
czenie wartości funkcji (1J:.
STWIERDZENIE 16.11
Jeśli n = n~"'1 pf' jest rozkładem kanonicznym liczby natumirlej n > I, to
r (0,+1).1: I
u,,(n) = rr
i-I
P,
ł
P' - I
-
' dla k E 1R, {O}.
IV szczególności
r
p (o,+lj - I
Ul (n) = rr
.",1
'
P• - I
.
Dowód
Z multiplikatywności funkcji Ul otrzymujemy
",(a) = rr q,(p~') rr (I + p~ + ... + p~") -rr., .

j
•
I
=
j
•
l
-
r (o,+l)ł
P,
pł_l'
-
I
D
Wykład 14
1 17 1 Funkcje arytmetyczne (2)
Z funkcją a związane jest bardzo stare zagadnienie liczb doskonalych.
DE:F"INICJA 17.1
J'vlówimy, że liczba naturalna N jlc'St doskonała, jeśli a(N) = 2N, to znaczy
liczba N jest równa sumie wszystkich swoich dodatllich dZielników różnych od niej
samej.
Przykład 17.2
Liczbami doskonałymi są: 6, 28, 496, 8128.
TWIERDZENIE 17.3
Jeśli liczba 2"H - l jest IJiertvsza, to liczba 2"(2"+-1 - I) jest doskonała.
Dowód
Niech N = 2"(2"+1 -1). Ze stwierdzeni!l 16.11 otrzymujemy
a(N) = (2"+1 - 1)·2"+1 = 2N. D
Przypomnijmy, że liczby postaci 2" - l nazy",'amy liczbami rvlersenne'a, a liczby

pierwsze tej postaci nazywamy liczbami pierwszymi Merscnue'a.

Każda liczba doskonała pa7'zysta ma postać 2"(2"+1 - 1), gdzie 2"+1 - 1 jest liczbą
pierwszą lvlersenne'a.
Dowód
Niech N doskollab} parzysb} i N = 2" N', gdzie n > 1 i N' jest
będzie liczbą
liczbą nieparzystą. Wykażemy, że N' jest liczbą pierwszą równą 2"+1 - l. Ponieważ
(j(N) = 2N = 2,,+1 N', więc z ltlultiplikatywuości (j i stwierdzenia 16.11 wynika, że
a(N) = a(2")·a(N') = (2"+1 - l)a(NI) i wobec tego 2"+1 -liN'. Jeśli przyjmiemy
NI = (2,,-1 -l). Nil, to a(N') = 2"+IN", gdzie Nil < N'. Z równości N' + Nil =
2"+lN" = a(N') oraz z tego, że N"IN' i Nil < N', wynika, że N' jest liczbą
pierws;'+ Sbld Nil = l i NI = 2,,+1 - 1. O
84 Wykład 14
Uwagi 17.5
Dotychczas ZUUllC są 43 liczby doskonale parzyste (por. illfol'lnacje po definicji 1L 15
na ss. 52-53). :'Jic wiadomo, czy istnieje nieskOllczenie wiele liczb doskonałych pa-
filystych. :'Jie wiadomo też, czy istnieje liczba doskonała nieparzysta. Sprawdwuo,
że jeśH taka liczba istnieje, to musi ona być większa od 10300 • W 2006 roku P. P. Nie-
Isen wykazał, :ile liczba doskonała llicparzysta (o ile istnieje) ma co najmuiej !) róż
nych dzielników pierwszych.
Następnym ważnym przykładem funkcji arytmetycznej jest funkcja I{, zwana
funkch Móhiusa.
DEFINICJA 17.6
Funkcja Mobiusa II określona jest uastępuj1lCO:
(I) ,,(1) ~ I,
(2) II( n) = (_l)k, jeśli n jest iloczynem k różnych liczb pierwszych,
(3) 1J,(n) = O w pozostałych przypadkach, to jest jeśli n dzieli się przez kwadrat
liczby naturalnej większej od L
Łatwo sprawdzić następujące
STWIERDZENIE 17.7
Punkcja .Afóbi'usa Ił jest multiplikatywna.
Z funkcją :Móbiusa związana jest następująca tożsamość:
TWIERDZENIE 17.8
2::M(d)~{I,
O,
jeśli
jeśli
n = l,
n > l.
dl"
Dowód
Niech n = n
pf' będzie rozkładem kanonicznym liczby naturałnej n > I. Dzielniki
d liczby n, dła których J-t( d) f- O maj.! postać 1, P\, 1.12, ... ,Pr, P;Pj (i < j), ... , PiPjPj;
(i < j < k), ... , PIP2'" Pr· Stąd
,
L/~(d) = lAl) + LP{p,) + LP.(PiPj) + L 1',(PiPjPI,) + ...
dl.. ;=1 ;<j i<j<k
+ "(1',," p,) ~ 1- G) + G) (;) + ... + (-1)' ~ (1 -1)' ~ O. D
Ważnym zastosowaniem funkcji :Móbiusa /-l jest następujące
TWIERDZENIE 17.9 (twierdzenie Mobiusa o odwracaniu)

JdU f jest funkcj(ł arytmetyczną i g funkcją określoną wzorem g(n) = 2:dlnf(d),
to
f(n) ~ 2::M(d)g
,I I li
Gl·
148~5_J. ObyWN PWN 2006
Dowód
LIAd)'1C) ~ L,,(d) Lf(d') ~ L I,(d)f(d') ~ Lf(d'). L"(d)

dl" dl" d'11 d"'I" d'l" dl 7
Z t\vierdzenia. 17.8. wynika, ze Ldl " II( d) = 0, jeśH d' f- n, czyH
"
I>(d)g Gl ~ Lf(d') L "(d) ~ f(n) D
'II" d'l" dl 7
Prawdziwe jest tabe twierdzenie odwrotne.
TWIERDZENIE 17.10
JdU f i 9 sq funkcjami arytmetycznymi oruz g( u) = LJln p.( d)! (J)' to
f(n) ~ Lg(d).
dl"
Dowód
L g(d) ~ Lg (:l ~ L L "(d')f (d~' l ~ L L" (,;~, l f(d')

dl" dl" dl" d'I1 dl" d'11
~ L
<ld'l"
I' (:~, l f(d') ~ D(d') L" C~, l ~ f(n).
d'l" dl'7
D
WNIOSEK H.U
Jeśli (j) jest funkcją Eulem, to
Dowód
Ponieważ n = 2::111" <:p(d) (por. twierdzenie 16.5), więc z twierdzenia 17.9 mamy
Teoril,? funkcji arytlllctyCJluych, a zwl,'\Szl;za teoriI,! fllukeji arytmetycznych lllul-

tiplikatywnych, IllOZl1a opisać, wykorzystującpojęcie splotu Dirichleta funkcji aryt-
metycznych.
DEFINICJA 17.12
Niech f i !J będą funkcjami arytmetycznymi. Splotem Dirichleta funkcji f i g
nazywamy fUllkcjQ arytlllctyCZIH! f * g okrdloną wzorem
(f. g)(n) ~ Lf(d) g

dl"
Gl ~ L
d,d,="
f(d,) g(M
148~S_J. t> by WN PWN 2tlO6
86 Wykład 14
Jeśli
oznaczymy przez I fllnkcjQ tożsamościowo rówllą 1, a przez Id funkcjQ
określollą wzorem ld(n) = n, to [atwo sprawdzić, że
1*I=d, 1*ld=al, '*Td!;=ak.

\-Viele wlasności funkcji arytmctyczllych, w szczególności multiplikatywllość
omawianych poprzednio funkcji (twierdzenia: 16.3, 16.7, 16.10, stwierdzenie 17.7),
a także twierdzenie lviobiusa o odwracaniu i twierdzellie 17.10 są prostymi konse-
kwencjami następujących twierdze6:
TWIERDZENIE 17.13
Zbiór funkcji arytmetycznych ze zwykłym dodawaniem i splotem Dirichlcta w cha-
rakterze mnożenia tworzy pierścień przemienny z jednością e określoną wzorem
e(n)={~: gdyn=l,
gdynf-1.
P.ierŚcień
ten nic ma dzidników zera, a element f tego pierścienia ma element
odwrotny wtedy i tylko wtedy, gdy 1(1) f- O.
TWIERDZENIE 17.14
Hmkcje multiplikatywne ze splotem Dirichleta jako działaniem tworzą grupę. Ozna-
cza to, że jeśli 1 i g są multiplikatywne, to 1 * g jest też multiplikatywna, a ponadto,
jeśli f jest multiplikatywna, to istnieje multiplikatyuma funkcja g taka, że f * g = e.
Dowody tych twierdzeó oraz szersze omówienie teorii funkcji arytmetycznych,

wykorzystujące pojęcie splotu, znajdują się w [4] (rozdzial 4.).
,
Cwiczenia
1. Oblicz !p(n), d(n), a(n), j1(n), jeśli:
(a.) fi = 2006, (c) n = 2008,
(b) n ~ 2007, (d) n ~ 2009.
2. Znajdź n, jeśli:
(a) d(n) = 6, a(n) = 28, w(n) = 2, gdzie w(n) - liczba różnych dzielników
pierwszych liczby n,
(b) :1In, 41n oraz d(n) = 14,
(e) >p(n) ~ 14,
(d) >p(n) ~ 16,
(e) )C'(n) = ~.
3. Sprawdź, że liczba 8128 jest doskonala.
4. Korzyslając z ćwiczeuia 16. ze s. 34, podaj mny dowód multiplikatywllości
funkcji Eulera.
5. Wykaż, ż;e jeśli n;) 2, to w pierścicniu Z" jcst !p{n) clcmelltów odwracalnych.
6. Udowodnij !H:l1;tl,)Plljflcc własności funkcji Eulcra:

(a) n;<: 3 => 21<p(n),
(b) din => ~(d· n) ~ d· ~(n),
(e) din => ,,(d)I,,(n),
(d) ,,(m· n) . ,,((m, n)) ~ ~(m) ·,,(n)· (m, n),
(e) ,,(m·n)~(m,n).,,([m,n]),
(f) <p(m· n) = <p(m)· <p(n) => (m, n) = l,
(g) <p(n) o;,;; n - vn dla liczb złożonych n.
7. Udowodnij następujące wlasności funkcji d:
~(.)
(a) I1d!" d = n ' ,

(b) (d(m"), n) ~ l,
(e) d(n) <; 2;;;.
8. Udowodnij następujące wlasności funkcji a:
( a) '" l
L..-dl" d = " '
0(")
( b) J'cśli n > 1 i n = pal ... pa' to 1 > -::-h > (1 _ ..L) ... (1 _ ..L)
l r , 0\"1 1'1 1', '
(C) 0;:,"1;<: 1+ ł + ... +~,
(d) u(n) > n + vn dla liczb złożonych n.
9. Wykaz, że przy ustalonym k E N równanie a(n) -
.
rozwlązan.
. k ma skoIlczenie wicie
10. Oblicz:
(a) J.t(n)·,An+l)·J-t(n+2)·'l(n+3),
(b) L;~, ~(j!),
(e) Ldl"I«d)d.
11. Wykaż, ze jeśłi 1 jest funkcją arytmetycznąmultiplikatywną., to funkcja F( n) =
L,j I" 1( d) jŁ'St też multiplikatywna.
12. Korzystając z ćwiczenia 11., podaj inne dowody twierdzel't 16.7 i 16.10.
13. Udowodnij, ze jeśli F(n) = Ldl,J(d) jest funkcją multiplikatywną, to funkcja
1 jest też Illułtiplikatywlla.
14. Wykaz, ze jeśli 1, g są funkcjami multiplikatywnymi, to funkcje 1.g oraz ~
(9 -# O) są też lllultiplikatywllc.
15. Wykaż, że jeśli funkcja lllultiplikatywna 1 spełnia warunek: dla dowolnych
m,n E N zachodzi równość l(m + n) = l(m) + l(n), to funkcja ta lila po-
stać f(n) = n dla każdego n E N, czyli 1 = Id.
16. Udowodnij następujące wzory:

(a) Lm,,,(d(m))3 ~ (Lm,,,d(m))',
(b) Lml"a(m) = Lm!" ;',d(m),
(c) Lml" ~O'(m) = Lm!" md(m).
'B" .... B, "'" ""
88 Wykład 14
17. vVykaż, że jeśli n::f:. 6 jest liczbą doskonałą parzystą, to n =1 (mad 9).
18. Sprawdź, ze jeśli N = 2" . (2"+1 ~ l) jest liczbą doskonalą, to ndlN d = N"+I
0"'" ~(N) ~ 2"(2" - 1).
Własności asymptotyczne
18 funkcji arytmetycznych (l)
Omówimy teraz naj prostsze własnoścl asymptotyczne podstawowych funkcji aryt-

metycznych, to znaczy b~dziclIlY badać, jak zachowllją si~ te funkcje przy argu-
mencle dążącym do nieskOllczoności. Na początku podamy kilka własności funkcji
Enlcra.
STWIERDZENIE 18.1
(1) łim,,--+oo rp(n) = 00,
(2) -l· 'ci!!! = 1.
llll,,_oo "
Zallilll podamy dowód stwierdzenia 18.1, popatrzmy na graficzue ilustracje po-

wyższych granic (rys. l i 2).
~(n)
150
1·10 ••
UO
•
120 •
110 • •
••
•
100 •
• •
00
•
80
70
•
•
•
• • •
•
•
•
•
••
..
60 • • • •
50
• • ..• • • •
40
•
• •
•
•
.. •
•
•
30
20
••
.. :.
•
.. •
• •
•
.. •
10 '. ., • •
M';'·'··-,· .
lO ?O 30 40 50 60 70 80 90 100 110 120 130 140 150 1l
Rysunek l
18. Własności asymptotyczne funkcji arytmetycznych (1) 89
l
.. ..• • •• • • • •• • • • • •• .. • • •• •
•• •
• •
• •
•
•
• • • • • •
.. ..
•
•
•
•• • • •
•
• • • • • ••
•
... •
• . .. •
•
• '. • •
• • •
•
10 20 30 -lO 50 60 70 80 90 100 IIQ 120 130 140 150 n
Ry~ullck 2
Dowód
(1) .Jeśli]J przebiega zbiór liczb pierwszych, to iiml'_oo ",(p) = limjJ--+oo(I,-l) = 00,
zatem Iim,,_oo'P(n) = 00. \Vystarczy teraz wykazać, że dla dowolnego k E N
rówllauie rp(n) = k ma skoIiczcnie wiele rOZWil!ZaÓ w liczbach naturalnych n.
Rzeczywiście, jeśli n = p~i; ... p~r, to z równości i.p(n) = k wynika, że k =
pf'-' ... p~.-l (Pi - 1) ... (Pr - 1), stąd ilość liczb pierwszych PI, ... ,p" które
spełniają pO\vyższą równość jest sko6czona, podobnie liczby Ol, .•. , nr mogą
przyjmować tylko SkOllczcnic wiele wartości.
(2) Jeśli p przebiega zbiór liczb pierwszych, to lilll rl --+ oo <pi;') = lim p --+ oo r~ł = 1.
Stąd i z tego, że !p(n) < n, wynika równość tim,,--.oo 1":,") = l. D
Dokladniejsz,! illformację o szybkości wzrastania funkcji rp daje następuj,!ce
TWIERDZENIE 18.2
Jeśli a> O, lo
. ~(n)
hm
"--+00 n
l =
(1
00.
Dowód tego twierdzenia opiera się na następującym lemacie:
LEMAT 18.3
Jc.1li f jest funkcją rrmltiplikatywnq i f(p"') --+ O dla 1)m _ 00, gdzie p E !P' oraz
rn E N, to fen) --+ O, gdy n --+ 00.
Dowód
Ponieważ f(pm) --+ O dla pm --+ 00, więc f musi spełniać następujące warunki:
(i) istnieje stala dodatnia A taka, że If(p"')1 < A dla wszystkich 1) E !P', m E N,
(ii) istnieje stala dodatnia B taka, że jeśli pm > B, to If(p"')1 < 1,
(iii) dla dowolnego c > O istnieje taka liczba N(c) E N, że jeśli p'" > N(c), to
I/(p"')1 < E.
Oczywiście stale A i B nic zależ,! od c, m, p, liczba N(c) zależy tylko od c.
El",,,",.,,,,, ,rot"' lirJt. wors:z..... 200ó
,. r Z,"IIzydi.
148SS_J. [> oyWN I'WN 2006
90 Wykład 14
Niech n = pf' ... p~; b\,,<lzic rozkładem kanonicznym liczby n > 1. Ponieważ
funkcja 1 jest multiplikatywna, więc
(1)
Rozpatrzmy \vszystkie potęgi l/" liczb pienvszych i niech C będzie liczbą tych potęg,
które nic są większe od B. Liczba C nie zależy od n i E. Korzystając z warnnkn (i),
otrzymujemy, że modul tych czynników f(p;~i) w rozkładzie danym \vzorem (l),
dla których pf; . ; ; H, jest mniejszy od AC. Pozostałe czyuniki tego rozkładu są, na
mocy (ii), mniejsze co do modułu od l.
Zauważmy, że istnieje skOllczenie wiele liczb naturalnych, których rozkład ka-
noniczny sklada się wyb!cznie z czynników postaci li', gdzie p" ..;;; N(E). Niech P(E)
będzie największą z takich liczb. Jeśli weźmiemy teraz n> P(e), to w rozkładzie
kanolliczllylll liczby n jest co najnllliej jeden cZYlłllik postaci p", gdzie p" > N(E).
Do czynnika tego możemy zastosować warnnck (iH). Ostatecznie jeśli n> P(E), to
1/(n)1 < AC. g,
a więc I(n) -+ O, gdy n -+ 00. D
Dowód twie1Ytzenia 18.2
Jeśli (T > l, to teza twierdzenia 18.2 jest oczywiście spełniona. Niech (T ..;;; l oraz
,-o
I(n) = ~(,,); zauważmy, że funkcja 1 jest multiplikatywna. Zatem z lematu 18.:ł,
wystarczy wykazać, że 1(11"') -+ O dla pm -+ 00, gdzie p E IP i 111 E M. Tak
rzeczywiście jest, gdyż
m _ p'n(I-<l') l 2
/(p ) - ,"("m)
"r '
--=-'=----',-"
- p"'''' (l - -) ~ -pm-o' D
Wykład 15
Własnościasymptotyczne
19 funkcji arytmetycznych (2)
Podamy teraz kilka własności asymptotycznych funkcji d liczby dzielników.
STWIERDZENIE 19.1
Dowolna liczba naturalna k;;;. 2 jest punktem skupienia ciągu {d(n)}~l' a WlęC:
(1) lim,,--+ood(n) = 2,
(2) lim,,--+ood(n) = 00.
Dowód
Niedł k b~dzie dowolllf! liczb,! lIaturallll! ;;;. 2, 1)1, lJo;!, ... ciągiem kolejnych liczb
pierwszych. Przyjmując x" = p~-j, ze wzoru na funkcj~ d(n) w stwierdzeniu 16.8
otrzymujemy lim,,--+oo d(x,J = lim,,--+oo k = k. D
Następne dwa twierdzenia ilustrują szybkość wzrastania funkcji d w stosunku do

lIiektórych funkcji elementarnych. Popatrzmy najpierw na wykresy ci,!gu {d( n)}~ 1
(rys. 3) oraz ciągu {d~;')}:1 (rys. 4).
d(n)
18
lO
•
12 • • • • • • •
10 •
8 • •• • • .. -.
, .. . • •
4 ... NNN_N . ... . . . .. . - .-
• •
2 •••••••••••••••
•
.. ... .. . ..... •
.. .. •
•
10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 n
Rysunek :3
'ą8JJ·j. Ci 0' W" f W lO _!Dl
92 Wykład 15
d(n)
,.
l
• • •
• .
•• •
, • ••
.. •
•• • •
...
••••••• H
H
..............-
.': .' •
•••••••
' . . •
'H~"~
~
• • '. "
"H'
~ ._M··
10 20 30 40 50 60 70 80 90 100 IW 120 130 140 150 n
Rysunek 4
TWIERDZENIE 19.2
Jeżeli Ó > 0, to d(n) = 0(n 6 ), czyli
cl(n)
!im - , - =0.
" ..... 00 n
Dowód
Puukcja J(n) = d.;~) jt."St Illultiplikatywlla, a wi!,;"C na mocy lematu 18.3 wystarc"'y
wykazać, że f(p"') ----Jo O dla pm _ 00, gdzie p E ]p i 111 E N. Tak rzeczywiście jest,
gdyż
rn+12·m, 2 logpm 2 log 11'''
1(,,") ~ pm6 "'"
"~T =-=--"
-- .
pm6 - pm6 log p <; - -
log 2 .
pm6' ""s-- o
TWIERDZENIE 19.3
Dla każdegaLl > O istnieje ciąg ni, /112, ••• liczb natumlnych, laJ.-i że
. d( n,)
IIm = 00.
i ..... oo (logn;)Ll
Dowód
Przy ustalonym .1 > O niech k będzie tab} liczbą ealkowitf}, dla której zachodzą
nierówności: k:S;; .1 < k+ l, a Pk+l będzie (k+ l)-szą liczbą pierwszą. Przyjmujemy
ni = (2·3·5··· Pk+d; dla i = 1,2, ... Ze wzom na fnnkcjl; d(n) w stwierdzeniu
16.8 otrzymujemy cl( ni) = (i + l)k+1 > i~+1. Ponieważ
pHI = (
logn.
'
),,+1 > c(log nf+l.
log(2·:1···PHd "
gdzie c jest stalą dodatnią, więc d( ni) > c(log rti)k+l. Przyjmując Ó = k +1- .1,
otrzymujemy
d(,.,) ,
Ll > c(logn;) - 00 przy 1 - 00,
(Iog n, )
zatem {ni}~1 rzeczywiśóe spelnia tezę twierclzellia. o
148~S_J. t> by WN PWN 2tlO6
Uwaga 19.4
:Można wykazać, że dla każdego f; > O istnieje liczba naturalna N(E) taka, że
d{n)<2{l+~)~ dla n>N(E)

oraz istnleje nicskOIiezcnie wicie liczb naturalnych n, dla których
d(n) < 2(I-e)~.
'T\vierdzcnia o asymptotycznym zachowaniu się funkcji arytmetycznej formuluje

się często za pomocą fUllkcji sumacyjnej.
DEFINICJA 19.5
Funkcją sumacyjną funkcji arytmetycznej f nazywamy funkcję F określol1ą
wzorem
"
F(n) ~ 2:)(;).
j=!
Zwróćmy mva.gę, że funkcja F~') określa średnią wartość funkcji f dla liczb natu-
ralnych z przedziału [l, n].
Przytoczymy teraz bez dowodu trzy twierdzenia traktuhce o asymptotycznych
własnościach funkcji sumacyjnych funkcji Eulera "P i funkcji d liczby dzielników.
Przypomnijmy, że zapis f(n) = 0(9(n)) oznacza, że dla n E N iloraz ~I:l jest
wielkością ograniczoną.
TwrERDZENI8 19.6 (Mertens)

Jeśli rp jest funkcją sumacyjną funkcji E-ulem <p, to
3n'
<"/i(n) = -2 + O(nlogn).
n
Dowód tego twierdzenia można znaleźć w [2] (rozdzial 6., twierdzenie 22.) lub
w [12] (na s. 145).
TWIERDZENIE 19.7 (Dirichlet)
Jeśli D jest funkcją sumacyjną funkcji arytmetycznej d, to
D(o) ~ nlogn+ (20-1)n+ O(;;i),
gdzie 'Y jest stalą Eutem.
Dowód tego twierdzenia można znaleźć w [2] (rozdzial 6., twierdzenie 9.) lub
w [4] (rozch.d<tł 4., twierdzenie 4.14). Ostatni człon, O(JJl), w powyżsqm wzorze
można poprawić do o( n{,+~) (H. Iwaniec, C.,1. :\1ozzochi). Istnieje przypuszczenie
(jest to tzw. problem dzielników), że zamiast O(jn) można też wziąć O(n:l+~).
Wiadomo lIatomiast, że wzór tell nie jest prawdziwy, jeśli zamiast o( y'n) przyjmie
"ę 0(0 1) (G. H.,·dy).
Na zakoóczenie podamy kilka wlasności asymptotycznych funkcji JT(x) określo
nej w definicji 10.9. Funkcję tę mozna rozpatrywać na zbiorze liczb rzeczywistych
lub na zbior'lC liczb naturalnych. :-Jie istnieje w'lór po'lwalający efektywnie oblic'lać
'ę"H·j. C> 0' W" f W lO _ _
94 Wykład 15
wartości funkcji 7r; wynika to z dnżej nicregularności pojawiania si\; liczb pierwszych
w zbiorze liczb naturalnych. lvIimo to, dość dużo można powiedzieć o jej asympto-
tycznym zachowaniu się (por. twierdzenie 10.10). Zauważmy, że z nieskOlkzoności
zbioru liczb pierwszych wynika natychmiast następujące
STWIERDZENIE 19.8
lim 7r(x) = 00.
,-=
Dwa następne tWierdzenia określają zachowanie Się funkcji JT w stosunku do
pewnych fUllkcji elementarnych.
TWIERDZENIE 19.9
Istnieje taka stała dodatnia c, że dla wszystkich liczb rzeczywistych x # 2 zachodzi
nien5wność
JT(X);;" clogx.
Dow6d
Dla danej liczby rzeczywistej x ;;,. 2 oznaczmy przez B(x) ilość liczb naturalnych
bezkwadratowych, mniejszych lub rówllych x. (O liczbie natural11ej większej od 1
mówimy, że jest bezkwadratowa, jeśli nie jest podzielna przez kwadrat Hczby
calkowitej wi(,?kszej od 1.) Zauważmy, że
E(x)::;'
?
:r:-l- -=-
22 - -=-
32 - '"
= X+X-X(I+ ~
22 +~+
32 '" ) -1 = X(2- JT2)_1
6'
Z kolei liczb bezkwadratO\vych ,;;;;: x jest co najwyżej 271"(:Z) - l, skąd
,
271"(:Z) _ 1 ;;,. x( 2 - ~ ) - 1.
Pouieważ dla x;::: 8 prawdziwa jest nierówność x(2 - :') ;;,. xł, więc
(I) gdzie X;;" 8.
(1) jest również prawdziwa dla 2 ,;;;;: x < 8. Po
Łatwo sprawdzić, że lIierówllość
zlogarytmowaniu obu stron nierówności (1) otrzymujemy ostatecznie
1
JT(x);;" l logx. D
2og2
TWIERDZENIE 19.10
lim JT(x) = o.
:z~oo X
Dow6d
Oznaczmy przez s(x, k) ilość liczb naturalnych';;;;: x, które nie SIl podzielne przez
żadm! z k początkowych liczb pierwszych ])1,"" Pk" Łatwo sprawdzić, stosując
metodę wlączania-wylączania, że zachodzi wzór (por. [4], lemat 4.22)
(2) ,(x, kHx] - I:

I';;;i';;;o,
[X]
p,
+ I: [-;-,-:]
Pj
l';;;i<j';;;o, 1,
148~S_J. C by WN PWN :lOC'6
Ponieważ 1I"(x) " $(x, k) + k, wiQ<: ze WZOrtl (2) wynika, że
1I"(x) < x- L .::. + L ...:!- - ... + 1.:+2.1:

l';"" Pi l"i<j:;;'" Pi Pi
=. I'i''''II (l-~) P,
+k+2'
<xII (1_~)+2kH,
U;;i'ł P,
Z twierdzenia 11.3 wiemy, 'Że nU;;'I:(l - ~) - O, gdy k _ 00. Wcimy e > Q.

Wówczas dla odpowiednio du'ŻCgo k mamy: nh';;i'.l:(l - ~) < ~ i odpowiednio
dużego x: 21;-+1 < 12:.
Sl1ld ostatecznie
< <
1I"(x) < 2:1:+ 2 x =ex,
a to dowodzi, że lim.._ oo ..~:z) = O. D
,
Cwiczenia
L Sprawdź, ze lim,,_oo 'f~,ltl = o.
2. Sprawdź, że lillln_oou(n) = 00.
3. Sprawdź, że:
l,
(a ) ...!.!!!,,_:>c " = l,
,,(n) (b) -1'-
IIl1 n _
"'(fI}
oo ---;;- = 00.
4. Udowodnij lla5tępUjącc własności funkcji 17"(x):

() 0'1' E D t
3 Jo.:;;,;.11' ~,CI
... (,,-l}
pl
< IfC,,)
p'
(b)jcm1lL~PU{I), to 'tn)<If~/),
(e) 1l"(X)" lll(lll x) dla x:;' 2.
(Wskazówka: Skorz,ystaj ze stwierdzenia 10.8.)
5. Niech f, P bl,:"<i<l flltlkcjullIi arytmetycznymi takimi, 7.e F(1l) = Ldl,,J(d). Wy-
kai, 'e 2::;'=, F(j) = 2::;'=, f(j) [y]
6. Korzystając z poprzedniego ćwiczenia, wykaż, że:
(a) 2::;~, d(j) ~ 2::;., [y],

(b) 2::;~, .(j) = 2::;~,j[7J,
(e) 2::;' ,1'0')[71 = l.
7. Niech dla s > [ funkcja <
bądzic okrcślona wzorem «8) - L::l ,~. « llOSI
uazwę funkcji dzeta Riemanna).
1485513.08' WIO f WN_
96 Wyklad 15
(a) Niech f: fil _ Cb~lzic funkcją multiplikatywną oraz nicch szereg E:l l,!;)
będzie zbiciny bezwzględnie. Udowodnij, że zachodzi następujący wzór Eu-
lem:
(\\'skazówka:
~ "f(n) + "f(n)
II (I + f(p) + f(p')
p~s
p'l'"
+ ...)
l)loJ L.... n'"
n~"
L.... n ~
nEA
gdzie A = {n E N: 11 ~ Z, VpEp piu => P";;; x}.)

(b) Kor.lystając ze wzoru Eu)cra, udowodnij następujące równości:
( 1) "":>o ~ =
Ln 1,,'
«(I-II)
((I
dla $ > 2'
(2) L:::, ~ ~ (((s))' dla s > l,
(3) L:::' 'l:' ~ «sK(s - I) dla s > 2,
(4) L:"';:' ~ ((s))-' dla s > 1.
8. Niech n będzie dowalili} lic-J;bą naturalną. Znajdź granice ciągów
(a) n, I'(n), 1'(I'(n»), ,

(b) n, d(n), d(d(n)), ,
(e) n, urn), u(u(n)), .
9. Wykaż, że dla lxI 2

n' < lp(n)a{n) <
2" 1}.2.
101. Sprawdź, że liczba II .. , l ma co uajwyżej 364 różne dzielniki.

'-v-'
1977 """Y
102. \Vykaż, że O'(n) < n1 dla każdego n > 2.

103. Znajdź wszystkie liczby naturalne n, dla których lp(n) = d(n).
104. Znajdź wszystkie liczby picrwsze p takie, że suma dzielników liczby pl jest
kwadratem liczby całkowitej.
,,,,,j.
• ~ L-..zy<ki. El"••,"",,,,,, I~-:b. \\".........~ 200()
105. Udowodllij tożsamość Hermite'a
[xl + [x+ ;,] ++ [x+ n:l] ~lnxJ, gdzie x E lR, n E N.
lOG. Oblicz wartość Silmy [JI] + [J2] + ... + [./n 2 l].

107. \\'ykaż, że ostatnią cyfrą liczby doskonalej parzystej jest 6 albo 8.
108. Udowodnij, że 6 jest jedyną liczbą doskonalą bczkwadratową·
109. Oblicz wartości sum:
(a) S,(n) ~ L".I,(d) '1' m,
(h) S,(n) = L'" L~I",(d)l, (1.).
110. Udowodnij, że II(n) = L l"o~II e2ll"i;.
(0.11)=1
111. \Yykaż, że jeśli funkcja f jest całkowicie multiplikatywna U(mn) = f(m)f(n)

dla dowolll:ych 111, n E N), g, h ~l funkcjami arytmetycznymi, to f . (9 * h) =
U· g). U' h), gdzie· oznacza zwykle nUlożenie funkcji. Wykaż, że zał()'"~C.llic
całkowitej lIIultiplikatywności funkcji f jest istotne.
112. Kiech f będzie funkcją arytmetyczną spelniającą warunki:

(I) f(N) C N,
(2) f jest ściśle rosnąca,
(3) istnieje j E N, j> 1, takie że fu) = j,
(4) f jest 1I1ultiplikatywna.
\Y,ykaż, że f(n) = n dla każdego n E N.
,,,,,j.
• ~ L-..zy<ki. El".""",,,,,, I~-:b. \\'.........~ 200()
148U_J. C byWN PWN:!OOb
Bibliografia
tli Burtou D., Elemenlu'1l Number Theorg. ADrII. and Bacon. 800;toll. 1976.
(2) Chandnlliekhamn K., "ltrod~liQn to Anolytic ,,""mbeT Theory. Sprioger Verlag. ~ev.' York 19GB
(istrueje Ill'U'klad TOiWjski).
[3] Crandall R.. POm('Tllll(~ C.. Primc ",,,mbeN. .4 Compuu.tionai Perspet:!ive. Sprillgcr. 2005 (~nd
ooitioll).
[-I] Narkiew~ W .. Teoria /ic:b, "'ydallmict"..o Naukowe PWN, Warszawa 2003 (ll'1'dallle lnede).
[al l'\iwll 1.. Zncwml:U\ II.. An Jn/roductioll to Me 17100"1 ol NlIm1Jer"3, John Wik-y k Sonll, New York
1980.
[6] Rose H.E.. A Couru in Number Thoory, Oxford Uni\'ersity Press. 1994 (liCCOlld cditlon).
[7] Sierpiński W' o A'lł'mel~'1l teoretyczna, Biblioleka ~Iatemat~'czlla, I. 7. PWN. Wanll.l\w'l\ 1969.
[8J Sierpiliski W., Teoria liab, cz. 1, Monografie ~Ial('mal)'czne, L 19, Warszawa Wrocław 19:M,l.
[9] SicrpillSki W., Teoria Iic:b. cz. II, ~lonogrllfic fo.llltcmatycznc, t. 38, P\\"N, ""llTSZilWIl 1959.
[10] Sicrl'itiski W .. ElemCII/OI'll TIIf:JJry ol Numocl'"$, PWN, Wan;7....wa 1987 (W)·c1a"ic <!nlgic pod ".'dakcją
A. Schinzla).
[IL] ""cil A., Number Theory lor 8cgilllleN, Springcr Verlag, Ncw York 1979.
[121 Winogradow J., ElcmcIlty teol"ii liczb, PWN, Warszawll 1954.
[131 y,.ll S. Y., Teol"io liczb Ul i"lo.mQtyce, W)'dawnictwo !\aukoll"c P\\'N, \\"arsza,,",. 2006.
,,,,,j.
• ~ L-..zy<ki. El"••,"",,,,,, I~-:b. \\".........~ 200()
Skorowidz
Aksjomat indukcji 1 liczb)' 19

algorytm Euklidesa 5 flwkcja 8l'ytIDCtyczl\8 79
dzeta Riemanrm 95
Berlranda JXII>tulat 50 EuJera 32
Bineta "wr dla liczb FibonfICCiego 21 liczby dzielników.' I
MObiusa 8-l
Canch~··eg(J Fa«.'}"l:l t"'icrd:reuic 58 lllultiplikatpl"lla 79
co:h)' l>Odzidności 31 :r(x), ilość Iit::'lb pierwsz)'Ch "x 18
chińskie t".. icrdzcuic o res?tl\Ch 37 sumacyjna 93
ciąg Fibonl\CCiego 19 silmy dzielników.·, u 81
sum k-trch poto;x dzielnikó...., "l 81
Dirichkta splol 85
twierdzenie o fuukcji ilulIIneyjncj funkcji Gaussa lemat 68
liczby dzielnikó..· 93 Goldbacha hipoteza 5-1
o Liczbach pierwszych w ciągu
arytllłel yCZllym l7 Hipoteza Goldbacha 5<1
dzielnik 3 Waringa 75
Hurwitz-R twicrdz.cllie 62 63
Erato:stenesa ~ito I l
Eukli(k"", .. Igor)'t'" 5 Indeks licz h)' modlllo 11\ 11I"I-.V 1>Od~tawic ,. 4 I
Eul<:ra funkcja 32
twierd~.{'lłie 32 Klasa re8zt mtXilllo :ID
o lie7.bach doskolUllych 8;\ kOllgruclItja 30
o re~zlach kWlldratowyth ;17
Lagl"imgc'" twierdzclIi.:: o liczhie r07.wi'!7.all
Fareya ulamki 58 kongrnelJcji :16
Fermata liC'"llx\ 47 o pr7.edstawieniu lic'lby naturnlnt·j
równanie 15 w postaci slIm)" C'"ltercch kwadrnt6w 73
twi<:rd~.cni<: mnie 33 Legendr..,'" sJ"'"bol 67
o IlrlCtistawicniu liC'"l.hy llierwll"l.ej ... postnei lemat GalL'lsa 68
liWII)· dwóch kwadratów 70 liczba be:i:kwadratowa 94
o róv.·u8uiu Xl + 1/1 '" z~ Hi doskonała83
wjcLkie 15, Hi Fermata 47
• ~ Lyzy<ki. El"••,"",,,,,, ,,,,,j. I~-:b. \\'...... ,,~ 200()
148U_J. C by ....N PWN:!OOb
100 Skorowidz
li<:;.I.", pierwsza 9 chii,skic o rt.'S';.tach 37

ll6Cudollier\\1>Za 55 Dirichleta o funkcji sumacyjnej funkcji
SierpiiJskicgo 56 liczby dzielnikó 93
złożona 9 o liczbach pier :;z}"Ch .... ciąglI
af}·tlllct}·czn}·m 47
li<:.tbr Fil>Qua<,.'Cicgo I()
Eulera 32
pierv."l>ze bliiniacze 52
o liczbach doskonałych 83
wzgłędnie picf\\~ "
o resztach k....admtO'l')·ch J7
Luca:;a ..wr dla liczb Fibonaccicgo 21
fermata male 3J
o przedstawieniu 1icz~' pien'SU'j w IlOo'itaci
Mediana ulamkó9.' 58
SUIII)' dwóch k....'adrntów 70
Merscnne'a liczba 52
o ró....naniu Zl + yl =: ~1 16
McrtenS8 t ..·ierdz<'nie o funkcji SUlIlao:'\'jlK"j
....ielkie 15
funkcji Eulere 93
Hurv.·itza 62, 63
Mobin.'>łł fllnk..-ja 8-1
Lagrnnge·a o liczbie roz";ązlul kollY1K"n<:ji
t .... ie«b.enie o ()(hnlM;IlUiu &1
36
lIIodul kongmc:neji 30
o przedsta....ielliu Ikzbr IIl\turaJncj
.... postaci SIImr cztcll'd! k911.dmt6w 73
Naj,,;ększr ""'Sp6łllr dzielnik 3. Mertensa o fnnkcji sumacyjnej rllllkcji
lliereszta k..'adratO'l'a 1lI0dulo 37 EnJera 9J
MObillli8 o od....TaClllliu 84
P",",il'l>"tek p",",'OlU)' modulo m 1-1 o dzieleniu z resztą J
Pitagorasa równanie 15 o I'ierv..iastkach pierv.'Ot l1)'ch II
postać kanoniczna 10 o rozmłfSZCU'uiu liczb pier.....s zreh 19
postulat Ikrtranda 50 '\"ilsona :la
prawu wzajelllllOlk:i l'C:Sl:t kwadratov.')'ch 69 zasadułcn' arytmct}·ki 9
problem dzic!nik(n,' 93
prJ.)"'SlawlIllie modulo 30 Uklad reli'lt pełny 31
zreduko....any 32
Redukt ułamka hlllcuchov.l'go 24 ulamek lai,,:;udl()\\·,y SkOlll;ZOll}' aryllllet}'C'l.lIy
relSztll kwadratO'l·a 1IIo<lulo 37 2:J
Riemanna funkcja <lzeta 9ti nicskollczony arytmetyczny 21
równllnie r1ioflllll)1:;l'.nc II ulamki fareya 58
fermata 15
liniowe 14 Waringa hipoteza 75
Pitagora.':ill 15 wielokrotność 3
Wilsona twierdzl'nic 35
Si<.;rl'il',~kil'go Iiczl>lI 5G wzór Bincta dla liczb FihollJtcdego 21
sito EratOlit<:n...' llfl II Lucasa dla liczb fibonllcciego 21
splot Diricllleta 8ti
symbol Lcgcndre'a G7 Zasadni<:l.e twierdzenie aryj lllctyki !J
zasada indukcji matematy<:.tllcj l'.upclul'j l
Trójka pitagorejska 15 maksimum l
twi<.;rdzclLic Callchy'cgo FilreYII 58 minimum I

Marzantowicz W. - Elementy Teorii Liczb

Uploaded by

Copyright:

Available Formats

Marzantowicz W. - Elementy Teorii Liczb

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Marzantowicz W. - Elementy Teorii Liczb

Uploaded by

Copyright:

Available Formats

I I Spis treści

typn MATHEMATICA, MAPLE czy DERJVE, które zawierają bogate biblioteki

[ "1 I Liczby naturalne i całkowite

Konsekwencjami aksjomatu indukcji są:

TWIERDZENIE LI (zasada maksimum)

TWIERDZENIE 1.2 (zasada minimum)

TWIERDZENIE 1.3 (zasada indukcji matematycznej zupełnej)

TWIERDZENIE 2.1 (o dzieleniu z resztą)

(1) dla i dlb,

Następujące twierdzenie podaje podstawową charakteryzację liczb względnie

TWIERDZENIE 2.11 (Euklides III w. p.n.e.)

gdzie O < 1""1 < b.

1"",,_2= q"T,,_1 + Tr" 0<1""" < 7"""_1,

Aby to wykazać, wystarczy udowodnić na.<;tępujłlcy

Zasaclllość algorytmu Euklidesa wyuika z ciągu rówIlości

(a,b) = (b,7""d = (7""1,7""2) = ... = (7"",,_1,7"",,) = (7"",,,0) = 7""". D

10. Oblicz (817HI, 52003, 33649).

I '3 I Liczby pierwsze

Dowód zasadniczego twierdzenia arytmetyki

gdzie 1 < nI < n.

Pl :;;; P2 :;;; .. . :;;; Pn

gdzie Pi E lP, aj E N, Pl < P2 < ... < p,-.

Z definicji liczby pierwszej nic wynika bezpośrednio nicskoóCZOllOŚĆ zbioru lP.

TWIERDZENIE 3.8 (Euklides)

7. Sprawdź, że dla każdego n E ]\i, {3} nie wszystkie liczby n, n + 2, n +4 są

1. Wykaż, że każdą liczbę naturalną n można przedstawić

2. Wykaż, że każdą liczbę naturalną n można przedstawić jednoznacznie w postaci

7. (a) Niech (a, b) = d, (a', b') = d'. Wykaż, żc

(aa', ab', ba', bb') = dd'.

(b) Sprawdi, że jeśli n E H, to (a, b)" = (a", b").

14. Dla n E N, n > l, funkcje j, g określamy wzorami:

16. Niech n będzie liczbą naturalną nicparzystą większf! od 3,

I '4 I Równania diofantyczne

Nazwa tego typu równa{\ pochodzi od imienia greckiego matematyka Diofalltosa

x=2st, y=i_t 2, Z=S2+ t 2,

Korzystając z powyższych rozważaiI, można udowodnić następuhce

TWIERDZENIE 4.5 (Fermat)

3. Znajdź wszystkie trójki pitagorejskie x, y, z, takie że z < 30.

6. Znajdź wszystkie rozwiązania w liczbach całkowitych równania danego wzorem

8. Znajdź wszystkie trójkąty prostokątne o bokach całkowitych a, h, c, takie że

dla pewllych liczb całkowitych m, n.

13. Rozwiąż w liczbach całkowitych następujące równania:

I '5 I Liczby Fibonacciego

fi = l, h= l, /"+1 = i" + /"-1 dla n = 2,3, ...

/m-H. = /"'-1 /n + /m /"+1 .

I '5 I Liczby Fibonacciego

fi = l, h= l, /"+1 = i" + /"-1 dla n = 2,3, ...

/m-H. = /"'-1 /n + /m /"+1 .

i"'+1:+1 = im+k + im+k-1 = im-lUk + ik-d + i",(j1:+1 + id

Tt_Z = qkTk_1 + T"k,

Z lematn 5.5 otrzymlljcmy ciąg równości (im,f,,) = (f,,,ir,) = (jr'J,j"1) = ...

Wyprowadzenie wzoru Bineta

3. Udowodnij tożsamości (a)-(f) ze s. 21.

Rozpatrz dwa przypadki w zależności od tego, czy wielomian b + ax - x 2 ma

Do zapisu powyższego ulamka używa się często symbolu

Prawd.ziwe jest również stwierdzenie OdWl'Otlle.

T,,_Z = T,,_Ia,,_1 + T",

Liczby rzeczywiste niewymierne ró\vnież można przedstawić w postaci ułamków

Zauważmy dalcj, że liczbę

otrzymuje się z liczby 6"_1 poprzez zmianę w przedstawieniu la{lCucbowym 6"_1