Teoria liczb 2010, sem.IV,

B.Bajorska, O.Macedo«ska

Wykªad 1.

Liczby naturalne

Bóg stworzyª liczby naturalne, a caª¡ reszt¦ stworzyª czªowiek

Leopold Kronecker

1

Pitagoras 572-497 p.n.e.,

Arystoteles 384-322 p.n.e.,

Euclides 325-265 p.n.e..

1 Elementy historyczne

Pitagoras »yª w VI wieku p.n.e (ok. 572-497 p.n.e.). Pochodziª z Samos

w Grecji. Studiowaª w Egipcie i Babilonie.

Zaªo»yª szkoª¦ pitagorejsk¡ w Krotonie, w greckiej osadzie na poªudniu

Wªoch (na obcasie Wªoskiego buta).

Pitagoras dzieliª uczniów na sªuchaczy i Pitagorejczyków. Po trzech la-

tach nauki kursu trivium

2

, w skªad którego wchodziªy: logika, gramatyka

oraz retoryka, sªuchacz mógª by¢ przyj¦ty do klasy drugiej, klasy Pitagorej-

czyków.

Pitagorejczycy wierzyli, »e musi istnie¢ spajaj¡ca ‘wiat harmonia, która

wszystko utrzymuje. Motywacj¡ »ycia jest poznanie tej harmonii jak naj-

gª¦biej, a drog¡ do jej poznania byªo studiowanie czterech mathemata, czyli

przedmiotów nauki: geometrii, arytmetyki (de facto teorii liczb), harmonii

(de facto muzyki) i astrologii (de facto astronomii).

3

Pitagorejczycy tworzyli rodzaj bractwa rycerskiego, mieli wspólnot¦ wszel-

kich dóbr, wszyscy znali wszystkie tajemnice szkoªy i byli zwi¡zani przysi¦g¡

o ich nieujawnianiu.

Przez dªugi czas panowaª zwyczaj, by twierdzeniom nadawa¢ imiona wy-

bitnych m¦»ów. Tak byªo w przypadku Twierdzenia Pitagorasa. Najwa»niej-

sze twierdzenie dotycz¡ce gur podobnych nazwano Twierdzeniem Talesa

4

.

1

L.Kronecker 1823-1891

2

st¡d sªowo trywialny

3

W ±redniowieczu nazywano te cztery przedmioty quadrivium; razem z trivium

stanowiªy kanon edukacji osoby wyksztaªconej.

4

Tales (625-545 p.n.e.)

1

Mówi ono, »e prosta równolegªa do jednego z boków trójk¡ta dzieli

pozostaªe boki na cz¦±ci proporcjonalne. Pitagorejczycy wierzyli, »e

istnieje odcinek, który mie±ci si¦ caªkowit¡ ilo±¢ razy w ka»dej z czterech

cz¦±ci.

Legenda mówi, »e pewien Pitagorejczyk zostaª utopiony za kar¦ za to, »e

publicznie chwaliª si¦, »e to on dodaª dwunasto±cian do regularnych wielo-

±cianów, które znaª Pitagoras.

Dewiz¡ Pitagorejczyków byªa sentencja: Wszystko jest liczb¡ (mieli na

my±li tylko liczby naturalne). Doktryn¡ pitagorejczyków byªo pozna¢ har-

moni¦ Wszech±wiata poprzez harmoni¦ liczb. Sprowadzaªo si¦ to do przypo-

rz¡dkowania ka»dej rzeczy pewnej liczby. Nie u»ywali liczby zero, bo nic

nie mo»e by¢ czym±. Pierwsz¡ prawdziw¡ liczb¡ byªa dwójka, gdy» jedynka

byªa jakby praliczb¡, sªu»¡c¡ do tworzenia prawdziwych liczb. Jedynka

oznaczaªa rozs¡dek który daje poj¦cie jedynej prawdy. Dwójka oznaczaªa

m¦»czyzn¦, trójka - kobiet¦. Czwórka byªa symbolem sprawiedliwo±ci, jako

liczba b¦d¡ca równocze±nie iloczynem i sum¡ liczb równych. Pi¡tka sym-

bolizowaªa maª»e«stwo, jako suma 2+3. Liczby parzyste, oprócz 2, uzna-

wane byªy za przyziemne, kobiece. Liczby nieparzyste, wi¦ksze od 3 uwa-

»ane byªy za m¦skie i boskie. Wyja±nieniem mo»e by¢ fakt, »e intelektu-

ali±ci staro»ytnej Grecji, zaabsorbowani problemami lozoi to byli ci sami

m¦»czy¹ni, którzy budowali fundamenty matematyki jako systemu my±lenia.

Matematyka byªa dla nich narz¦dziem dla zagadnie« lozocznych, dla zro-

zumienia ±wiata.

Fakt, »e stosunek dªugo±ci przek¡tnej kwadratu do jego boku nie jest

stosunkiem liczb (naturalnych) zagra»aª ich koncepcji, »e ±wiatem rz¡dz¡

liczby.

Pitagorejczycy zdominowali lokaln¡ wªadz¦ w Krotonie, a w wyniku po-

wstania ludowego w roku 501 p.n.e. wielu Pitagorejczyków zostaªo zabitych.

4 lata pó¹niej zabito równie» Pitagorasa. Bractwo Pitagorejczyków istniaªo

jeszcze okoªo dwóch wieków jako towarzystwo lozoczne i matematyczne,

trzymaj¡c w sekrecie swoje wyniki i przypisuj¡c je Mistrzowi.

2 Przedmiot teorii liczb

Oznaczenia: W dalszej cz¦±ci kursu zbiór liczb caªkowitych b¦dziemy ozna-

cza¢ przez Z, zbiór liczb naturalnych przez N, a zbiór liczb pierwszych przez
P

. Ponadto przyjmujemy, »e 0 /∈ N.

Teoria liczb jest cz¦±ci¡ wi¦kszej dziedziny matematyki, mianowicie aryt-

metyki teoretycznej. Arytmetyka teoretyczna zajmuje si¦ wszystkimi licz-

bami i zwi¡zkami mi¦dzy nimi, natomiast teoria liczb ogranicza si¦ do liczb

2

caªkowitych. Ze wzgl¦du na dodatkowe wªasno±ci, w Z wyró»niamy mi¦dzy

innymi liczby:

1. dodatnie/ujemne

2. parzyste/nieparzyste

3. kwadratowe k

n

= n

2

/ trójk¡tne t

n

= t

n−1

+ n

(ilo±ci kropek, z których

buduje si¦ kwadraty/trójk¡ty o dowolnej dªugo±ci boku)

4. pierwsze/zªo»one

5

; najwi¦ksza liczba pierwsza znaleziona przy pomocy

r¦cznego kalkulatora to liczba Ferriera:

2

148

+1

17

; najwi¦ksza znana obec-

nie liczba pierwsza, znaleziona w sierpniu 2008, to 2

43112609

− 1

, ma ona

12 978 189 cyfr

5. Mersenne'a (∀ p ∈ P M

p

= 2

p

− 1,

np. 3, 7); najwi¦ksza znana obecnie

liczba pierwsza to prawdopodobnie 46-ta liczba Mersenne'a

6. Fermata (∀ n ∈ N F

n

= 2

2

n

+ 1

, np. 5, 17)

7. Sophie Germain (p ∈ P takie, »e 2p + 1 ∈ P, np. 2, 29)

8. pierwsze lustrzane (np. 13 i 31, 17 71) i palindromiczne (np. 101, 131)

9. bli¹niacze (p, p + 2, np. 3 i 5, 5 i 7) /trojacze (p, p + 2, p + 4, tylko 3,5

i 7) /czworacze (p, p + 2, p + 4, p + 6 - nie istniej¡)

10. doskonaªe (równe sumie swoich dodatnich dzielników wªa±ciwych, np.

6, 28)

11. zaprzyja¹nione (pary liczb naturalnych takie, »e suma dodatnich dziel-

ników wªa±ciwych ka»dej z nich jest równa drugiej, np. 220 i 284).

12. wzgl¦dnie pierwsze (NW D(a, b) = 1, np. 3 i 4, 6 i 49)

13. mi¦dzypierwsze (liczby zªo»one b¦d¡ce ±redni¡ dwóch s¡siednich liczb

pierwszych, np. 4, 6, 9)

14. pseudopierwsze Fermata przy podstawie a ∈ N (liczby zªo»one n takie,

»e n|a

n

− a

, np 341 (przy podstawie 2)) / Carmichaela (liczby zªo»one

n

, które s¡ liczbami pseudopierwszymi Fermata przy ka»dej podstawie

a

wzgl¦dnie pierwszej z n, np 561, 1105).

5

Pitagorejczycy dzielili liczby (naturalne) na klasy: parzyste, nieparzyste, pierwsze,

zªo»one, kwadratowe, trójk¡tne (które stanowiªy ogniwo mi¦dzy arytmetyk¡ i geometri¡)

3

15. (ci¡g) Fibonacciego (f

1

= f

2

= 1, f

n

= f

n−1

+ f

n−2

, czyli 1,1,2,3,5,8,...)

16. trójki pitagorejskie (x, y, z ∈ Z x

2

+ y

2

= z

2

, np 3,4,5)

2.1 Wybrane wªasno±ci liczb naturalnych i caªkowitych

Zbiór liczb naturalnych ma porz¡dek < b¦d¡cy dobrym porz¡dkiem - to zna-

czy takim porz¡dkiem liniowym, »e ka»dy niepusty podzbiór ma (ze wzgl¦du

na ten porz¡dek) element najmniejszy. Wªasno±¢ ta nazywa si¦ Aksjoma-

tem Dobrego Porz¡dku. Poni»sze dwie Zasady s¡ równowa»ne z tym

Aksjomatem.

Twierdzenie 1 ( Zasada minimum ) W ka»dym niepustym podzbiorze zbioru
N

istnieje liczba najmniejsza.

Twierdzenie 2 ( Zasada maksimum ) W ka»dym niepustym ograniczonym

podzbiorze zbioru N istnieje liczba najwi¦ksza.

Uwaga Powy»sze twierdzenia mo»na rozszerzy¢ do zbioru N ∪ A, gdzie A

jest dowolnym sko«czonym podzbiorem Z - w szczególno±ci do N ∪ {0}.

Twierdzenie 3 ( Zasada indukcji matematycznej )

Niech ka»dej liczbie n ∈ N przyporz¡dkowane b¦dzie zdanie logiczne p(n).

Je±li speªnione s¡ warunki
(1) ∃ m ∈ N

takie, »e zdanie p(m) jest prawdziwe,

(2)

dla ka»dego n ≥ m z prawdziwo±ci p(n) wynika prawdziwo±¢ p(n + 1)

to ∀ n ≥ m zdanie p(n) jest prawdziwe.

Uwaga W zbiorze liczb caªkowitych zachodzi wªasno±¢: je±li mn = 0 to albo
m = 0

albo n = 0, innymi sªowy - nie ma dzielników zera.

Lemat 1 W zbiorze liczb caªkowitych zachodz¡ prawa skracania:

je±li a 6= 0 to z ab = ac wynika b = c oraz z ba = ca wynika b = c.

Dowód We¹my dowolne a, b, c ∈ Z, a 6= 0. Wtedy mamy:

ab = ac ⇒ ab − ac = 0 ⇒ a(b − c) = 0

a6=0

⇒ b − c = 0 ⇒ b = c.

Drugie prawo skracania wynika z przemienno±ci mno»enia w Z. 2

4

Reguªy wnioskowania (Sylogizmy) Arystotelesa

6

1. Wprowadzenie alternatywy

p

p ∨ q

p → (p ∨ q)

2.

Opuszczenie koniunkcji

p ∧ q

p

(p ∧ q) → q

3.

Wprowadzenie koniunkcji

p
q

p ∧ q

(p) ∧ (q) → (p ∧ q)

4.

Modus ponens

p ∧ q

p
q

((p → q) ∧ p) → q

5.

Modus tollens

p → q

∼ q
∼ p

((p → q) ∧ ∼ q) → ∼ p

6.

Sylogizm dysjunktywny

p ∨ q

∼ q

p

((p ∨ q) ∧ ∼ q) → p

7.

Sylogizm hipotetyczny

p → q
q → r
p → r

((p → q) ∧ (q → r)) → (p → r)

8.

Dylemat

p ∨ q

p → r
q → r

r

((p ∨ q) ∧ (p → r) ∧ (q → r)) → r

9.

Prawo zaprzeczenia

∼ p → c

p

(∼ p → c) → p

6

Arystoteles 384-322 p.n.e.

5