Дискретна математика Diskretna matematika 978-99955-46-26-7 [PDF]

Zitiervorschau

DISKRETNA MATEMATIKA Zoran Mitrovi´c Snjeˇzana Maksimovi´c Elektrotehniˇcki fakultet u Banjaluci

2 Recenzenti: Dr Dura Pauni´c, redovni profesor, PMF Novi Sad, Dr Duˇsko Joji´c, vanredni profesor, PMF Banja Luka. Korektor:

Izdavaˇ c: Elektrotehniˇcki fakultet, Banja Luka

ISBN ˇ Stampa: Tiraˇ z: 200 primeraka

Predgovor Ova knjiga je pisana prema programu kursa Diskretna matematika na Elektrotehniˇckom fakultetu u Banjaluci, osnova na kojoj je koncipirana su predavanja i vjeˇzbe koje su autori drˇzali studentima II godine. Knjiga je podijeljena na ˇsest poglavlja. U prvom poglavlju su objaˇsnjeni osnovni pojmovi elementarne teorije brojeva sa naglaskom na onim dijelovima koji su potrebni za rjeˇsavanje zadataka (djeljivost, prosti brojevi, Euklidov algoritam, modularna aritmetika i kineska teorema). Navedena je savremena primjena teorije brojeva u kriptografiji (RSA algoritam) kao i niz novijih rezultata iz savremene teorije brojeva. U drugom i tre´cem poglavlju analiziraju se kombinatorne osobine koeficijenata konaˇcnih i beskonaˇcnih suma. U ova dva poglavlja koristi se diferencijalni i integralni raˇcun i objaˇsnjava se njihova uloga u diskretnoj matematici. Ovde je data primjena funkcija generatrisa na rjeˇsavanje problema particija i deranˇzmana. Osim toga, opisano je kako se funkcije generatrise koriste za rjeˇsavanje rekurzivnih jednaˇcina (Fibonaˇcijevi i Katalananovi brojevi). ˇ Cetvrto poglavlje je posve´ceno teoriji grafova. U ovoj glavi je ve´cina pojmova pojaˇsnjena odgovaraju´cim primjerima. U ovom poglavlju se razmatraju povezani grafovi, stabla, planarni grafovi, Ojlerovi i Hamiltonovi grafovi. Navedene su i neke vaˇzne teoreme (teorema Kuratovskog) kao i neki nerijeˇseni problemi iz teorije grafova (problem trgovaˇckog putnika). Peto poglavlje poˇcinje sa definicijom prostora vjerovatno´ce. Zatim se uvode pojmovi uslovne vjerovatno´ce, nezavisnost dogadaja i diskretne sluˇcajne promjenljive. Pojam raspodjele vjerovatno´ca sluˇcajne promjenljive i neke vaˇznije raspodjele (Binomna, Puasonova, Gausova) su pokazane na odabranim primjerima. Poglavlje zavrˇsava sa uvodom u teoriju sluˇcajnih procesa. Posljednje poglavlje sadrˇzi rijeˇsene zadatke sa 32 ispita i kolokvijuma na Eletrotehniˇckom fakultetu u Banjoj Luci od 2010 do 2013. godine (ukupno oko 150 zadataka).

4 Primjeri su dati u tekstu kao ilustracija navedenih teorema i posebno su numerisani. Osim toga, na kraju svakog poglavlja, osim u poglavlju Ispitni zadaci, dati su zadaci za vjeˇzbanje koji su detaljno rijeˇseni ili je naveden rezultat (ukupno oko 140 primjera i 170 zadataka). Medu zadacima se nalaze kako lakˇsi koji ilustruju teoriju tako i teˇzi, koji dopunjuju osnovni tekst knjige. Oznake koje se koriste u tekstu kao i numeracije definicija, teorema, posljedica i napomena su standardne. * *

*

Zahvaljujemo recenzentima prof. dr Duru Pauni´cu i prof. dr Duˇsku Joji´cu na sugestijama i sveukupnoj pomo´ci tokom izrade ovoga udˇzbenika koju su nam nesebiˇcno pruˇzili. Takode, zahvaljujemo asistentu Dinu Kosi´cu, na pomo´ci oko obrade slika. Na kraju, bi´cemo zahvalni svim ˇcitaocima udˇzbenika koji nam ukaˇzu na greˇske i eventualne propuste.

Autori

Sadrˇ zaj 1 Teorija brojeva 1.1 Uvod . . . . . . . . . . . . . 1.2 Djeljivost . . . . . . . . . . 1.3 Euklidov algoritam . . . . . 1.4 Blenkinˇsipov algoritam . . . 1.5 Prosti brojevi. . . . . . . . 1.6 Modularne aritmetike . . . 1.7 Multiplikativne funkcije . . 1.8 Kineska teorema o ostacima 1.9 RSA algoritam . . . . . . . 1.10 Pitagorine trojke . . . . . . 1.11 Zadaci . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

7 7 9 13 16 18 26 33 42 45 47 49

2 Binomni koeficijenti i sume 2.1 Binomna i polinomna formula 2.2 Gausova metoda . . . . . . . 2.3 Metoda perturbacije . . . . . 2.4 Beskonaˇcne sume . . . . . . . 2.5 Primjena izvoda i integrala . 2.6 Princip ukljuˇcenja-iskljuˇcenja 2.7 Zadaci . . . . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

69 69 76 79 81 85 86 89

. . . . . .

97 97 102 107 109 110 111

3 Funkcije generatrise 3.1 Uvod . . . . . . . . . . . . . . . . . 3.2 Particije . . . . . . . . . . . . . . . 3.3 Hanojske kule . . . . . . . . . . . . ˇ 3.4 Stajnerov problem . . . . . . . . . 3.5 Fibonaˇcijevi brojevi . . . . . . . . 3.6 Problem dijagonalnih triangulacija

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

6

Sadrˇ zaj 3.7 3.8 3.9 3.10

Sistemi rekurzivnih jednaˇcina Problem deranˇzmana . . . . . Kompozicijski inverz . . . . . Zadaci . . . . . . . . . . . . .

4 Teorija grafova 4.1 Osnovni pojmovi . . . . . . . 4.2 Stepen ˇcvora . . . . . . . . . 4.3 Povezani grafovi . . . . . . . 4.4 Stabla . . . . . . . . . . . . . 4.5 Planarni grafovi . . . . . . . . 4.6 Ojlerovi i Hamiltonovi grafovi 4.7 Zadaci . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

112 113 114 115

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

135 . 135 . 139 . 143 . 146 . 149 . 153 . 158

5 Diskretna teorija vjerovatno´ ce 5.1 Pojam vjerovatno´ce . . . . . . . . 5.2 Uslovna vjerovatno´ca . . . . . . . 5.3 Diskretne sluˇcajne promjenljive . 5.4 Binomna i Puasonova raspodjela 5.5 Funkcija raspodjele . . . . . . . . 5.6 Sluˇcajni procesi . . . . . . . . . . 5.7 Zadaci . . . . . . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

173 173 180 186 186 190 194 196

6 Zadaci sa ispita

211

Literatura

315

Indeks pojmova

318

Glava 1

Teorija brojeva 1.1

Uvod

Klasiˇcna teorija brojeva se bavi prouˇcavanjem prirodnih, cijelih i racionalnih brojeva. Prvi problemi iz teorije brojeva zapisani su joˇs u starom Vavilonu i Egiptu 2000-3000 godina prije nove ere. Otkri´ce iracionalnih brojeva i osnovnih osobina djeljivosti prirodnih brojeva sadrˇzani su i u Euklidovim1 elementima. Neki najpoznatiji rijeˇseni i nerijeˇseni problemi iz teorije brojeva su: • Problem ”parova blizanaca”: Postoji beskonaˇcno mnogo parova prostih brojeva medusobno udaljenih za 2 (npr. 3 i 5, 5 i 7, 11 i 13, 17 i 19, 41 i 43, 101 i 103, . . .). Tvrdnja joˇs nije dokazana2 . Moˇze se pokazati da je problem ”parova blizanaca”ekvivalentan problemu da postoji beskonaˇcno mnogo prirodnih brojeva n, tako da broj n2 − 1 ima taˇcno 4 djelitelja. • Goldbahova3 hipoteza: Svaki paran broj 2n, n ≥ 2, se moˇze izraziti kao suma dva prosta prirodna broja (npr. 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3, . . .) i danas odgovor je nepoznat, iako su sve konkretne provjere dale pozitivne odgovore. Goldbahova hipoteza kaˇze da je odgovor potvrdan. Tvrdnja joˇs nije dokazana.4 1 2

Euklid (330 p.n.e. - 275 p.n.e.), grˇcki matematiˇcar. 2014. je dokazano da ima beskonaˇcno mnogo parova brojeva ˇcija je razlika najviˇse

246. 3

Christian Goldbach, (1690-1764), pruski matematiˇcar. Da bi pojaˇcao publicitet knjige ”Uncle Petros and Goldbach’s Conjecture”koju je napisao Apostolos Doxiadis, britanski izdavaˇc Tony Faber ponudio je $1,000,000 nagrade ako mu se dokaz poˇsalje do aprila 2002. god. Nagrada nije dodjeljena. 4

8

1.1. Uvod • ”Problem gustine”prostih brojeva: Za svaki dovoljno veliki realni broj x, npr. x ≥ 117 postoji bar jedan prost broj izmedu brojeva x i √ x + x. Tu hipotezu je krajem 18. vijeka postavio Leˇzandr5 , ali ona i do danas nije rijeˇsena. Ovo je samo jedan od problema vezan za tzv. ”problem gustine”prostih brojeva. • 10. Hilbertov6 problem postavljen 1900. godine: Postoji li algoritam za nalaˇzenje rjeˇsenja Diofantove7 jednaˇcine? (Negativan odgovor je dao Matijaˇsevi´c 8 1970. godine.) (a) Pelova9 jednaˇ cina: Najpoznatija Diofantova jednaˇcina je x2 − dy 2 = 1, gdje je d prirodan broj koji nije kvadrat. Sva pozitivna cijela rjeˇsenja (xn , yn ) ove jednaˇcine su data sa √ √ xn + dyn = (x0 + dy0 )n , gdje je (x0 , y0 ) najmanje rjeˇsenje Pelove jednaˇcine u pozitivnim cijelim brojevima. (b) Fermaova10 posljednja velika teorema: Jednaˇcina xn + y n = z n , nema rjeˇsenja u skupu prirodnih brojeva, gdje je n prirodan broj ve´ci od 2. (Tvrdnju je dokazao Endrju Vajls11 .) (c) Katalanova12 hipoteza iz 1843. godine: Jedina rjeˇsenja jednaˇcine xu − y v = 1, u prirodnim brojevima x, y, u, v su 32 − 23 = 1. (Tvrdnju je dokazao Mihailesku13 2002.) 5

Adrien-Marie Legendre, (1752-1833) francuski matematiˇcar. David Hilbert, (1862-1943) njemaˇcki matematiˇcar. 7 Diofant iz Aleksandrije (roden oko 250. ne), grˇcki matematiˇcar. 8 Yuri Vladimirovich Matiyasevich, (1947-), ruski matematiˇcar. 9 John Pell, (1611-1685), engleski matematiˇcar. 10 Pierre de Fermat, (1601-1665) francuski matematiˇcar. 11 Andrew John Wiles, (1953- ), britanski matematiˇcar. 12 Eugne Charles Catalan, (1814-1894), belgijski matematiˇcar. 13 Preda V. Mihˇ ailescu (1955-), rumunski matematiˇcar. 6

Glava 1. Teorija brojeva

9

• Mala Fermaova teorema: Ako je n prirodan broj i p prost broj koji ne dijeli n, onda je np−1 ≡ 1 (mod p). Time je zapravo dokazan jedan smjer tzv. kineske hipoteze od skoro 2000 godina prije da je prirodan broj n prost ako i samo ako je 2n −2 djeljiv sa n. Njen drugi smjer nije istinit, npr. 2341 − 2 je djeljiv sa 341, a 341 = 31 · 11. Mala Fermaova teorema je temelj mnogih rezultata iz teorije brojeva, a joˇs se koristi kao kompjuterska metoda provjere je li broj prost. • Problem Diofantovih aproksimacija: Za realan algebarski broj α nejednaˇcina α − p < 1 , q q 2+ gdje je  > 0, ima konaˇcno mnogo rjeˇsenja. Problem je rijeˇsio Klaus Rot14 1958. godine (dobitnik Fieldsove15 medalje).

1.2

Djeljivost

DEFINICIJA 1.1. Neka su a i b cijeli brojevi. Kaˇzemo da a dijeli b ako je a 6= 0 i postoji k ∈ Z tako da je b = ak. Piˇsemo a | b i ˇcitamo ”a dijeli b”. Broj a nazivamo djelitelj (djelilac) broja b, a broj b sadrˇzilac broja a. Primjetimo da je relacija ”a dijeli b”, refleksivna, antisimetriˇcna i tranzitivna. Sljede´ca teorema slijedi direktno iz definicije 1.1. TEOREMA 1.1. Ako su a, b, c ∈ Z, a | b i a | c onda a | (nb + mc) za bilo koja dva cijela broja m i n. Primjer 1. Neka su x i y cijeli brojevi. Pokazati da je 3x + 5y djeljiv sa 13 ako i samo ako je x + 6y djeljivo sa 13. Rjeˇsenje. Iz 13 | 3x + 5y slijedi 13 | 5(3x + 5y), pa 13 | 15x + 25y. Kako je 15x + 25y = 13x + 13y + 2(x + 6y), dobijamo 13 | x + 6y. S druge strane, 13 | x + 6y ⇒ 13 | 3(x + 6y), pa 13 | (3x + 5y) + 13y, a odavde dobijamo 13 | 3x + 5y. 14

Klaus Friedrich Roth (1925-), njemaˇcki matematiˇcar. Fieldsova medalja je nagrada koja se dodjeljuje dvojici, trojici ili ˇcetvorici matematiˇcara mladih od 40 godina na Medunarodnom kongresu matematiˇcara na svakih ˇcetiri godine. Nagrada nosi ime kanadskog matematiˇcara John Charles Fieldsa. 15

10

1.2. Djeljivost

Primjer 2. Dokazati da razlomak

21n + 4 ne moˇze da se skrati ni za jedan 14n + 3

prirodan broj n.16 Rjeˇsenje. Za svaki n vrijedi 3(14n + 3) − 2(21n + 4) = 1, pa, na osnovu teoreme 1.1, dobijamo da ako d | 14n + 3 i d | 21n + 4 da je d = 1. TEOREMA 1.2. Neka je a ∈ N i b ∈ Z tada postoje jedinstveni cijeli brojevi q i r takvi da je b = aq + r i 0 ≤ r < a. Dokaz. Pokaˇzimo prvo egzistenciju brojeva q i r. Konstruiˇsimo skup S = {b − as : b − as ≥ 0, s ∈ Z}. Skup S je neprazan podskup skupa N ∪ {0}, pa ima minimum. Neka je to r. Tada postoji q ∈ Z takav da je b − aq = r. Jasno je da je r ≥ 0. Pokaˇzimo da je r < a. U suprotnom bi imali r ≥ a, pa je b − a(q + 1) = r − a ≥ 0. Dakle, b − a(q + 1) ∈ S i b − a(q + 1) < r ˇsto je nemogu´ce. Pokaˇzimo jedinstvenost brojeva q i r. Pretpostavimo da je b = aq1 + r1 i b = aq2 +r2 , gdje je 0 ≤ r1 < a i 0 ≤ r2 < a. Tada je a|q2 −q1 | = |r2 −r1 | < a, pa kako su q1 i q2 cijeli brojevi to je |q2 − q1 | = 0. Znaˇci q1 = q2 i r1 = r2 . DEFINICIJA 1.2. • Ako su a, b, ∈ Z takvi da d | a i d | b onda d nazivamo zajedniˇ cki djelitelj od a i b. • Najve´ ci zajedniˇ cki djelitelj brojeva a i b oznaˇcavamo sa (a, b). • Najmanji prirodan broj ˇciji su a i b djelitelji nazivamo najmanji zajedniˇ cki sadrˇ zilac i oznaˇcavamo sa [a, b]. Napomena 1.1. Sliˇcno se definiˇse (a1 , a2 , . . . , an ) i [a1 , a2 , . . . , an ], gdje su a1 , a2 , . . . , an cijeli brojevi. Sljede´ca teorema slijedi direktno iz definicije 1.2. TEOREMA 1.3. Vrijedi: • (a, b) = (b, a) = (|a|, |b|), • [a, b] = [b, a] = [|a|, |b|], • ako d | a i d | b tada je d | (a, b), • ako a | m i b | m tada je [a, b] | m, 16

Medunarodna matematiˇcka olimpijada, Rumunija 1959.

Glava 1. Teorija brojeva

11

• (a, b) ≤ min{a, b} ≤ max{a, b} ≤ [a, b]. • ako je a=

n Y

u

pj j i b =

j=1

n Y

v

pj j ,

j=1

gdje su pj prosti brojevi, tada je (a, b) =

n Y

min{uj ,vj }

pj

i [a, b] =

j=1

n Y

max{uj ,vj }

pj

.

(1.1)

j=1

Primjer 3. Odrediti (460, 200) i [460, 200]. Rjeˇsenje. Kako je 460 = 22 ·5·23 i 200 = 23 ·52 imamo (460, 200) = 22 ·5 = 20 i [460, 200] = 23 · 52 · 23 = 4600. Primjer 4. Na´ci sve prirodne brojeve d, (d > 1) takve da d | (n2 + 1, (n + 1)2 + 1). Rjeˇsenje. Dobijamo da d | n2 + 1 i d | (n + 1)2 + 1, tj. d | (n2 + 2n + 2), pa d | [(n2 + 2n + 2) − (n2 + 1)]. Prema tome, d | (2n + 1), a odavde d | (4n2 + 4n + 1). Sada, imamo d | [4(n2 + 2n + 2) − (4n2 + 4n + 1)], ili d | 4n + 7. Kako d | (2n + 1), imamo d | [(4n + 7) − 2(2n + 1)], ili d | 5. Dakle, d = 1 ili d = 5. Stavljaju´ci n = 2, zakljuˇcujemo da je d = 5. Primjer 5.

17

Dokazati da je

(m, n, p)2 [m, n, p]2 = za sve m, n, p ∈ N. [m, n][m, p][n, p] (m, n)(m, p)(n, p) Rjeˇsenje. Pretpostavimo da je m = pa11 · pa22 · · · pakk , n = pb11 · pb22 · · · pbkk , p = pc11 · pc22 · · · pckk , gdje su pi prosti brojevi i ai , bi , ci , nenegativni cijeli brojevi, i ∈ {1, . . . , k}. Koriste´ci (1.1) dobijamo max{a1 ,b1 ,c1 }

· p2

max{a1 ,b1 }

· p2

[m, n, p] = p1

[m, n] = p1 17

max{a2 ,b2 ,c2 } max{a2 ,b2 }

max{ak ,bk ,ck }

· · · pk

max{ak ,bk }

· · · pk

Medunarodna matematiˇcka olimpijada, SAD, 1972.

,

,

12

1.2. Djeljivost max{a1 ,c1 }

· p2

max{b1 ,c1 }

· p2

[m, p] = p1 [n, p] = p1

max{a2 ,c2 }

· · · pk

max{ak ,ck }

max{b2 ,c2 }

· · · pk

max{bk ,ck }

,

,

opet iz (1.1) je min{a1 ,b1 ,c1 }

· p2

min{a1 ,b1 }

· p2

min{a1 ,c1 }

· p2

min{b1 ,c1 }

· p2

(m, n, p) = p1

(m, n) = p1 (m, p) = p1 (n, p) = p1

min{a2 ,b2 ,c2 }

min{ak ,bk ,ck }

· · · pk

min{a2 ,b2 }

· · · pk

min{ak ,bk }

min{a2 ,c2 }

· · · pk

min{b2 ,c2 }

· · · pk

min{ak ,ck }

min{bk ,ck }

,

, ,

.

Sada se zadatak svodi da se pokaˇze da je 2 max{a, b, c} − max{a, b} − max{a, c} − max{b, c} = 2 min{a, b, c} − min{a, b} − min{a, c} − min{b, c}. Moˇzemo pretpostaviti da vrijedi a ≤ b ≤ c. Tada je 2 max{a, b, c} − max{a, b} − max{a, c} − max{b, c} = 2c − b − c − c = −b. Sliˇcno, 2 min{a, b, c} − min{a, b} − min{a, c} − min{b, c} = 2a − a − a − b = −b. TEOREMA 1.4. (B´ezout18 ) Neka su a i b prirodni brojevi. Tada postoje cijeli brojevi x i y takvi da je (a, b) = ax + by. Dokaz. Skup S = {ax + by : ax + by > 0, x, y ∈ Z} je podskup skupa N, pa ima najmanji elemenat d0 . To znaˇci da postoje cijeli brojevi x0 i y0 takvi da je d0 = ax0 + by0 . Pokaˇzimo da d0 | ax + by za sve x, y ∈ Z. Ako (1.2) ne bi vrijedilo postojali bi cijeli brojevi x1 i y1 takvi da d0 - ax1 + by1 . 18 ´

Etienne B´ezout, (1730-1783), francuski matematiˇcar.

(1.2)

Glava 1. Teorija brojeva

13

Znaˇci postoje brojevi q i r, 1 ≤ r < d0 , takvi da je ax1 + by1 = qd0 + r, pa je a(x1 − qx0 ) + b(y1 − qy0 ) = r, ˇsto je nemogu´ce, jer je d0 minimum skupa S. Dakle, vrijedi (1.2), pa za x = 1 i y = 0 imamo d0 | a, a za x = 0 i y = 1 imamo d0 | b, to znaˇci d0 | (a, b). S druge strane, (a, b) | a i (a, b) | b, pa (a, b) | ax0 + by0 to jest (a, b) | d0 . Znaˇci d0 = (a, b). Posljedica 1.1. Ako su a i b relativno prosti brojevi to jest (a, b) = 1 tada postoje cijeli brojevi x i y takvi da je ax + by = 1. Primjer 6. Pokazati da jednaˇcina 12x + 15y = 3 ima cjelobrojna rjeˇsenja. Rjeˇsenje. Kako je (12, 15) = 3 na osnovu prethodne posljedice zakljuˇcujemo da jednaˇcina 4x+5y = 1 ima cjelobrojna rjeˇsenja, pa prema tome i jednaˇcina 12x + 15y = 3. Napomena 1.2. Iz dokaza teoreme 1.4. vidimo da je (a, b) = min{ax + by : ax + by > 0, x, y ∈ Z}.

1.3

Euklidov algoritam

DEFINICIJA 1.3. Diofantova jednaˇcina je polinomijalna jednaˇcina sa cjelobrojnim koeficijentima, f (x1 , x2 , . . . , xn ) = 0, ˇcija se rjeˇsenja traˇze u skupu Z (ili u N). U prethodnoj sekciji smo vidjeli da je za rjeˇsavanje linearne Diofantove jednaˇcine, ax + by = c, potrebno na´ci najve´ci zajedniˇcki djelilac brojeva a i b. Algoritam dat u sljede´coj teoremi daje postupak za odredivanje najve´ceg zajedniˇckog djelioca dva broja. TEOREMA 1.5. (Euklidov algoritam) Pretpostavimo da su a, b ∈ N i a < b. Dalje, neka su q1 , q2 , . . . , qn+1 ∈ Z, r1 , r2 , . . . , rn ∈ N i 0 < rn < rn−1 < · · · < r1 < a takvi da je b = aq1 + r1

14

1.3. Euklidov algoritam a = r1 q2 + r2 r1 = r2 q3 + r3 .. . rn−2 = rn−1 qn + rn rn−1 = rn qn+1 .

Tada je (a, b) = rn . Dokaz. Pokaˇzimo prvo da je (a, b) = (a, r1 ). Iz (a, b) | a, (a, b) | b i b = aq1 +r1 imamo (a, b) | r1 . Dakle, (a, b) | (a, r1 ). S druge strane, (a, r1 ) | a i (a, r1 ) | r1 , pa kako je b = aq1 + r1 imamo (a, r1 ) | b. Prema tome, (a, r1 ) | (a, b), pa je (a, b) = (a, r1 ). Na sliˇcan naˇcin imamo (a, r1 ) = (r1 , r2 ) = · · · = (rn−1 , rn ). Kako je (rn−1 , rn ) = rn , dobijamo (a, b) = rn .

Primjer 7. Imamo

1. Odrediti (589, 5111). 5111 =589 · 8 + 399 589 =399 · 1 + 190 399 =190 · 2 + 19 190 =19 · 10.

Dakle, (589, 5111) = 19. 2. Na´ci bar jedno rjeˇsenje jednaˇcine 589x + 5111y = 19. Iz 19 =399 − 190 · 2 =399 − (589 − 399 · 1) · 2 =589(−2) + 399 · 3 =589(−2) + (5111 − 589 · 8) · 3 =5111 · 3 + 589(−26),

Glava 1. Teorija brojeva

15

zakljuˇcujemo da je x = −26 i y = 3, pa je (−26, 3) jedno rjeˇsenje jednaˇcine 589x + 5111y = 19. Napomena 1.3. 1. Ako je (x0 , y0 ) rjeˇsenje jednaˇcine ax + by = c onda za svako rjeˇsenje (xt , yt ) te jednaˇcine vrijedi xt = x0 + bt, yt = y0 − at, gdje je t ∈ Z. Dakle, koriste´ci Euklidov algoritam moˇzemo rijeˇsiti svaku Diofantovu jednaˇcinu oblika ax + by = 1, gdje je (a, b) = 1. 2. Linearna Diofantova jednaˇcina a1 x1 +a2 x2 +· · ·+an xn = c ima rjeˇsenje ako i samo ako (a1 , a2 , . . . , an ) | c. 3. Za broj koraka j u Euklidovom algoritmu vrijedi j < 2 log2 a. Naime, za i−ti korak vrijedi ri ≤

ri−1 ri−1 ili < ri < ri−1 . 2 2

U drugom sluˇcaju je qi+1 = 1 i ri+1 = ri−1 − ri
1. (Zadatak Sophie Germain.19 ) Rjeˇsenje. Kako je n4 + 4 = n4 + 4n2 + 4 − 4n2 = (n2 + 2)2 − (2n)2 = (n2 + 2 + 2n)(n2 + 2 − 2n), dobijamo da je dati broj sloˇzen. TEOREMA 1.7. Neka su a1 , a2 , . . . , an ∈ Z i p prost broj. Ako p | a1 · a2 · · · an tada p | aj za neko j ∈ {1, . . . , n}. TEOREMA 1.8. (Osnovna teorema aritmetike) Faktorizacija svakog prirodnog broja n > 1 na proste faktore je jedinstvena. Dokaz. Prvo ´cemo indukcijom pokazati da svaki prirodan broj n ≥ 2 ima reprezentaciju koja se sastoji od proizvoda prostih brojeva. Broj 2 ima reprezentaciju koja se sastoji od prostih brojeva. Prepostavimo sada da je n > 2 i da svaki prirodan broj m za koji vrijedi 2 ≤ m < n ima reprezentaciju koja se sastoji od proizvoda prostih brojeva. Ako je n prost broj tada je dokaz gotov, u suprotnom postoje prirodni brojevi n1 i n2 takvi da je 2 ≤ n1 < n i 2 ≤ n2 < n i n = n1 · n2 . Zbog indukcijske pretpostavke n1 i n2 imaju reprezentacije preko proizvoda prostih brojeva, pa prema tome takvu reprezentaciju ima i broj n. Dokaˇzimo sada jedinstvenost. Pretpostavimo da je 0

0

0

n = p1 · p2 · · · · pr = p1 · p2 · · · ps , 0

0

0

gdje su p1 ≤ p2 ≤ · · · ≤ pr , p1 ≤ p2 ≤ · · · ≤ ps prosti brojevi. Imamo p1 | 0 0 0 0 0 p1 ·p2 · · · ps , pa p1 | pi za neki i ∈ {1, . . . , s}. S druge strane p1 | p1 ·p2 ·· · · pr , 0 pa p1 | pj za neki j ∈ {1, . . . , r}. Dakle, imamo 0

0

p1 = pi ≥ p1 = pj ≥ p1 , 0

pa je p1 = p1 . Sada je

0

0

p2 · · · pr = p2 · · · ps , 0

pa se na sliˇcan naˇcin pokaˇze da je r = s i pi = pi , i = 1, . . . , r. 19

Sophie Germain, (1776-1831), francuska matematiˇcarka.

20

1.5. Prosti brojevi.

Posljedica 1.2. Za svaki prirodan broj n postoje prosti brojevi p1 , . . . , pk i prirodni brojevi α1 , . . . , αk takvi da je n = pα1 1 · · · pαk k .

(1.5)

DEFINICIJA 1.5. Reprezentacija (1.5) se naziva kanonska dekompozicija broja n. TEOREMA 1.9. Ako je n sloˇzen broj, onda n ima prost faktor manji ili √ jednak od n. Dokaz. Ako je n sloˇzen, iz definicije sloˇzenog broja, slijedi da ima faktor a za koji je 1 < a < n. Zato, imamo da je n = a · b, gdje je b pozitivan broj √ √ √ √ ve´ci od 1. Dokaˇzimo da je a ≤ n ili b ≤ n. Ako je a > n i b > n, √ √ √ onda je a · b > n · n = n, a ovo je kontradikcija. Prema tome, a ≤ n ili √ b ≤ n. Kako su a i b djelioci broja n, imamo da n ima djelilac ne ve´ci od √ n. Taj djelilac je prost ili, prema osnovnoj teoremi aritmetike, ima prost faktor ne ve´ci od njega samog. U oba sluˇcaja, n ima prost faktor manji ili √ jednak od n. TEOREMA 1.10. (Euklid) Skup prostih brojeva je beskonaˇcan. Dokaz. Pretpostavimo suprotno. Neka su p1 < p2 < · · · < pk svi prosti brojevi. Tada je na osnovu osnovne teoreme aritmetike broj n = p1 · p2 · · · pk + 1 djeljiv sa pj za neko j ∈ {1, . . . , k}. Dakle, pj | n − p1 · p2 · · · pk , to jest pj | 1 ˇsto je nemogu´ce. Primjer 12. Dokazati da prostih brojeva oblika 4k + 3 ima beskonaˇcno mnogo. Rjeˇsenje. Koristimo ideju Euklidovog dokaza o beskonaˇcnosti prostih brojeva. Pri dijeljenju sa 4 neparni prosti broj moˇze dati ostatak 1 ili 3. Proizvod brojeva oblika 4k + 1 i sam je tog oblika. Zaista, (4s + 1)(4t + 1) = 4(4st + s + t) + 1. Neka su sada p1 , p2 , . . . , pn svi prosti brojevi oblika 4k + 3. Posmatrajmo broj 4p1 p2 · · · pn − 1. Ako bi svi njegovi prosti faktori bili oblika 4k + 1, onda bi i on sam imao taj oblik, a to nije taˇcno. Prema tome, on ima barem jedan prosti faktor p oblika 4k + 3. Oˇcigledno je p 6= pi , za i = 1, 2, . . . , n, pa smo dobili kontradikciju. Prethodni primjer je specijalan sluˇcaj teoreme o prostim brojevima u aritmetiˇckim progresijama.

Glava 1. Teorija brojeva

21

TEOREMA 1.11. (Dirichlet20 ) Svaki aritmetiˇcki niz {a + nb} kod koga su a i b uzajamno prosti prirodni brojevi sadrˇzi beskonaˇcno mnogo prostih brojeva. Primjer 13. Dokazati da ne postoji polinom f (x) s cjelobrojnim koeficijentima, stepena deg(f ) ≥ 1, takav da je f (n) prost za sve n ∈ N. Rjeˇsenje. Neka je f (1) = p. Tada je p prost broj. Kako je f (1 + kp) − f (1) djeljivo sa (1 + kp) − 1 = kp (jer x − y dijeli xm − y m ), slijedi da p | f (1 + kp), za svaki k ∈ N. Medutim, f (1 + kp) je prost, pa mora biti f (1 + kp) = p, za svaki k ∈ N. Dakle, polinom f (x) − p ima beskonaˇcno mnogo nula, pa on mora biti nula polinom, pa je f (x) = p, ˇsto je u suprotnosti s pretpostavkom da je stepen polinoma deg(f ) ≥ 1. Prosti brojevi su nepravilno rasporedeni u skupu prirodnih brojeva. Jedan od osnovnih rezultata u teoriji brojeva je asimptotski zakon raspodjele prostih brojeva koji su 1896. godine dokazali Hadamard21 i de la Vall´ee Poussin.22 TEOREMA 1.12. (Hadamard i de la Vall´ee Poussin) Neka π(n) oznaˇcava broj prostih brojeva koji nisu ve´ci od prirodnog broja n. Tada je π(n) ∼

n kad n → +∞. ln n

Dokazi teorema 1.11 i 1.12 su komplikovani i izlaze van okvira ove knjige. Lema 1.1. Neka je x realan broj ve´ci od 2. Tada je X1 p≤x

p

> ln ln x − 1.

Suma na lijevoj strani je po svim prostim brojevima p koji ispunjavaju uslov p ≤ x. Dokaz. Neka p1 , p2 , . . . , pn predstavljaju sve proste brojeve ≤ x, i oznaˇcimo sa N = {pk11 pk22 · · · pknn | k1 ≥ 0, k2 ≥ 0, . . . , kn ≥ 0}, tj. N sadrˇzi 1 i sve pozitivne brojeve zapisane koriste´ci faktorizacije prostih brojeva p1 , p2 , . . . , pn . Prema tome, skup N sadrˇzi sve brojeve 1, 2, 3, . . . , bxc, 20

J. P. G. Lejeune Dirichlet (1805-1859), njemaˇcki matematiˇcar. J. Hadamard (1865-1963), francuski matematiˇcar. 22 Ch. J. de la Vall´ee Poussin (1866-1962), belgijski matematiˇcar. 21

22

1.5. Prosti brojevi.

pa je bxc+1 Z bxc X 1 X 1 dt ≥ ≥ = ln(bxc + 1) > ln x. n n t

n∈N

n=1

1

Primjetimo da je    X Y 1 1 −1 Y 1 1 1 1 + + 2 + 3 + ··· = 1− = . p p p p n p≤x

p≤x

n∈N

Iz prethodnih nejednakosti dobijamo  Y 1 −1 > ln x, 1− p

p≤x

a odavde logaritmuju´ci obe strane slijedi X p≤x



1 ln 1 − p

−1 > ln ln x.

(1.6)

Koriste´ci Maklorenov razvoj funkcije ln(1 − x), imamo − ln(1−x) = x+

x2 x2 x2 x3 + +· · · ≤ x+ (1+x+x2 +· · · ) = x+ 2 3 2 2

za 0 ≤ x < 1. Kako je



1 1−x

 ,

1 1 ≤ 2, za x ≤ , dobijamo nejednakost 1−x 2

1 ln(1 − x)−1 = − ln(1 − x) ≤ x + x2 , za x ≤ . 2 1 Specijalno, ako je p prost, tada je p ≤ , pa vrijedi 2   1 −1 1 1 ln 1 − ≤ + 2. p p p Sumiraju´ci ove nejednakosti za sve proste brojeve p ≤ x i koriste´ci nejednakost (1.6) dobijamo X1 X 1 + > ln ln x. (1.7) p p2 p≤x

p≤x

Glava 1. Teorija brojeva

23

Kako vrijedi,  +∞ +∞ +∞  X 1 X X X 1 1 1 1 = 1, ≤ ≤ = − p2 n2 n(n − 1) n−1 n n=2

p≤x

n=2

n=2

iz nejednakosti (1.7) dobijamo X1 p≤x

p

> ln ln x − 1.

Napomena 1.6. Kako je lim ln ln x = +∞ iz leme 1.1 dobijamo da je broj x→+∞

prostih brojeva beskonaˇcan, ˇsto predstavlja joˇs jedan dokaz teoreme 1.10. Lema 1.2. Neka je x pozitivan realan broj i π(x) broj prostih brojeva koji nisu ve´ci od x, tada vrijedi X1 p≤x

π(x) = + p x

Z

x

2

π(u) du. u2

Dokaz. Neka p1 < p2 < . . . < pn predstavljaju sve proste brojeve ne ve´c od x. Tada vrijedi Z 2

x

n−1 Z pk+1

Z x π(u) π(u) du + du 2 u u2 p p n k k=1 Z x n−1 X Z pk+1 k n du + du = 2 2 u pn u k=1 pk    n−1 X 1 1 1 1 = k − +n − pk pk+1 pn x

X π(u) du = 2 u

= =

k=1 n−1 X k=1 n X k=1

n

Xk−1 k n n − + − pk pk pn x k=2

1 π(x) − . pk x

24

1.5. Prosti brojevi.

TEOREMA 1.13. Za svaki  > 0 i svaki realan broj ω postoji broj x > ω takav da je x π(x) > (1 − ) . ln x Dokaz. Pretpostavimo suprotno. Tada postoje realni brojevi  i ω takvi da je x , π(x) ≤ (1 − ) ln x za sve x > ω. U tom sluˇcaju imamo Z x Z ω Z x Z x π(u) π(u) π(u) du du = du + du ≤ C + (1 − ) 2 2 2 u u u 2 2 ω ω u ln u =C + (1 − )(ln ln x − ln ln ω) = D + (1 − ) ln ln x, gdje su C i D konstante nezavisne od ω. Kako je π(x) < x, iz leme 1.2 dobijamo X1 ≤ (1 − ) ln ln x + Const. p p≤x

Ovo je kontradikcija sa lemom 1.1. DEFINICIJA 1.6. Neka je p prost i n prirodan broj. Broj ep (n!) se definiˇse sa ep (n!) = max{k ∈ N : pk | n!}. TEOREMA 1.14. (Leˇzandr) Za broj ep (n!) vaˇzi       n n n ep (n!) = + 2 + 3 + ··· . p p p

Dokaz. Medu brojevima 1, 2, . . . , n ima

j k n p

brojeva djeljivih sa p,

j k n p2

djeljivih sa p2 itd. Primjer 14. Pokazati da za svaki prirodan broj n vaˇzi 2n | (n + 1)(n + 2) · · · (n + n). Rjeˇsenje. Slijedi iz prethodne teoreme i ˇcinjenice     j n k j n k   2n  2n 2n e2 ((2n)!) − e2 (n!) = + 2 +· · ·− + 2 + ··· = = n. 2 2 2 2 2

Glava 1. Teorija brojeva Primjer 15. zati da

23 Dat

25

je prirodan broj n i prost broj p tako da pp | n!. Dokapp+1 | n!.

Rjeˇsenje. Ako je n < p2 , tada je, prema Leˇzandrovoj teoremi,       n n n + 2 + 3 + · · · < p. p p p Odavde dobijamo da broj pp ne dijeli broj n!, a ovo nije mogu´ce zbog pretpostavke zadatka. Znaˇci, ako pp | n!, onda je n ≥ p2 . Prema tome,           n n n n n + 2 + 3 + ··· ≥ + 2 = p + 1. p p p p p Zato, pp+1 | n!. Sljede´ca teorema je poznata kao mala24 Fermaova teorema. TEOREMA 1.15. Neka je a prirodan broj i p prost tada je p | ap − a. Dokaz. Dokaza´cemo teoremu koriste´ci indukciju po a. Za a = 1 tvrdnja je trivijalna. Neka je a > 1 i stavimo a = b + 1. Koriste´ci binomnu formulu dobijamo,     p p−1 p p p p a − a =(b + 1) − (b + 1) = b + b + ··· + b+1−b−1 1 p−1     p p−1 p p =(b − b) + b + ··· + b. 1 p−1 p Po indukcijskoj   hipotezi b − b je djeljivo sa p. S druge strane, kako je p p prost to p | , k = 1, . . . , p − 1, pa je dokaz gotov. k 23

Amer. Math. Monthly, Problem No. 11158, 2005. Fermaova teorema je nazvana ”mala”kao kontrast Fermaovoj posljednjoj teoremi koja tvrdi da jednaˇcina xn + y n = z n nema rjeˇsenja u skupu prirodnih brojeva za n > 2. Ovaj problem je bio nerijeˇsen preko 350 godina, sve dok ga nije rijeˇsio Andrew Wiles 1995. god. Mala Fermaova teorema je mnogo jednostavnija, ali ima znaˇcajne primjene u kriptografiji i tajnom prenosu podataka na Internetu. 24

26

1.6. Modularne aritmetike

Napomena 1.7. Na sliˇcan naˇcin se moˇze dokazati i da p | (a1 + a2 + · · · + an )p − ap1 − ap2 − · · · − apn , gdje je p prost, a a1 , a2 , . . . , an cijeli brojevi. Primjer 16. Pokazati da postoji prirodan broj k takav da je 11256 = 1 + 257 · k. Rjeˇsenje. Broj 257 je prost, pa na osnovu male Fermaove teoreme 257 | 11257 − 11, a odavde dobijamo da 257 | 11256 − 1, tj. postoji k takav da je 11256 = 1 + 257 · k. Primjer 17. Ako je p prost broj ve´ci od 3, dokazati da 6p | abp − ap b. Rjeˇsenje. Vrijedi abp − ap b = ab(bp−1 − ap−1 ), odavde zakljuˇcujemo da je dati izraz djeljiv sa 2 (ako je bar jedan od brojeva a i b paran onda je ab paran, u suprotnom su oba neparna, pa je (bp−1 −ap−1 ) paran). Djeljivost sa 3 se pokaˇze tako ˇsto se razmotre sluˇcajevi: a = 3k + r, b = 3l + s, gdje su r, s ∈ {0, 1, 2}. Djeljivost sa p slijedi iz male Fermaove teoreme jer p | bp−1 − 1 i p | − 1, pa dobijamo

ap−1

p | (bp−1 − 1) − (ap−1 − 1) = bp−1 − ap−1 .

1.6

Modularne aritmetike

U ovoj sekciji, koriste´ci osobine prostih brojeva nastavljamo da izuˇcavamo relaciju ”a dijeli b”. Njemaˇcki matematiˇcar Gaus25 je razvio koncept kongruencija na kraju osamnaestog vijeka. Pojam kongruencija igra znaˇcajnu ulogu u teoriji brojeva. 25

Johann Carl Friedrich Gauß, (1777-1855), njemaˇcki matematiˇcar.

Glava 1. Teorija brojeva

27

DEFINICIJA 1.7. Ako je n | a − b onda kaˇzemo da je a kongruentno b po modulu n i to piˇsemo a ≡ b (mod n). Relacija ”biti kongruentan po modulu n”je relacija ekvivalencije na skupu Z. Svi cijeli brojevi koji su kongruentni po datom modulu obrazuju jednu klasu brojeva. Tako na primjer po modulu 3 imamo tri klase brojeva: • klasu brojeva oblika 3k koji su djeljivi sa 3, odnosno kongruentni su nuli po modulu 3, • klasu brojeva oblika 3k + 1 koji prilikom dijeljenja sa 3 daju ostatak 1, odnosno kongruentni su jedinici po modulu 3, • klasu brojeva oblika 3k + 2 koji prilikom dijeljenja sa 3 daju ostatak 2, odnosno kongruentni su broju 2 po modulu 3. Primjer 18. Odrediti prirodan broj p ako su p i 8p2 + 1 prosti brojevi. Rjeˇsenje. Prema prethodnom svaki cijeli broj se moˇze zapisati u jednom od sljede´ca tri oblika: n = 3k, n = 3k + 1 n = 3k − 1, gdje je k cijeli broj. Ako je p 6= 3 onda je p oblika 3k ± 1, jer je p prost. U oba sluˇcaja je 8p2 + 1 = 3(24k 2 ± 16k + 3) djeljivo sa 3. Dakle, ostaje jedino mogu´cnost da je p = 3 i u tom sluˇcaju imamo 8p2 + 1 = 73, ˇsto je prost broj. TEOREMA 1.16. • Ako je a ≡ b (mod n) i c ≡ d (mod n) onda je a ± c ≡ b ± d (mod n) i ac ≡ bd (mod n). • Ako je a ≡ b (mod n), d ∈ N i d | n onda je a ≡ b (mod d). • Ako je a ≡ b (mod n) onda je ac ≡ bc (mod n) za svaki cijeli broj c. • Ako je a ≡ b (mod n) onda je ak ≡ bk (mod n) za svaki prirodan broj k. • Ako je f polinom sa cjelobrojnim koeficijentima i a ≡ b (mod n), tada je f (a) ≡ f (b) (mod n).

28

1.6. Modularne aritmetike • Ako je f polinom sa cjelobrojnim koeficijentima stepena n i p prost, onda kongruencija f (x) ≡ 0 (mod p) ima najviˇse n rjeˇsenja po modulu p. • Ako je ac ≡ bc (mod n) i (c, n) = 1 onda je a ≡ b (mod n).

Dokaz. Dokaˇzimo na primjer posljednju osobinu. (Dokaz ostalih osobina je sliˇcan.) Neka je ac ≡ bc (mod n). Tada imamo n | c(a − b), pa kako je (c, n) = 1 to je n | a − b. Znaˇci a ≡ b (mod n). Napomena 1.8. Moˇze se pokazati da je ac ≡ bc (mod n) ako i samo ako je n a ≡ b (mod (c,n) ). Primjer 19. Odrediti posljednju cifru u dekadnom zapisu broja 3400 . Rjeˇsenje. Vrijedi 34 ≡ 1 (mod 10), pa je 3400 ≡ 1100

(mod 10),

to jest 3400 ≡ 1

(mod 10).

Dakle, posljednja cifra broja 3400 je 1. Napomena 1.9. Neka je f (x1 , . . . , xn ) polinom sa cjelobrojnim koeficijentima. Ako Diofantova jednaˇcina f (x1 , . . . , xn ) = 0 ima rjeˇsenje (a1 , . . . , an ) onda kongruencijska jednaˇcina f (x1 , . . . , xn ) ≡ 0

(mod m),

ima rjeˇsenje (a1 , . . . , an ) za svaki m ∈ N. Prema tome, ako postoji m ∈ N, takav da kongruencija f (x1 , . . . , xn ) ≡ 0 (mod m) nema rjeˇsenja, onda i Diofantova jednaˇcina f (x1 , . . . , xn ) = 0 nema rjeˇsenja. Primjer 20. Pokazati da Diofantova jednaˇcina x2 = y 5 + 7 nema rjeˇsenje. Rjeˇsenje. Uoˇcimo kongruencijsku jednaˇcinu x2 ≡ y 5 + 7 (mod 11). Vrijedi x2 ≡ 0, 1, 3, 4, 5 ili 9 y 5 ≡ 0, 1 ili 10

(mod 11) za sve x ∈ Z,

(mod 11) za sve y ∈ Z.

Prema tome, y 5 + 7 ≡ 6, 7 ili 8

(mod 11),

Glava 1. Teorija brojeva

29

pa je x2 6= y 5 + 7

(mod 11) za sve x, y ∈ Z.

Ovo znaˇci da kongruencijska jednaˇcina x2 ≡ y 5 + 7 (mod 11) nema rjeˇsenje, odakle zakljuˇcujemo da i Diofantova jednaˇcina x2 = y 5 + 7 nema rjeˇsenje. Napomena 1.10. Malu Fermaovu teoremu moˇzemo zapisati i na sljede´ci naˇcin: Ako je a prirodan broj i p prost onda je ap ≡ a

(mod p).

Primjer 21. Neka je p prost broj ve´ci od 2 i p ne dijeli a. Pokazati da je jedan i samo jedan od brojeva A = a1+2+···+(p−1) − 1 i B = a1+2+···+(p−1) + 1, djeljiv sa p. Rjeˇsenje. Na osnovu male Fermaove teoreme je ap−1 ≡ 1 (mod p), pa je  (p−1)p   (p−1)p  AB = a 2 − 1 a 2 + 1 = a(p−1)p − 1 ≡ 0

(mod p).

Dakle, p | AB. Kako je B − A = 2 i p prost broj ve´ci od 2, to samo jedan od brojeva moˇze biti djeljiv sa p. Primjer 22. Ako je p prost i n prirodan broj takav da je p | (4n2 + 1), tada p ≡ 1 (mod 4). Rjeˇsenje. Jasno da je p 6= 2. Neparan broj pri dijeljenju sa 4 daje ostatak 1 ili 3. Prema tome, treba dokazati da p nije oblika 4k + 3. Pretpostavimo da postoji k takav da je p = 4k + 3. Na osnovu malog Fermaovog teorema, jer p nije djeljivo sa n, je (2n)p−1 ≡ 1 (mod p). Iz pretpostavke zadatka je (2n)2 ≡ −1

(mod p),

pa je (2n)p−1 ≡ (2n)4k+2 ≡ [(2n)2 ]2k+1 ≡ (−1)2k+1 ≡ −1 ˇsto je kontradikcija. Prema tome, p ≡ 1 (mod 4).

(mod p),

30

1.6. Modularne aritmetike

Primjer 23. Dokazati da n nije djelilac broja 2n − 1, ako je n prirodan broj ve´ci od 1. Rjeˇsenje. Neka je p najmanji prost djelilac od n. Tada je (n, p − 1) = 1, pa zbog posljedice 1.1, postoje cijeli brojevi x i y takvi da je nx + (p − 1)y = 1. Ako p | (2n − 1), onda je zbog male Fermaove teoreme 2 ≡ 2nx+(p−1)y ≡ (2n )x (2p−1 )y ≡ 1

(mod p),

a ovo je kontradikcija. Prema tome, p - (2n − 1), odakle slijedi n - (2n − 1). Neka je dat prirodan broj m > 1. Posmatrajmo m klasa cijelih brojeva kongruentnih redom sa brojevima 0, 1, 2, . . . , m − 1. Jasno je da jedan broj ne moˇze biti u dvije razliˇcite klase i da svaki cijeli broj mora biti u jednoj od klasa. Izaberimo m brojeva tako da svaki bude iz po jedne klase. Tako izabrani brojevi nazivaju se potpuni sistem ostataka po modulu m. Svedeni sistem ostataka po modulu m se dobija ako se iz potpunog sistema ostataka izbace brojevi koji nisu uzajamno prosti sa m. U svedenom sistemu ostataka po datom modulu uvijek je isti broj elemenata bez obzira od kog potpunog sistema podemo. TEOREMA 1.17. Neka je (a, m) = 1 i {α1 , α2 , . . . , αk } proizvoljan potpuni (svedeni) sistem ostataka po modulu m. Tada je {aα1 , aα2 , . . . , aαk } potpuni (svedeni) sistem ostataka po modulu m. Dokaz. Brojeva aαi ima koliko i brojeva αi , pa treba dokazati da brojevi aαi i aαj pripadaju razliˇcitim klasama po modulu m ako je i 6= j. Ako bi bilo aαi ≡ aαj (mod m), kako je (a, m) = 1, imali bi da je α1 ≡ αj (mod m), ˇsto je nemogu´ce. TEOREMA 1.18. Ako je p prost broj, onda za svaki k ∈ {2, 3, . . . , p − 2}, postoji taˇcno jedan broj l ∈ {2, 3, . . . , p − 2}, takav da je kl ≡ 1

(mod p)

i vrijedi l 6= k. Dokaz. Na osnovu teoreme 1.17 brojevi k, 2k, 3k, . . . , (p − 1)k, pk

Glava 1. Teorija brojeva

31

obrazuju potpuni sistem ostataka po modulu p, pa uzeti u nekom redoslijedu daju ostatke 0, 1, 2, . . . , p − 1 po modulu p. To znaˇci da postoji taˇcno jedan l ∈ {2, 3, . . . , p − 1} takav da je kl ≡ 1

(mod p).

Broj l ne moˇze biti jednak k, jer bi u tom sluˇcaju imali k2 ≡ 1

(mod p),

a ovo je ekvivalentno sa (k − 1)(k + 1) ≡ 0

(mod p).

Ovo znaˇci da je k≡1

(mod p) ili k ≡ −1

(mod p),

ˇsto je nemogu´ce, jer je k ∈ {2, 3, . . . , p − 2}. TEOREMA 1.19. (Vilson26 ) Ako je p prost broj, tada vrijedi (p − 1)! ≡ −1

(mod p).

Dokaz. Za p = 2 tvrdenje oˇcigledno vrijedi. Ako je p prost broj ve´ci od 2, u proizvodu (p − 1)! = 1 · 2 · 3 · . . . · (p − 1) ima paran broj faktora. Na osnovu teoreme 1.18 vrijedi 2 · 3 · . . . · (p − 2) ≡ 1

(mod p),

kako je 1 · (p − 1) ≡ −1

(mod p),

dobijamo tvrdenje teoreme. Primjer 24. Odrediti ostatak pri dijeljenju broja 93! sa 97. Rjeˇsenje. Kako je 97 prost broj na osnovu Vilsonove teoreme imamo 96! ≡ −1

(mod 97).

Pretpostavimo da je 93! ≡ x 26

(mod 97).

John Wilson (1741-1793), engleski matematiˇcar.

32

1.6. Modularne aritmetike

Sada dobijamo 96 · 95 · 94 · x ≡ (−1)(−2)(−3)x

(mod 97).

Dakle, −1 ≡ −6x

(mod 97),

pa vrijedi 6x ≡ 1

(mod 97),

kako je (16, 97) = 1 mnoˇzenjem posljednje jednakosti sa 16 dobijamo 96x ≡ 16

(mod 97),

−x ≡ 16

(mod 97),

x ≡ −16

(mod 97),

to jest

odavde je

pa je x ≡ 81

(mod 97).

Primjer 25. Ako je p prost broj ve´ci od 2, dokazati 12 · 32 · 52 · . . . · (p − 2)2 ≡ (−1)

p+1 2

(mod p).

Rjeˇsenje. Na osnovu Vilsonove teoreme je 1 · 2 · 3 · . . . · (p − 1) ≡ −1

(mod p).

Za svako i = 0, ±1, ±2, . . . vrijedi i ≡ −(p − i)

(mod p).

p−1 Zamijenimo parnih brojeva na lijevoj strani prve kongruencije bro2 jevima njima kongruentnim koji se dobijaju iz druge kongruencije za i = 2, 4, . . . , p − 1. Dobijamo 12 · 32 · 52 · . . . · (p − 2)2 (−1)

p−1 2

≡ −1

(mod p).

Glava 1. Teorija brojeva

33

Primjer 26. Neka {a1 , a2 , . . . , a101 } i {b1 , b2 , . . . , b101 } predstavljaju potpune sisteme ostataka po modulu 101. Moˇze li {a1 b1 , a2 b2 , . . . , a101 b101 } predstavljati potpun sistem ostataka po modulu 101? Rjeˇsenje. Pretpostavimo da je {a1 b1 , a2 b2 , . . . , a101 b101 } potpun sistem ostataka po modulu 101. Moˇzemo pretpostaviti da je a101 ≡ 0 (mod 101). Tada je b101 ≡ 0 (mod 101), jer je jedan od brojeva bj kongruentan sa 0 po modulu 101, pa je aj bj ≡ a101 b101 ≡ 0 (mod 101). Iz Vilsonove teoreme dobijamo a1 a2 · · · a100 ≡ b1 b2 · · · b100 ≡ 100! ≡ −1 (mod 101), dakle, a1 b1 a2 b2 · · · a100 b100 ≡ 1 (mod 101). Ali a101 b101 ≡ 0 (mod 101), pa imamo a1 b1 a2 b2 · · · a100 b100 ≡ 100! ≡ −1 (mod 101). Prema tome, odgovor je ne.

1.7

Multiplikativne funkcije

DEFINICIJA 1.8. Funkcija f : N → N je multiplikativna ako je f (mn) = f (m)f (n), za sve prirodne brojeve m i n za koje je (m, n) = 1. TEOREMA 1.20. Neka je n = pα1 1 · · · pαk k kanonska dekompozicija broja n. Broj pozitivnih djelilaca broja n je (1 + α1 ) · · · (1 + αk ). Dokaz. Svi pozitivni djelioci broja n (ukljuˇcuju´ci 1 i sam n) su oblika pβ1 1 · · · pβk k , 0 ≤ β1 ≤ α1 , . . . , 0 ≤ βk ≤ αk , prema tome, ukupan broj pozitivnih djelilaca broja n je (koristimo pravilo proizvoda iz kombinatorike) (1 + α1 ) · · · (1 + αk ).

DEFINICIJA 1.9. Ukupan broj pozitivnih djelilaca broja n oznaˇcava se sa τ (n).27 TEOREMA 1.21. Funkcija τ je multiplikativna. Dokaz. Slijedi direktno iz τ (pα1 1 · · · pαk k ) = (1 + α1 ) · · · (1 + αk ). 27 ˇ

Cesto se koristi i oznaka d(n)

34

1.7. Multiplikativne funkcije

Primjer 27. Odrediti τ (600). Rjeˇsenje. τ (600) = τ (23 · 3 · 52 ) = 4 · 2 · 3 = 24. Primjer 28. Pokazati da je n potpun kvadrat ako je τ (n) neparan broj. Rjeˇsenje. Broj n = pα1 1 · · · pαk k je potpun kvadrat ako i samo ako su eksponenti α1 , . . . , αk parni brojevi, tj. ako i samo ako je proizvod (1+α1 ) · · · (1+ αk ) neparan broj. Primjer 29. Na´ci broj rjeˇsenja u obliku uredenih parova prirodnih brojeva (x, y) jednaˇcine 1 1 1 + = , x y n gdje je n prirodan broj. Rjeˇsenje. Iz date jednaˇcine dobijamo 1 1 1 + = ⇔ xy = nx + ny ⇔ (x − n)(y − n) = n2 . x y n Ako je n = 1, tada data jednaˇcina ima jedinstveno rjeˇsenje (2, 2). Za n ≥ 2, neka je n = pα1 1 pα2 2 · · · pαk k kanonska dekompozicija broja n. Kako je x, y > n, postoji bijekcija izmedu rjeˇsenja (x, y) i djelilaca od n2 . Prema tome, broj rjeˇsenja je τ (n2 ) = (2α1 + 1)(2α2 + 1) · · · (2αk + 1). DEFINICIJA 1.10. Suma svih pozitivnih djelilaca broja n oznaˇcava se sa σ(n). TEOREMA 1.22. Ako je n = pα1 1 · pα2 2 · · · pαk k kanonska dekompozicija broja n, tada je α +1

σ(n) =

1 − pk k 1 − pα1 1 +1 1 − pα2 2 +1 · ··· . 1 − p1 1 − p2 1 − pk

Dokaz. Vrijedi σ(n) =

X

pβ1 1 pβ2 2 · · · pβk k =

0≤βi ≤αi , 1≤i≤k

=

Y 1 − pαi +1 i . 1 − pi

1≤i≤k

Y 1≤i≤k

1 + pi + p2i + · · · + pαi 1




Glava 1. Teorija brojeva

35

TEOREMA 1.23. Funkcija σ je multiplikativna. Dokaz. Slijedi direktno iz Teoreme 1.22. Primjer 30. Izraˇcunati σ(500). Rjeˇsenje. σ(500) = σ(22 · 53 ) =

1 − 23 1 − 54 · = 1092. 1−2 1−5

DEFINICIJA 1.11. Broj n je savrˇsen ako je σ(n) = 2n. Savrˇseni brojevi su rijetki. Prvih pet glasi: 6, 28, 496, 8128, 33550336. Primjer 31. Ako je n savrˇsen broj pokazati da vrijedi X1 d|n

d

= 2.

Rjeˇsenje. X1 d|n

d

=

X 1 1X 1 1 = d = σ(n) = 2n = 2. n/d n n n d|n

d|n

TEOREMA 1.24. (Euklid) Ako je za neki prirodan broj n broj 2n −1 prost onda je 2n−1 (2n − 1) savrˇsen broj. Dokaz. Dovoljno je dokazati da je σ(2n−1 (2n − 1)) = 2n (2n − 1). Zato, odredimo djelioce broja 2n−1 · p, gdje je p = 2n − 1. To su brojevi 1, 2, 22 , . . . , 2n−1 , p, 2p, 22 p, . . . , 2n−1 p. Prema tome, imamo σ(2n−1 p) =1 + 2 + 22 + · · · + 2n−1 + p + 2p + 22 p + · · · + 2n−1 p =(p + 1)(1 + 2 + 22 + · · · + 2n−1 ) =(p + 1)(2n − 1) =2n (2n − 1).

36

1.7. Multiplikativne funkcije

TEOREMA 1.25. (Ojler28 ) Svaki paran savrˇsen broj je oblika 2n−1 (2n − 1), gdje je n prirodan broj i 2n − 1 prost broj. Dokaz. Neka je k savrˇsen broj i n − 1 najve´ci eksponent broja 2 takav da 2n−1 | k. Tada, za neki prirodan broj m vrijedi 2k = σ(k) = σ(2n−1 m) = σ(2n−1 )σ(m), jer su 2n−1 i m relativno prosti brojevi. Kako je σ(pk ) =

pk+1 − 1 , p−1

dobijamo, 2k = (2n − 1)σ(m), tj. 2n m = (2n − 1)σ(m). Odavde je

(1.8)

m 2n − 1 = . σ(m) 2n

Kako je razlomak (2n − 1)/2n nesvodljiv jer su 2n − 1 i 2n relativno prosti brojevi, dobijamo da je m = c(2n − 1) i σ(m) = c2n , za neki prirodan broj c. Dokaˇzimo da je c = 1. Pretpostavimo da je c 6= 1. U tom sluˇcaju je, σ(m) ≥ m + c + 1, jer m ima barem m, c i 1 kao djelioce. Zato je, σ(m) ≥ c(2n − 1) + c + 1 = 2n c + 1 > σ(m), kako je σ(m) = 2n c, to je kontradikcija. Prema tome c = 1, odakle slijedi m = 2n − 1 i k = 2n−1 (2n − 1), jer je k = 2n−1 m. Sada, zbog (1.8) imamo (2n − 1)σ(2n − 1) = 2n (2n − 1), tj. σ(2n − 1) = 2n = (2n − 1) + 1. Prema tome, jedini djelioci broja 2n − 1 su sam taj broj i broj 1. Odavde dobijamo da je 2n − 1 prost broj. 28

Leonhard Paul Euler, (1707-1783) ˇsvajcarski matematiˇcar.

Glava 1. Teorija brojeva

37

Napomena 1.11. Jedan od najstarijih otvorenih problema u teoriji brojeva je pitanje egiztencije neparnog savrˇsenog broja. R. P. Brent, G. L. Cohen i H. J. J. te Riele29 su u zajedniˇckom radu 1993. godine pokazali da ako postoji neparan savrˇsen broj onda mora biti ve´ci od 10300 , dok su P. Ochem i M. Rao30 2012. godine pokazali da mora biti ve´ci od 101500 .

Primjer 32. Pokazati da svaki neparan savrˇsen broj ima bar tri razliˇcita prosta faktora. Rjeˇsenje. Pretpostavimo suprotno. Tada postoji neparan savrˇsen broj n koji je oblika n = pk , gdje je p ≥ 3 prost broj i k prirodan broj ili je n oblika n = pk11 pk22 , gdje su p2 > p1 ≥ 3 prosti brojevi i k1 , k2 prirodni brojevi. Ako je n = pk onda je   1 1 1 σ(n) =1 + p + p + · · · + p = p 1 + + 2 + · · · k p p p   1 1 1 1 1 n i m, n su relativno prosti brojevi razliˇcite parnosti. Dokaz. Jednaˇcinu (1.11) moˇzemo pisati u obliku y 2 = (z + x)(z − x).

(1.13)

48

1.10. Pitagorine trojke

Neka je y = 2c. Brojevi z + x i z − x su parni, pa postoje prirodni brojevi a i b takvi da je z + x = 2a, z − x = 2b. Sada imamo c2 = ab.

(1.14)

Kako je z = a + b, x = a − b, dobijamo da su brojevi a i b relativno prosti. Prema tome, iz (1.14) slijedi da postoje relativno prosti prirodni brojevi m i n takvi da je a = m2 , b = n2 . Odavde je x = m2 − n2 , z = m2 + n2 , y = 2mn. Brojevi m i n ne mogu biti oba parni jer su relativno prosti i ne mogu biti oba neparni jer je zbog leme 1.3 broj x = m2 − n2 neparan. Prema tome, brojevi m i n su razliˇcite parnosti. Lako se provjeri da x, y i z dati sa (1.12) zadovoljavaju jednaˇcinu (1.11). Treba joˇs pokazati da je (x, y, z) primitivna Pitagorina trojka. Pretpostavimo da brojevi x i z imaju zajedniˇcki djelilac d > 1. Tada je d neparan, d | (m2 + n2 ) + (m2 − n2 ) = 2m2 i d | (m2 + n2 ) − (m2 − n2 ) = 2n2 , a ovo je u kontradikciji s pretpostavkom da su m i n relativno prosti. TEOREMA 1.33. Jednaˇcina x4 +y 4 = z 2 nema rjeˇsenja u skupu prirodnih brojeva. Dokaz. Pretpostavimo suprotno. Tada postoje prirodni brojevi x, y i z, koji su rjeˇsenje date jednaˇcine. Neka su x, y i z takvi da je z najmanji mogu´ci. Pokaza´cemo da nas to vodi u kontradikciju jer moˇzemo na´ci novo rjeˇsenje (x1 , y1 , z1 ) kod koga je z1 < z. Pretpostavimo da je (x, y) > 1, tada postoji prost broj p koji dijeli x i y. Odavde slijedi da p4 | (x4 + y 4 ), tj. p4 | z 2 , pa p2 | z. Tada je (x/p)4 + (y/p)4 = (z/p2 )2 , pa smo naˇsli rjeˇsenje sa manjom vrijednosti od z. Ovo je u kontradikciji sa izborom (x, y, z), pa zakljuˇcujemo da je (x, y) = 1. Prema tome, (x2 , y 2 ) = 1, pa je (x2 , y 2 , z) primitivna Pitagorina trojka. Pretpostavimo da je x2 neparan i y 2 paran. Prema teoremi 1.32 postoje relativno prosti brojevi u i v takvi da vrijedi x2 = u2 − v 2 , y 2 = 2uv, z = u2 + v 2 . Odavde dobijamo da je (x, v, u) primitivna Pitagorina trojka sa neparnim x. Zbog toga, postoje relativno prosti brojevi s i t takvi da je x = s2 − t2 , v = 2st, u = s2 + t2 .

Glava 1. Teorija brojeva

49

Kako je (s, t) = 1 dobijamo da su u, s i t po parovima relativno prosti. Kako je (y/2)2 = uv/2 = ust, proizvod u · s · t je potpun kvadrat, a ovo implicira da su u, s i t potpuni kvadrati. Zato postoje brojevi a, b i c takvi da je s = a2 , t = b2 i u = c2 . Kako je u = s2 + t2 , dobijamo a4 + b4 = c2 , tj. (a, b, c) je pozitivno rjeˇsenje polazne jednaˇcine. Ovo je u kontradikciji sa √ pretpostavkom da je z minimalan, jer vrijedi c = u ≤ u2 < u2 +v 2 = z. Posljedica 1.5. Jednaˇcina x4 + y 4 = z 4 , nema rjeˇsenja u skupu prirodnih brojevima. Dokaz. Ako bi (x, y, z) bilo rjeˇsenje date jednaˇcine onda je (x, y, z 2 ) rjeˇsenje jednaˇcine iz teoreme 1.33, a ovo je kontradikcija. Primjer 43. Pokazati da ne postoji Pitagorin trougao ˇcija je povrˇsina jednaka kvadratu prirodnog broja. Rjeˇsenje. Pretpostavimo da takav trougao postoji i da su mu x, y katete, z hipotenuza, a P povrˇsina. Tada je x2 + y 2 = z 2 , xy = 2P. Po pretpostavci postoji prirodan broj n takav da je P = n2 , tj. 2xy = (2n)2 . Sada imamo z 2 + (2n)2 = (x + y)2 , z 2 − (2n)2 = (x − y)2 , a odavde mnoˇzenjem dobijamo z 4 = (2n)4 + (x2 − y 2 )2 . Ovo je u suprotnosti sa teoremom 1.33.

1.11

Zadaci

1. Dati su brojevi 125 i 962. (a) Odrediti njihove kanonske dekompozicije. (b) Na´ci (125, 962). (c) Na´ci [125, 962]. Rjeˇsenje. Primjetimo da je 125 = 53 , 962 = 2·13·37, pa je (125, 962) = 1, a [125, 962] = 125 · 962 = 120250. 2. Koriste´ci Euklidov algoritam rijeˇsiti Diofantove jednaˇcine:

50

1.11. Zadaci (a) 2918x + 19y = 1, (b) 361x + 418y = (361, 418), (c) 3x + 4y + 5z = 6. Rjeˇsenje. (a) Vrijedi 2918 = 153 · 19 + 11 19 = 11 + 8 11 = 8 + 3 8=2·3+2 3=2+1 2 = 2 · 1. Odavde vidimo da je (2918, 19) = 1. Odredimo bar jedno rjeˇsenje polazne jednaˇcine. Imamo 1 = 3 − 2 = 3 − (8 − 3 · 2) = 3 · 3 − 8 = 3 · (11 − 8) − 8 = 3 · 11 − 4 · 8 = 3 · 11 − 4(19 − 11) = 7 · 11 − 4 · 19 = 7 · (2918 − 19 · 153) − 4 · 19 = 7 · 2918 − 1075 · 19. Odavde vidimo da je x0 = 7, y0 = −1075 jedno rjeˇsenje polazne jednaˇcine. (b) Radi se na isti naˇcin kao i (a). (c) Primjetimo da je 3x + 4y + 5z = 6 ⇔ 3x + 4y = 1 + 5(1 − z). Iz ˇcinjenice (3, 4, 5) = 1, slijedi da jednaˇcina ima rjeˇsenja u skupu Z. Kako traˇzimo samo cjelobrojna rjeˇsenja polazne jednaˇcine, tada je 3x + 4y ≡ 1 (mod 5), pa je 3x + 4y = 1 + 5k, k ∈ Z. Odavde je x1 = −1 + 3k, y1 = 1 − k, pa je opˇste rjeˇsenje {(−1 + 3k + 4t, 1 − k − 3t, 1 − t) : k, t ∈ Z}. 3. Koriste´ci Blenkinˇsipov algoritam rijeˇsiti Diofantove jednaˇcine: (a) 267x + 110y = (267, 110), (b) 466x − 11y = (466, −11), (c) 2012x + 19y = 1.

Glava 1. Teorija brojeva

51

Rjeˇsenje. Uradimo samo zadatak (a), jer se ostali rade na sliˇcan naˇcin. Posmatrajmo matricu   267 1 0 . 110 0 1 Vrijedi 267 = 110 · 2 + 47, pa mnoˇze´ci sa −2 drugu vrstu i sabiraju´ci je sa prvom imamo   47 1 −2 . 110 0 1 Kako je 110 = 47 · 2 + 16, mnoˇze´ci sa −2 prvu vrstu i sabiraju´ci je drugoj dobijamo   47 1 −2 , 16 −2 5 47 = 16 · 2 + 15, pa mnoˇze´ci sa −2 drugu vrstu i sabiraju´ci je prvoj imamo   15 5 −12 , 16 −2 5 mnoˇze´ci sa −1 vrstu 1 i sabiraju´ci je sa vrstom 2, slijedi   15 5 −12 , 1 −7 17 mnoˇze´ci sa −15 vrstu 2 i sabiraju´ci je sa vrstom 1, dobijamo   0 110 −267 . 1 −7 17 Ovo povlaˇci da je (267, 110) = 1 i 1 = 267 · (−7) + 17 · 110. 4. Odrediti najmanji pozitivan broj koji ima taˇcno k djelilaca za k ∈ {1, . . . , 6}. Uputstvo. Koristiti da je τ (n) = (1 + α1 ) · · · (1 + αt ), gdje je n = pα1 1 ·pα2 2 · · · pαt t , p1 , p2 , ..., pt su razliˇciti prosti brojevi, a αi , i = 1, 2, ..., t su nenegativni cijeli brojevi. 5. Neka su x i y cijeli brojevi. Dokazati da je 3x + 4y djeljiv sa 11 ako i samo ako je x + 5y djeljiv sa 11. Rjeˇsenje. Iz 11 | 3x + 4y slijedi 11 | 4(3x + 4y), pa 11 | 12x + 16y. Kako je 12x + 16y = 11x + 11y + (x + 5y),

52

1.11. Zadaci dobijamo 11 | x + 5y. S druge strane, 11 | x + 5y ⇒ 11 | 3(x + 5y), pa 11 | (3x + 4y) + 11y, a odavde dobijamo 11 | 3x + 4y. 6.

36

Neka su a, b i c tri razliˇcita cijela broja i P polinom sa cjelobrojnim koeficijentima. Dokazati da je nemogu´ce da je P (a) = b, P (b) = c, P (c) = a. Rjeˇsenje. Neka je P (x) = an xn + · · · + a1 x + a0 , gdje su a0 , a1 , . . . , an , cijeli brojevi. Vrijedi P (x) − P (y) =an xn + · · · + a1 x + a0 − (an y n + · · · a1 y + a0 ) =an (xn − y n ) + · · · a1 (x − y), odakle dobijamo da za cijele brojeve x i y vaˇzi x − y | P (x) − P (y).

(1.15)

Prema tome, iz relacije (1.15) slijedi a − b | P (a) − P (b) = b − c,

(1.16)

a − c | P (a) − P (c) = b − a,

(1.17)

b − c | P (b) − P (c) = c − a.

(1.18)

Iz relacija (1.16), (1.17) i (1.18) dobijamo da postoje cijeli brojevi k1 , k2 i k3 takvi da je b − c = k1 (a − b), (1.19) b − a = k2 (a − c),

(1.20)

c − a = k3 (b − c).

(1.21)

Sada, iz relacija (1.19), (1.20) i (1.21) dobijamo da je k1 · k2 · k3 = 1,

(1.22)

kako su k1 , k2 i k3 cijeli brojevi, bar jedan od njih je jednak 1. Neka je to npr. k1 (sliˇcno se postupi i ako je to k2 ili k3 ). Tada iz (1.19) a+c dobijamo da je b = , pa uvrˇstavanjem u (1.20) dobijamo 2 c−a = k2 (a − c), 2 a ovo je kontradikcija, jer je k2 cijeli broj. 36

Medunarodna matematiˇcka olimpijada, SAD, 1974.

Glava 1. Teorija brojeva

53

7. Dokazati da je (m, n)[m, n] = mn, za sve m, n ∈ N. Rjeˇsenje. Pretpostavimo da je m = pa11 · pa22 · · · pakk , n = pb11 · pb22 · · · pbkk , gdje su p1 , p2 , . . . , pk prosti brojevi i ai , bi , ci , i ∈ {1, . . . , k} nenegativni cijeli brojevi. Koriste´ci (1.1) dobijamo max{a1 ,b1 }

· p2

min{a1 ,b1 }

· p2

[m, n] = p1

(m, n) = p1

max{a2 ,b2 }

· · · pk

max{ak ,bk }

min{a2 ,b2 }

· · · pk

min{ak ,bk }

,

.

Sada se zadatak svodi da se pokaˇze da je max{ai , bi } + min{ai , bi } = ai + bi , i = 1, 2, ...k. Moˇzemo pretpostaviti da vrijedi ai ≤ bi . Iz te pretpostavke slijedi tvrdenje. 8. Dokazati da je (m, n, p) [m, n, p] = , mnp (m, n)(m, p)(n, p) za sve m, n, p ∈ N. Uputstvo. Pogledati primjer 5. n n o p 9. Ako je (p, q) = 1 i p ≥ 2 dokazati da u nizu qn+1 ima beskonaˇcno mnogo cijelih brojeva. Rjeˇsenje. Kako je (p, q) = 1, to je i (pk , q) = 1 za sve k ∈ N. Za svaki prirodan broj k vaˇzi q|pkϕ(q) − 1. Neka je nk =

pkϕ(q) − 1 . q

Tada je pnk pnk = kϕ(q) = pnk −kϕ(q) . qnk + 1 p Kako je p ≥ 2, za dovoljno veliko k vrijedi nk ≥ kϕ(q).

54

1.11. Zadaci

10.

37

Za dato c ∈ N, neka je n0 najmanji prirodan broj takav da je 2n0 > c. Dokazati da tada za sve n > n0 vaˇzi an | cbn ⇒ a | b, gdje su a, b ∈ N. Rjeˇsenje. Neka je p prost broj i neka su α, β i γ redom najviˇsi stepeni kojim p dijeli brojeve a, b, c, za koje smo pretpostavili da an | cbn (n ≥ n0 ). Imamo nα ≤ γ + nβ. S druge strane, kako je 2n0 > c, to je γ < n0 ≤ n. Prema tome, nα < nβ + n = n(β + 1), pa je α < β + 1, tj. α ≤ β. Kako je p proizvoljan prost broj, slijedi a | b.

11. Dokazati da je n4 + 4n sloˇzen broj za svaki n > 1. Uputstvo. Koristiti ideju rjeˇsenja iz primjera 11. 12. Dokazati da ako je a > 3 brojevi a, a + 2, a + 4 ne mogu biti svi prosti. Pjeˇsenje. Svaki prost broj a ve´ci od 3 moˇzemo zapisati u obliku a = 3k+1 ili a = 3k+2, k ∈ N. Za a = 3k+1 dobijamo brojeve 3k+1, 3(k+ 1), 3k + 5. Broj 3(k + 1) je sloˇzen, pa brojevi a, a + 2, a + 4 ne mogu biti svi prosti. Za a = 3k + 2 dobijamo brojeve 3k + 2, 3k + 4, 3k + 6. Broj 3k + 6 je sloˇzen odakle slijedi da brojevi a, a + 2, a + 4 ne mogu biti svi prosti. 13. Odrediti sve proste brojeve p takve da je 2p + 1 kub prirodnog broja. Rezultat. Jedini prost broj koji ispunjava uslov zadatka je p = 13. 377 − 1 14. Dokazati da je neparan i sloˇzen broj. 2 Pjeˇsenje. Primjetimo da je 377 − 1 (3 − 1)(376 + 375 + · · · + 3 + 1) = = 376 + 375 + · · · + 3 + 1. 2 2 37

Nacionalna olimpijada, Rumunija, 1991.

Glava 1. Teorija brojeva

55

Broj 376 + 375 + · · · + 3 + 1 je neparan kao zbir 77 neparnih brojeva. Ovim smo dokazali da je posmatrani broj neparan. Dokaˇzimo da je sloˇzen. Kako je 377 − 1 311·7 − 1 (311 − 1)(366 + 355 + · · · + 1) = = 2 2 2 (3 − 1)(310 + 39 + · · · + 1)(366 + 355 + · · · + 1) = 2 = (310 + 39 + · · · + 1)(366 + 355 + · · · + 1), vidimo da je

377 − 1 sloˇzen broj. 2

15. Odrediti sve prirodne brojeve a i b takve da je a4 + 4b4 prost broj. Rjeˇsenje. Vrijedi a4 + 4b4 =a4 + 4a2 b2 + 4b4 − 4a2 b2 (a2 + 2b2 )2 − (2ab)2 =(a2 + 2b2 − 2ab)(a2 + 2b2 + 2ab) =[(a − b)2 + b2 ][(a + b)2 + b2 ]. Kako su a i b prirodni brojevi vrijedi (a + b)2 + b2 > 1, pa je a4 + 4b4 prost broj ako je (a − b)2 + b2 = 1. Odavde je a = b = 1. 16. Dokazati da ako je 2n + 1 prost da je n sloˇzen. Rjeˇsenje. Ako je broj n sloˇzen, tada je on oblika n = n1 · n2 , gdje su 1 < n1 < n, 1 < n2 < n. Tada je 2n − 1 = 2n1 ·n2 − 1, odakle slijedi da 2n1 − 1 | 2n − 1, pa je broj 2n − 1 sloˇzen. Kako brojevi 2n − 1 i 2n + 1 ne mogu biti istovremeno prosti, slijedi da je broj 2n + 1 prost broj. 17. Neka je broj 2k + 1 prost. Dokazati da je tada k = 0 ili k = 2n za neki n ≥ 0.38 Rjeˇsenje. Ako je k = 0, broj 20 + 1 = 2 je prost. Pretpostavimo da je k = 2n · m, gdje je m > 1 neparan broj. Tada je 2k + 1 = 22 38

n

n ·m

n

+ 1 ⇒ 22 + 1 | 2k + 1,

Brojevi Tn = 22 + 1 nazivaju se Fermaovi brojevi. Ferma je smatrao da su svi oni prosti. Zaista, T0 = 3, T1 = 5, T2 = 17, T3 = 257 i T4 = 65537 su prosti. Medutim, T5 = 232 + 1 je sloˇzen, 641 | T5 . Hipoteza je da je samo konaˇcno mnogo Fermaovih brojeva prosto.

56

1.11. Zadaci pa broj 2k + 1 je sloˇzen, ˇsto je kontradikcija sa pretpostavkom. Dakle k = 2n . n

18. Definiˇsimo niz Tn = 22 + 1, n ∈ N. Dokazati da je (Tn , Tm ) = 1 za n 6= m. Rjeˇsenje. Vrijedi n

n−1 ·2

Tn − 2 =22 − 1 = 22

−1

2

2 =(Tn−1 − 1) − 1 = Tn−1 − 2Tn−1

=Tn−1 (Tn−1 − 2) =Tn−1 Tn−2 (Tn−2 − 2) .. . =Tn−1 Tn−2 · · · T1 T0 (T0 − 2) =Tn−1 Tn−2 · · · T1 T0 , za sve n. Zbog toga, zajedniˇcki djelilac od Tn i Tm mora da dijeli 2. Ali svaki Tn je neparan, pa su Tn i Tm uzajamno prosti. 19. Pokazati da je n + 1 djelilac broja 1m + 2m + · · · + nm , za svaki prirodan broj n > 1 i svaki neparan prirodan broj m. Uputsvo. Koristiti da za sve a, b ∈ N i neparne m ∈ N, a + b | am + bm . 20. Odrediti sa koliko nula se zavrˇsava 2009!. Rjeˇsenje. Broj nula je jednak broju eksponenta broja 5 u kanonskoj dekompoziciji broja 2009!, a to je         2009 2009 2009 2009 + + + = 401 + 80 + 16 + 3 = 500. 5 52 53 54   20 21. Odrediti faktorizaciju preko prostih brojeva za i 20!. 10 Rjeˇsenje. Na osnovu osnovne teoreme aritmetike je 20! = 2a1 · 3a2 · 5a3 · 7a4 · 11 · 13 · 17 · 19.

Glava 1. Teorija brojeva

57

Odredimo a1 , a2 , a3 i a4 . Imamo        20 20 20 20 + + + = 18 = 2 4 8 16     20 20 = + =8 3 9   20 = =4 5   20 =2 = 7 

a1 a2 a3 a4

Tada je 20! = 218 · 38 · 54 · 72 · 11 · 13 · 17 · 19. Kako je   20 20! = , 10 10! · 10! odredimo faktorizaciju broja 10! preko prostih faktora. Kao i ranije, zakljuˇcujemo da je 10! = 2b1 · 3b2 · 5b3 · 7, gdje su 

     10 10 10 b1 = + + =8 2 4 8     10 10 b2 = + =4 3 9   10 = 2. b3 = 5 Tada je 10! = 28 · 34 · 52 · 7, pa je   20 218 · 38 · 54 · 72 · 11 · 13 · 17 · 19 = = 22 · 11 · 13 · 17 · 19. 10 (28 · 34 · 52 · 7)2 22. Dokazati da broj sa 30 cifara ne moˇze imati viˇse od 100 prostih faktora. Rjeˇsenje. Pretpostavimo da broj sa 30 cifara ima 101 prostih faktora koje smo oznaˇcili sa p1 , p2 , . . . , p101 . U tom sluˇcaju imamo 2101 ≤ p1 · p2 · · · p101 < 1030 , kako je pi ≥ 2, i = 1, 2, . . . , 101, dobijamo 2101 < 1030 , a odavde slijedi 27.1 < 53 , ˇsto je nemogu´ce.

58

1.11. Zadaci

23. Dokazati da 30 | m5 − m za sve m ∈ N. Rjeˇsenje. Kako je m5 − m = m(m4 − 1) = m(m − 1)(m + 1)(m2 + 1), zakljuˇcujemo da je posmatrani broj djeljiv sa 6 kao proizvod tri uzastopna prirodna broja. Pokaˇzimo da 5 | m5 − m. Ako 5 | m, tada 30 | m5 − m. Pretpostavimo da (m, 5) = 1. Tada je na osnovu male Fermaove teoreme m5 ≡ m (mod 5), odakle zakljuˇcujemo da 30 | m5 − m. 24. Dokazati da zbir kvadrata pet uzastopnih cijelih brojeva ne moˇze biti potpun kvadrat. Rjeˇsenje. Potpun kvadrat pri dijeljenju sa 4 daje ostatak 0 ili 1 (u zavisnosti da li je paran ili neparan broj), ali zbir kvadrata pet uzastopnih cijelih brojeva se moˇze zapisati sa (n − 2)2 + (n − 1)2 + n2 + (n + 1)2 + (n + 2)2 = 4(n2 + 2) + 2, pa pri dijeljenju sa 4 daje ostatak 2. 25. Dokazati da razlomak

26n + 5 ne moˇze da se skrati ni za jedan priro39n + 7

dan broj n. Rjeˇsenje. Ako d | 26n + 5 i d | 39n + 7 onda imamo da d | 3(26 + 5) − 2(39 + 7) = 1, pa dobijamo d = 1.

26. Pokazati da je (k 4 + 3k 2 + 1, k 3 + 2k) = 1 za svaki k ∈ N. Rjeˇsenje. Primjetimo da je k 4 + 3k 2 + 1 = k(k 3 + 2k) + k 2 + 1, pa je (k 4 + 3k 2 + 1, k 3 + 2k) = (k 3 + 2k, k 2 + 1) (koristili smo da iz a = bq + r ⇒ (a, b) = (b, r)). Dalje je k 3 + 2k = k(k 2 + 1) + k, odakle zakljuˇcujemo da je (k 3 + 2k, k 2 + 1) = (k 2 + 1, k) = 1. Dakle, (k 4 + 3k 2 + 1, k 3 + 2k) = 1.

Glava 1. Teorija brojeva

59

27. Dato je n brojeva a1 , a2 , . . . , an . Dokazati da se od njih moˇze odabrati nekoliko ˇciji je zbir kvadrata djeljiv sa n. Rjeˇsenje. Ako je neki od brojeva s1 = a21 , s2 = a21 + a22 , . . . , sn = a21 + a22 + · · · + a2n , djeljiv sa n tvrdenje je dokazano. Ako nije, tada postoje dva od tih brojeva si i sj , (i < j), koji imaju isti ostatak pri djeljenju sa n, a u ovom sluˇcaju je sj − si traˇzeni broj. 28. Na´ci najmanji broj koji pri dijeljenju sa n, n + 1, . . . , n + m daje redom ostatke r, r + 1, . . . , r + m. Rezultat. [n, n + 1, ..., n + m] − n + r. 29. Neka je S = {n ∈ N | n nema drugih prostih djelilaca osim p, q i r}. X1 Izraˇcunati . n n∈S Rjeˇsenje. Vrijedi, +∞ +∞ +∞ X1 X 1 X 1 X 1 X 1 = = −1 n pi qj pi q j r k rk

n∈S

i=0

n∈S

1 = 1−

1 p

1 · 1−

1 q

1 · 1−

j=0

1 r

k=0

−1=

pqr − 1. (p − 1)(q − 1)(r − 1)

√ 30. Dokazati da je τ (n) < 2 n, za sve n ∈ N. Uputstvo. Ako n nije potpun kvadrat, grupisati njegove djelioce u √ n n parove oblika (d, ), d < kojih ima manje od n. Ako je n potpun d d √ √ √ kvadrat, sliˇcno se dobije da je τ (n) ≤ 2( n − 1) + 1 = 2 n − 1 < 2 n. 31. Koliko ima djeljitelja broja 3030 koji imaju taˇcno 30 djeljitelja? Rjeˇsenje. Broj 3030 moˇzemo zapisati u obliku 3030 = 230 · 330 · 530 . Iz ovoga vidimo da su djeljitelji broja 3030 oblika x = 2a · 3b · 5c , gdje je 0 ≤ a, b, c ≤ 30. Iz uslova zadatka je τ (x) = (1 + a)(1 + b)(1 + c) = 30, pa imamo sljede´ce mogu´cnosti: - Broj 30 moˇzemo predstaviti kao 30 · 1 · 1, 1 · 30 · 1 ili 1 · 1 · 30, - 30 = 15 · 2 · 1, 6 mogu´cnosti, - 30 = 10 · 3 · 1, 6 naˇcina, - 30 = 6 · 5 · 1, 6 naˇcina,

60

1.11. Zadaci - 30 = 5 · 3 · 2, 6 naˇcina. Prema tome, ima ukupno 27 djelilaca broja 3030 koji imaju taˇcno 30 djelilaca.

32. Odrediti broj i zbir djelilaca broja 2010. Rjeˇsenje. Broj 2010 moˇzemo zapisati u kanonskom obliku 2010 = 2 · 3 · 5 · 67. Tada je τ (2010) = 24 = 16, σ(2010) =

22 − 1 32 − 1 52 − 1 672 − 1 · · · = 4896. 2 − 1 3 − 1 5 − 1 67 − 1

33. Odrediti sve proste brojeve p za koje je (a) broj 2p savrˇsen broj, (b) broj p2 savrˇsen broj. Rjeˇsenje. (a) Broj n je savrˇsen ako je σ(n) = 2n. Iz uslova zadatka je σ(2p) = 4p. Kako je σ(2p) =

22 − 1 p 2 − 1 · = 3(p + 1), za p > 2, 2−1 p−1

dobijamo 3p + 3 = 4p, pa je p = 3. (b) Iz σ(p2 ) = 2p2 slijedi p2 + p + 1 = 2p2 . Ova jednaˇcina nema rjeˇsenja u skupu prirodnih brojeva, pa takvih prostih brojeva nema. 34. Ako je f : N → N, multiplikativna funkcija, dokazati da je g : N → N, data sa X g(n) = f (d), d|n

Glava 1. Teorija brojeva

61

multiplikativna funkcija. Rjeˇsenje. Neka su m i n uzajmno prosti prirodni brojevi. Vrijedi X X X f (d1 )f (d2 ) f (d1 d2 ) = f (d) = g(mn) = =

d1 |m,d2 |n

d1 |m,d2 |n

d|mn

XX

X

f (d1 )f (d2 ) =

d1 |m d2 |n

d1 |m

f (d1 )

X

f (d2 )

d2 |n

=g(m)g(n). 35. Ako je n = pk11 pk22 · · · pkr r kanonska dekompozicija broja n, dokazati da je X Y 1 + p2ki +1 i dϕ(d) = . 1 + pi d|n

1≤i≤r

Rjeˇsenje. Prema prethodnom zadatku funkcija X f (n) = dϕ(d), d|n

je multiplikativna. Zato, odredimo f (pk ), gdje je p prost broj, f (pk ) =

X

dϕ(d)

d|pk

=1 + ϕ(1) + pϕ(p) + p2 ϕ(p2 ) + · · · + pk ϕ(pk ) =1 + p(p − 1) + p2 (p2 − p) + · · · + pk (pk − pk−1 ) =1 + (p2 − p) + (p4 − p3 ) + · · · + (p2k − p2k−1 ) =1 − p + p2 − p3 + p4 + · · · − p2k−1 + p2k 1 − (−p)2k+1 1 − (−p) 1 + p2k+1 = . 1+p

=

Prema tome, f (n) =f (pk11 pk22 · · · pkr r ) =f (pk11 )f (pk22 ) · · · f (pkr r ) =

2 +1 1 +1 r +1 1 + p2k 1 + p2k 1 + p2k r 1 2 · ··· . 1 + p1 1 + p2 1 + pr

62

1.11. Zadaci

36. Neka su a, b, c i d (a 6= c) prirodni brojevi. Dokazati a ≡ c(mod ab + cd) ⇔ a ≡ c(mod ad + bc). Rjeˇsenje. Tvrdenje slijedi iz identiteta ab + cd = (a − c)(b − d) + ad + bc. Primjetimo da vrijedi i b ≡ d(mod ab + cd) ⇔ b ≡ d(mod ad + bc). 37. Odrediti ostatak pri dijeljenju broja 641500 sa 9. Rezultat. 1. 38. Dokazati da ako su a1 , a2 , . . . , a9 brojevi koji nisu djeljivi sa 3, onda a21 + a22 + . . . + a29 ≡ 0

(mod 3).

Rjeˇsenje. Iz uslova zadatka je, na osnovu male Fermaove teoreme, a2i ≡ 1

(mod 3), i = 1, 2, . . . , 9,

pa je a21 + a22 + . . . + a29 ≡ 9 ≡ 0

(mod 3).

39. Ako je p prost broj onda za sve a, b, c ∈ N vrijedi 6p | a + b + c ⇔ 6p | ap + bp + cp . Uputstvo. Koristiti malu Fermaovu teoremu. 40. Rijeˇsiti jednaˇcinu 22009 x ≡ 1

(mod 13).

Rjeˇsenje. Primjetimo da je 212 ≡ 1 (mod 13), pa je 22009 ≡ 2167·12+5 ≡ 25 ≡ 6

(mod 13).

Kako je 22009 x ≡ 6x (mod 13), polazna jednaˇcina se svodi na 6x ≡ 1 x ≡ 11

(mod 13) / · 11 (mod 13).

Glava 1. Teorija brojeva

63

41. Koriste´ci Ojlerovu teoremu rijeˇsiti kongruencijsku jednaˇcinu 22x ≡ 1

(mod 729).

Rjeˇsenje. Na osnovu Ojlerove teoreme je x ≡ 22ϕ(729)−1

(mod 729).

Kako je   1 ϕ(729) = ϕ(3 ) = 729 1 − = 486, 3 6

prethodna jednaˇcina svodi se na x ≡ 22485

(mod 729).

Primjetimo da je 226 ≡ 1 (mod 729), pa je 22485 ≡ 226·80+5 ≡ 225 ≡ 631

(mod 729).

Rjeˇsenje jednaˇcine je x ≡ 631 (mod 729). 42. Rijeˇsiti sistem kongruencijskih jednaˇcina (a) x≡2

(mod 3)

x≡3

(mod 5)

x≡2

(mod 7).

x≡1

(mod 2)

x≡2

(mod 3)

x≡3

(mod 5).

(b)

Rjeˇsenje. (a) Primjetimo da je (3, 5, 7) = 1, pa ´cemo sistem rjeˇsavati koriste´ci kinesku teoremu o ostacima. Vrijedi a1 = 2, a2 = 3, a3 = 2, m1 = 3, m2 = 5, m3 = 7, M M M M = 105, = 35, = 21, = 15. m1 m2 m3

64

1.11. Zadaci Odredimo b1 , b2 , b3 . Iz 35b1 ≡ 1

(mod 3) ⇒ 2b1 ≡ 1

(mod 3) ⇒ b1 ≡ 2

21b2 ≡ 1

(mod 5) ⇒ b2 ≡ 1

(mod 5)

15b3 ≡ 1

(mod 7) ⇒ b3 ≡ 1

(mod 7)

(mod 3)

dobijamo 3 X M ai bi = 233. x0 = mi i=1

Rjeˇsenje sistema je x = 105t + 23, t ∈ Z. (b) a1 = 1, a2 = 2, a3 = 3, m1 = 2, m2 = 3, m3 = 5, M M M M = 30, = 15, = 10, = 6. m1 m2 m3 Iz 15b1 ≡ 1

(mod 2) ⇒ b1 ≡ 1

(mod 2)

10b2 ≡ 1

(mod 3) ⇒ b2 ≡ 1

(mod 3)

6b3 ≡ 1

(mod 5) ⇒ b3 ≡ 1

(mod 5)

dobijamo x0 =

3 X M ai bi = 15 + 20 + 18 = 53 mi i=1

Rjeˇsenje sistema je x = 30t + 23, t ∈ Z. 43.

39

Neka su m i n prirodni brojevi sa osobinom da za sve prirodne brojeve k vaˇzi (11k − 1, m) = (11k − 1, n). Dokazati da tada za neki m cijeli broj s vaˇzi = 11s . n Rjeˇsenje. Neka je m = 11a p, n = 11b q, pri ˇcemu je a, b > 0 i brojevi p, q nisu deljivi sa 11. Dokaza´cemo da je p = q, odakle slijedi tvrdenje zadatka. Kako je (p, 11) = 1, po kineskoj teoremi o ostacima postoji prirodan broj x koji zadovoljava: x≡0

39

(mod p), x ≡ −1

Nacionalna olimpijada, Rumunija, 1978.

(mod 11).

Glava 1. Teorija brojeva

65

Ali, tada je x = 11k − 1 za neki prirodan broj k, pa je: p = (x, 11a p) = (11k − 1, m) = (11k − 1, n) = (x, 11b q) = (x, q) ≤ q. Potpuno analogno se pokaˇze da je q ≤ p, odakle slijedi p = q. 44. Ako je p prost broj ve´ci od 2, dokazati 22 · 42 · 62 · . . . · (p − 1)2 ≡ (−1)

p+1 2

(

mod p).

Uputstvo. Pogledati primjer 25. 45. Neka su a i b prirodni brojevi takvi da je (a, b) = 1, te da je ab potpun kvadrat. Dokazati da su tada a i b potpuni kvadrati. Rjeˇsenje. Neka je ab = n2 . Iz (a, b) = 1 je (a2 , n2 ) = a i (n2 , b2 ) = b, odakle zakljuˇcujemo da su a i b potpuni kvadrati. 46.

40

Dokazati da postoji beskonaˇcno mnogo brojeva m za koje vrijedi σ(k) σ(m) < za sve 1 ≤ k < m. k m

σ(n) Rjeˇsenje. Definiˇsimo niz an = . Dovoljno je dokazati da niz {an }, n nema maksimalni element. Neka je n proizvoljan prirodan broj. Za svaki njegov djelilac d vaˇzi da 2d | 2n, odavde dobijamo nejednakost σ(2n) ≥ σ(n) + 1, jer 1 | 2n. Dijeljenjem sa 2n slijedi a2n > an , prema tome niz {an } nema maksimalni element. 47. Odrediti prirodan broj n sa osobinom da je 2n kvadrat, 3n kub, a 5n peta potencija nekog prirodnog broja. Rjeˇsenje. Traˇzimo broj n tako da je n = 2k · 3l · 5m . Iz uslova zadatka dobijamo da su brojevi: k + 1, l i m djeljivi sa 2, k, l + 1 i m djeljivi sa 3 i k, l i m + 1 djeljivi sa 5. Moˇzemo uzeti npr. k = 15, l = 20 i m = 24. Dakle, jedan takav prirodan broj je 215 · 320 · 524 . 48. Dati su prirodni brojevi a i b. Pokazati 40

Prijedlog za MMO, 1983. (Belgija)

66

1.11. Zadaci (a) a2 ≡ −b2 (mod 3) ⇒ a2 ≡ −b2 (mod 9), (b) a2 ≡ −b2 (mod 7) ⇒ a2 ≡ −b2 (mod 49). Rjeˇsenje. (a) Neka je a2 + b2 ≡ 0 (mod 3). Ostaci kvadrata po modulu 3 mogu biti samo 0 ili 1, pa zbir takva dva kvadrata moˇze biti djeljiv sa 3 samo ako su a i b djeljivi sa 3. Tada je oˇcigledno a2 + b2 ≡ 0 (mod 9). (b) Radi se na isti naˇcin kao i (a).

49. Dokazati da postoji prirodan broj n takav da je za svaki prost broj p broj 2pn + 3 sloˇzen. Uputstvo. Staviti n = 4, pa razmotriti sluˇcajeve p = 5k + r, r = 1, 2, 3, 4. 50. Broj a je dobijen tako ˇsto su brojevi od 1 do 101 napisani jedan do drugog. Dokazati da je a sloˇzen broj. Da li je a kvadrat nekog prirodnog broja? Rjeˇsenje. Neka je S zbir cifara broja a. Sa D oznaˇcimo zbir cifara broja koji ˇcine brojevi ispisani od 1 do 99, a sa P zbir cifara brojeva 100 i 101. Jasno je da je P = 3. Odredimo D. Sa Sn oznaˇcimo zbir cifara dijela broja a, gdje je sa n oznaˇcena desetica kojoj odredeni niz brojeva pripada. Tada je ! 9 9 9 X X X D= Sn = i + 10n . n=0

n=0

i=1

Odavde je S0 = 45, S1 = 55, S2 = 65, S3 = 75, S4 = 85, S5 = 95, S6 = 105, S7 = 115, S8 = 125, S9 = 135, pa je S = D + P = 900 + 3 = 903. Kako 3 | 903, a 9 - 903, zakljuˇcujemo da broj a ne moˇze biti potpun kvadrat. 51. Odrediti x za koje je x2 − 3x + 2 ≡ 0 (mod 53). Rezultat. x ≡ 1 (mod 53) ili x ≡ 2 (mod 53). 52. Rijeˇsiti kongruencijske jednaˇcine (a) x2 − 3x ≡ 0 (mod 11),

Glava 1. Teorija brojeva

67

(b) x2 ≡ 4 (mod 23). Rezultat. (a) x ≡ 0 (mod 11) ili x ≡ 3 (mod 11), (b) x ≡ 2 (mod 23) ili x ≡ 21 (mod 23). ˇ 53. Sifrirati poruku STOP koriste´ci RSA kriptosistem sa javnim kljuˇcem (2537, 13). Rjeˇsenje. Prvo prevodimo poruku STOP u njen numeriˇcki ekvivalent, slovu S odgovara broj 18 (S je osamnaesto slovo engleskog alfabeta), T broj 19, O broj 14 i P broj 15. Grupisa´cemo brojeve u blokove po ˇcetiri cifre. Dobijamo, 1819 1415. Da bi ˇsifrovali svaki blok koristimo preslikavanje C = M 13

(mod 2537).

Dobijamo 2081 ≡ 181913 (mod 2537) i 2182 ≡ 141513 (mod 2537). ˇ Sifrovana poruka je 2081 2182. 54. Dobijena je ˇsifrovana poruka 0981 0461. Kako glasi deˇsifrovana poruka ako je za ˇsifriranje koriˇstena RSA ˇsifra kao u zadatku 53? Rjeˇsenje. Poruka je ˇsifrovana koriste´ci RSA kriptosistem sa n = 43 · 59 i javnim kljuˇcem e = 13. Broj, d = 937 je inverzan od 13 po modulu 42 · 58 = 2436 (ϕ(n) = 42 · 58). Koristimo 937 kao tajni kljuˇc. Da bi deˇsifrovali blok C, raˇcunamo M = C 937

(mod 2537).

Dobijamo, 0704 ≡ 0981937

(mod 2537) i 1115 ≡ 0461937

(mod 2537).

Prema tome, numeriˇcka verzija originalne poruke je 0704 1115. Odavde zakljuˇcujemo da je poruka HELP. 55. Dokaˇzite da za svaki prirodan broj n ≥ 3 postoji Pitagorina trojka ˇciji je jedan ˇclan jednak n. Rezultat. Ako je n paran stavimo x=

 n 2 2

− 1, y = n, z =

 n 2 2

+ 1.

68

1.11. Zadaci U sluˇcaju da je n neparan, x = n, y =

n2 − 1 n2 + 1 ,z = , 2 2

je Pitagorina trojka. 56. Dokazati da jednaˇcina x4 + y 8 = z 6 nema rjeˇsenja u skupu prirodnih brojeva. Uputstvo. Koristiti teoremu 1.33.

Glava 2

Binomni koeficijenti i sume 2.1

Binomna i polinomna formula

Neka je n ∈ N ∪ {0}, izraz n! naziva se faktorijel broja n i definiˇse se sa  n! =

1 · 2 · 3 · · · · · n, n ∈ N, 1, n = 0.

  n Izraz naziva se binomni koeficijent i definiˇse se kao broj k−ˇclanih k podskupova skupa sa n elemenata, to jest   n = |{A ⊂ {1, 2, . . . , n} : |A| = k}| . k Napomena 2.1. Kada skup X ima n elemenata piˇsemo |X| = n i kaˇzemo da je kardinalnost (ili veliˇcina) skupa X jednaka n. Prebrojavanjem k−toˇclanih podskupova skupa sa n elemenata uoˇcavamo da je prethodna definicija ekvivalentna sa   n n(n − 1) · · · (n − k + 1) , = k! k ako iskoristimo definiciju faktorijela imamo   n n! = . k k!(n − k)!

70

2.1. Binomna i polinomna formula

Prethodna definicija se moˇze proˇsiriti i u sluˇcaju da se ne radi o cijelim brojevima. Ako je r ∈ C onda se definiˇse     r(r − 1) · · · (r − k + 1) r , k ≥ 0, = k!  k 0, k < 0. TEOREMA 2.1. Vaˇze sljede´ce formule:     n n 1. = = 1, 0 n     n n 2. = , (simetriˇ cnost) k n−k     n n n−1 3. = , k k k−1 4.

      n+1 n n = + , (Paskalov1 identitet) k+1 k k+1

    n n+1 k+1 , 5. = · n+1 k k+1          n m n n−k n n−m+k 6. = = , m k k m−k m−k k       n n n 7. < < ··· < , 0 1 b n2 c  8.

n



b n2 c

 > ··· >

n n−1



  n > . n

Dokaz. Dokaza´cemo formule 2., 4. i 5. Dokaz ostalih je sliˇcan. Druga formula slijedi iz:     n n! n! n = = . = k k!(n − k)! (n − k)!k! n−k 1

Blaise Pascal, (1623-1662), francuski matematiˇcar.

Glava 2. Binomni koeficijenti i sume

71

Na osnovu:     n n + = k k+1

n! n! + k!(n − k)! (k + 1)!(n − k − 1)!   n! 1 1 = + k!(n − k − 1)! n − k k + 1 (n + 1)! = (n − k)!(k + 1)!   n+1 = k+1

slijedi taˇcnost ˇcetvrte formule. Kako je:   (n + 1)n! k+1 n n! = · = k!(n − k)! (k + 1)k!(n − k)! n + 1 k (n + 1)! k+1 = · (k + 1)!(n − k)! n + 1   n+1 k+1 = · , k+1 n+1 peta formula je dokazana. Varijacije bez ponavljanja Neka je S konaˇcan skup koji se sastoji od n razliˇcitih elemenata i k prirodan broj takav da 1 ≤ k ≤ n. Svaku uredenu k-torku koja se sastoji od razliˇcitih elemenata skupa S nazivamo jednom varijacijom n elemenata k-te klase. Ukupan broj razliˇcitih varijacija bez ponavljanja n elemenata k-te klase izraˇcunava se po formuli:   n n! Vnk = k! = n(n − 1) . . . (n − k + 1) = . k (n − k)! Permutacije bez ponavljanja Varijacije bez ponavljanja n elemenata n-te klase nazivamo permutacijama bez ponavljanja n elementa. Njihov ukupan broj je, prema prethodnoj formuli: Pn = n!.

72

2.1. Binomna i polinomna formula Kombinacije bez ponavljanja

Neka su n i k cijeli brojevi takvi da je 0 ≤ k ≤ n. Svaki podskup koji sadrˇzi k elemenata, konaˇcnog skupa koji se sastoji od n razliˇcitih elemenata nazivamo kombinacija bez ponavljanja n elemenata k-te klase. Broj svih kombinacija klase k od n elemenata je:   n k Cn = . k

Varijacije sa ponavljanjem Neka su n > 0 i k ≥ 0 cijeli brojevi. Ako se dati konaˇcni skup sastoji od n razliˇcitih elemenata, onda svaku uredenu k-torku koja se sastoji od njegovih elemenata nazivamo varijacija sa ponavljanjem n elemenata k-te klase. Ukupan broj varijacija sa ponavljanjem n elemenata k-te klase izraˇcunava se po formuli: k V n = nk . Permutacije sa ponavljanjem Ako se konaˇcan skup sastoji od n elemenata, pri ˇcemu je n1 elemenata prve vrste,. . ., nk elemenata k-te vrste (n1 + · · · + nk = n), onda svaku uredenu n-torku nazivano permutacija sa ponavljanjem. Njihov ukupan broj se izraˇcunava formulom: P n1 ;...;nk =

n! . n 1 ! . . . nk !

Kombinacije sa ponavljanjem Neka su n ≥ k ≥ 0 dati cijeli brojevi. Svaki podskup koji sadrˇzi k elemenata konaˇcnog skupa koji se sastoji od n razliˇcitih vrsta elemenata, pri ˇcemu sadrˇzi najmanje k elemenata svake vrste, nazivamo kombinacija bez ponavljanja n elemenata k-te klase. Broj svih kombinacija klase k od n elemenata je:   n+k−1 k Cn = . k

Glava 2. Binomni koeficijenti i sume

73

Primjer 44. Koliko rjeˇsenja ima jednaˇcina x1 + x2 + · · · + xn = k, gdje su x1 , x2 , . . . , xn nenegativni cijeli brojevi? Rjeˇsenje. Posmatrajmo skup X = {1, 2, . . . , n}. Ako pretpostavimo da za 1 ≤ i ≤ n, broj xi oznaˇcava koliko je puta izabran element i iz skupa X, onda vidimo da svako rjeˇsenje (x1 , x2 , . . . , xn ) date jednaˇcine oznaˇcava taˇcno jedan neuredeni izbor k elemenata sa ponavljanjem iz skupa sa n elemenata. Vrijedi i obrnuto: svaki neuredeni izbor k elemenata sa ponavljanjem iz skupa sa n elemenata odredjuje taˇcno jedno rjeˇsenje (x1 , x2 , . . . , xn ) date jednaˇcine. Prema tome, broj rjeˇsenja je   n+k−1 . k Nije komplikovano provjeriti da vrijede sljede´ce jednakosti (x + y)2 =x2 + 2xy + y 2 , (x + y)3 =x3 + 3x2 y + 3xy 2 + y 3 , (x + y)4 =x4 + 4x3 y + 6x2 y 2 + 4xy 3 + y 4 . Ove jednakosti su specijalan sluˇcaj opˇstije jednakosti poznate pod nazivom Njutnova2 binomna formula. TEOREMA 2.2. Za svaki prirodan broj n vrijedi jednakost  n  X n n xk y n−k , (x + y) = k

(2.1)

k=0

gdje su x, y ∈ C. Dokaz. 1. (Koristimo kombinatoriku) Zapiˇsimo izraz (x + y)n u obliku n faktora jednakih x + y i pomnoˇzimo te faktore X (x + y)n = (x + y)(x + y) · · · (x + y) = a1 a2 · · · an . Dobijamo sumu 2n sabiraka oblika a1 a2 · · · an , gdje su ai ∈ {x, y}, i = 1, . . . , n. 2

Isaac Newton (1643-1727), engleski matematiˇcar.

74

2.1. Binomna i polinomna formula

  n Za svaki k ∈ {0, 1, 2, . . . , n}, postoji taˇcno sabiraka a1 a2 · · · an , kod k kojih su k od faktora a1 , a2 , . . . , an jednaki x, a n − k faktora jednaki y. Na osnovu toga zakljuˇcujemo da vrijedi jednakost (2.1). Dokaz. 2. (Koristi´cemo metodu matematiˇcke indukcije.) Za n = 0 formula je taˇcna, jer (x + y)0 = 1 ( ako je x = y = 0 javlja se neodredeni izraz 00 , pa smatramo da je x 6= 0 ili y 6= 0). Pretpostavimo da je k   X k k−i i (x + y)k = x y za neko k ≥ 0. i i=0

Sada je k  h i X k (x + y) = (x + y) x y = xk y i + xk−1 y i+1 i i i=0 i=0 k   k−1   X k k−i+1 i X k k−i i+1 k+1 k+1 =x +y + x y + x y i i i=1 i=0       k   k + 1 k+1 k + 1 k+1 X k k = x + y + + xk−i+1 y i+1 i i−1 0 k+1 i=1       k k + 1 k+1 X k + 1 k−i+1 i k + 1 k+1 = x + x y + y 0 i k+1 i=1  k+1  X k + 1 k+1−i i = x y, i k+1

k   X k

k−i i

i=0

ˇsto je i trebalo dokazati. Primjer 45. Ako u formuli (2.1) stavimo x = 1, y = 1, a zatim x = 1, y = −1, dobijamo sljede´ce jednakosti         n n n n + + + ··· + = 2n , (2.2) 0 1 2 n         n n n n n − + − · · · + (−1) = 0. (2.3) 0 1 2 n Iz jednakosti (2.2) i (2.3) sabiranjem i oduzimanjem dobijamo             n n n n n n + + + ··· = + + + · · · = 2n−1 . 0 2 4 1 3 5

Glava 2. Binomni koeficijenti i sume

75

Primjer 46. Sumaciona formula. Koriste´ci Paskalov identitet i matematiˇcku indukciju dokazuje se    n  X m+k m+n+1 = . k n k=0

Primjer 47. Vandermondova3 konvolucija. Odreduju´ci koeficijent uz xk , (0 ≤ k ≤ min{n, m}) u razvoju polinoma (1 + x)n+m = (1 + x)n (1 + x)m , dobijamo   X  k   n+m n m = . k i k−i

(2.4)

i=0

Ako je u (2.4) n = m, koriste´ci simetriˇcnost binomnih koeficijenata, slijedi 

2n k

 =

k  2 X n i=0

i

.

(2.5)

Neka su n1 , n2 , . . . , nk nenegativni cijeli brojevi za koje vrijedi n1 + n2 + · · · + nk = n, polinomni koeficijent se definiˇse sa   n! n . = n1 , n2 , . . . , nk n1 !n2 ! · · · nk ! Ako specijalno uzmemo n1 = k i n2 = n − k dobijamo binomni koeficijent     n! n n = = . k, n − k k k!(n − k)! TEOREMA 2.3. (Polinomna formula) Neka su k i n prirodni brojevi. Tada za sve x1 , x2 , . . . , xk ∈ C vrijedi  X n n (x1 + x2 + · · · + xk ) = xn1 1 xn2 2 · · · xnk k , (2.6) n1 , n2 , . . . , nk gdje se sabiranje vrˇsi po svim k−torkama (n1 , n2 , . . . , nk ) nenegativnih cijelih brojeva za koje vaˇzi n1 + n2 + · · · + nk = n. 3

Alexandre-Thophile Vandermonde, (1735-1796), francuski matematiˇcar.

76

2.2. Gausova metoda

Dokaz. Ako izraz (x1 +x2 +· · ·+xk )n napiˇsemo u obliku proizvoda n faktora jednakih x1 + x2 + · · · + xk i pomnoˇzimo te faktore, dobi´cemo zbir koji ima k n sabiraka oblika a1 a2 . . . an , gdje su a1 , a2 , . . . , an ∈ {x1 , x2 , . . . , xk }. Neka su n1 , n2 , . . . , nk nenegativni cijeli brojevi takvi da je n1 + n2 + · · · + nk = n. Broj sabiraka oblika a1 a2 · · · an , u kojima je za svaki broj j ∈ {1, 2, . . . , k} taˇcno nj od brojeva a1 , a2 , . . . , an jednako xj , jednak je broju n-varijacija n! tipa (n1 , n2 , . . . , nk ) elemenata x1 , x2 , . . . , xk , to jest . Prema n1 !n2 ! · · · nk ! tome, dobijamo formulu (2.6). Primjer 48. Na´ci koeficijent uz x15 u razvoju (1 − x2 + x3 )20 . Rjeˇsenje. Broj 15 se moˇze predstaviti u obliku zbira sabiraka jednakih 2 ili 3 na sljede´ca tri naˇcina 2 + 2 + 2 + 2 + 2 + 2 + 3, 2 + 2 + 2 + 3 + 3 + 3, 3 + 3 + 3 + 3 + 3 + 3, pa na osnovu formule (2.6) dobijamo da je koeficijent uz x15 jednak       20 20 20 . + − 15, 0, 5 14, 3, 3 13, 6, 1

2.2

Gausova metoda

Ovdje primjenjuju´ci formulu n X

ak =

k=0

n X

an−k ,

(2.7)

k=0

raˇcunamo neke sume. Ovu ideju je koristio njemaˇcki matematiˇcar Gaus4 . Primjer 49. Aritmetiˇ cka progresija. Pretpostavimo da smo izraˇcunali sumu aritmetiˇcke progresije S=

n X (a + bk). k=0

4

Poznata je anegdota koja kaˇze da je jednom prilikom Gausov uˇcitelj zadao da se saberu svi brojevi od 1 do 100. Gaus (imao je tada 7 godina) odmah je doneo svoj rezultat: 5050. Evo kako je to rijeˇsio: Posmatraju´ci niz 1, 2, 3, 4, ..., 97, 98, 99, 100, ˇcije je ˇclanove trebalo sabrati, uoˇcio je pravilo: kada spari 1 i 100, 2 i 99, 3 i 98, i tako dalje, uvek dobije zbir 101. Takvih parova ima taˇcno 50. Otuda je traˇzeni zbir jednak 50 · 101 = 5050.

Glava 2. Binomni koeficijenti i sume

77

Primjenjuju´ci formulu (2.7) dobijamo n n X X S= (a + b(n − k)) = (a + bn − bk). k=0

k=0

Prema tome, vrijedi n n X X 2S = ((a + bk) + (a + bn − bk)) = (2a + bn), k=0

kako je

k=0

n X

(2a + bn) = (2a + bn)(n + 1),

k=0

dobijamo 2S = (2a + bn)(n + 1). Znaˇci vrijedi

n X (2a + bn)(n + 1) . (a + bk) = 2 k=0

Primjetimo da iz prethodne formule dobijamo n X

n(n + 1) . 2

(2.8)

n(n + 1)(2n + 1) . 6

(2.9)

k=

k=0

Primjer 50. Pokazati da je n X

k2 =

k=0

Rjeˇsenje. Pretpostavimo da je S2 =

n X

2

k i S1 =

k=0

n X

k.

k=0

Iz identiteta (k + 1)3 = k 3 + 3k 2 + 3k + 1, sumiranjem po k dobijamo n n n n n X X X X X 3 3 2 (k + 1) = k +3 k +3 k+ 1. k=0

k=0

k=0

k=0

k=0

78

2.2. Gausova metoda

Koriste´ci (2.8) zakljuˇcujemo da je (n + 1)3 = 3S2 + 3S1 + n + 1, a odavde dobijamo formulu (2.9) Primjer 51. Izraˇcunati

n P

k3 .

k=0

Rjeˇsenje. Ako uvedemo oznaku S3 =

n P

k 3 , primjenju´ci formulu (2.7),

k=0

dobijamo 2S3 =

n n X X [k 3 +(n−k)3 ] = (n3 −3n2 k +3nk 2 ) = (n+1)n3 −3n2 S1 +3nS2 . k=0

k=0

Iz prethodne jednakosti, koriste´ci formule (2.8) i (2.9) dobijamo   n(n + 1) 2 S3 = . 2 Primjer 52. Pokazati da je   n X n k = n2n−1 . k k=0

Rjeˇsenje. Neka je

  n X n S= k . k k=0

Iz formule (2.7) dobijamo   n    X n n 2S = k + (n − k) . k n−k k=0

    n n Kako je = , dobijamo k n−k 2S =

n X k=0

  n   X n n (k + n − k) =n . k k k=0

Kako je (Primjer 45) n   X n k=0

k

= 2n ,

Glava 2. Binomni koeficijenti i sume

79

dobijamo S = n2n−1 . Primjetimo da se zadatak moˇze rijeˇsiti i na sljede´ci naˇcin     X n−1 n n X n − 1 X n n n−1 =n = n2n−1 . k = k· k k−1 k k k=0

k=0

k=1

Primjer 53. Neka je {an } niz pozitivnih realnih brojeva. Pokazati da je n+1 X k=1

Rjeˇsenje. Oznaˇcimo sa S =

ak n+1 = . ak + an+1−k 2 n+1 P k=1

ak ak +an+1−k ,

(2.10)

primjenju´ci formulu (2.7), dobi-

jamo S=

n+1 X k=1

an+1−k . an+1−k + ak

Prema tome, 2S =

n+1 X k=1

 n+1 X an+1−k ak + = 1 = n + 1, ak + an+1−k an+1−k + ak

odakle, dobijamo S =

2.3

k=1

n+1 2 .

Metoda perturbacije

Izloˇzimo osnovnu ideju metode perturbacije. Pretpostavimo da ˇzelimo n n P P ak . Oznaˇcimo sa Sn = ak . Tada vrijedi izraˇcunati sumu k=0

k=0

Sn + an+1 = a0 +

n+1 X

ak .

k=1

Ako je sada mogu´ce sumu

n+1 P

ak izraziti preko Sn , iz gornje jednakosti do-

k=1

bijamo jednaˇcinu po Sn . Rjeˇsavanjem te jednaˇcine odredujemo Sn . Primjer 54. Geometrijska progresija. Izraˇcunati Sn =

n P k=0

metodu perturbacije.

xk koriste´ci

80

2.3. Metoda perturbacije

Rjeˇsenje. Vrijedi n+1

Sn + x

=1+

n+1 X

xk .

k=1

Kako je n+1 X

xk = xSn ,

k=1

iz dobijene jednakosti imamo Sn + xn+1 = 1 + xSn . Rjeˇsavaju´ci posljednju jednaˇcinu po Sn dobijamo n X

1 − xn+1 , za x 6= 1. 1−x

xk =

k=0

n P

Primjer 55. Izraˇcunati sumu Sn =

kxk .

k=0

Rjeˇsenje. Vrijedi Sn + (n + 1)xn+1 =

n+1 X

kxk =

k=0 n+1 X

kxk =

k=1

n X

(k + 1)xk+1 = x

k=0

n X

kxk +

k=0

n+1 X

kxk ,

k=1 n X

xk+1 = xSn +

k=0

x(1 − xn+1 ) . 1−x

Prema tome, x(1 − xn+1 ) . 1−x Rjeˇsavaju´ci posljednju jednaˇcinu po Sn dobijamo Sn + (n + 1)xn+1 = xSn +

Sn =

x − (n + 1)xn+1 + nxn+2 , za x 6= 1. (1 − x)2

Primjer 56. Izraˇcunati

n P

(−1)k .

k=0

Rjeˇsenje. Oznaˇcimo sa Sn =

n P

(−1)k i primjenimo metod perturbacije.

k=0

Imamo sljede´ce n+1

Sn + (−1)

=

n+1 X

k

0

(−1) = (−1) +

k=0

n+1 X

n X (−1) = 1 + (−1)k+1 = 1 − Sn ,

k=1

k

k=0

Glava 2. Binomni koeficijenti i sume

81

pa Sn = Primjer 57. Izraˇcunati

n P

1 + (−1)n . 2

(−1)k k.

k=0

Rjeˇsenje. Uvedimo oznaku Tn =

n P

(−1)k k. Vrijedi

k=0

Tn + (−1)n+1 (n + 1) =

n+1 X

n X

k=1

k=0

(−1)k k =

(−1)k+1 (k + 1) = −Tn − Sn ,

pa koriste´ci prethodni primjer dobijamo Tn =

2.4

(−1)n (2n + 1) − 1 . 4

Beskonaˇ cne sume

Beskonaˇcna suma ima oblik a0 + a1 + a2 + · · · =

+∞ X

ak .

k=0

Ako su brojevi ak nenegativni i postoji konstanta A takva da je n X

ak ≤ A, za svaki n ∈ N,

k=0

tada postoji konstanta S takva da je S=

+∞ X

ak

k=0

i pri tome je S = lim Sn , n→+∞

gdje je Sn =

n P

ak . Ovu ˇcinjenicu (dokazuje se u kursu Matematiˇcka analiza

k=0

1) koristimo da odredimo neke beskonaˇcne sume.

82

2.4. Beskonaˇ cne sume

Primjer 58. Pokazati da je +∞ X k=1

1 = 1. k(k + 1)

Rjeˇsenje. Vrijedi n X k=1

        1 1 1 1 1 1 1 1 = 1− + − + − + ··· + − k(k + 1) 2 2 3 2 3 n n+1 =1 −

1 , n+1

pa je +∞ X k=1

  1 1 = lim 1− = 1. k(k + 1) n→+∞ n+1

Primjer 59. Izraˇcunati +∞ X k . 2k k=1

Rjeˇsenje. Odredimo prvo Sn =

n X k , 2k k=1

koriste´ci metodu perturbacije. Imamo Sn +

n+1

n+1

n

k=1

k=2

k=1

n+1 X k 1 X k 1 X (k + 1) = = + = + . n+1 k k 2 2 2 2 2 2k+1

Kako je n X (k + 1) k=1

2k+1

n

=

Sn X 1 Sn 1 1 − 21n + = + · , 2 2 22 1 − 21 2k+1 k=1

dobijamo Sn = 2 −

1 2n−1

−

pa zakljuˇcujemo da vrijedi +∞ X k = 2. 2k k=1

n , 2n

Glava 2. Binomni koeficijenti i sume

83

Koriste´ci sliˇcnu metodu moˇze se pokazati da je +∞ 2 X k k=1

Primjer 60. (Bazelski

2k

=6i

+∞ 3 X k k=1

problem5 )

2k

= 26.

Pokazati da je

+∞ X 1 π2 = . k2 6

(2.11)

k=1

Rjeˇsenje. Dokaza´cemo (2.11) koriste´ci Ojlerovu metodu6 . Koriste´ci Tejlorov razvoj imamo x3 x5 x7 sin x = x − + − + ··· , 3! 5! 7! stavljaju´ci x2 x4 x6 p(x) = 1 − + − + ··· , (2.12) 3! 5! 7! dobijamo sin x = xp(x). Nule funkcije sin x razliˇcite od nule su ±kπ za k = 1, 2, . . . . Na osnovu ovoga zakljuˇcujemo da je  x  x  x  x p(x) = 1 − 1+ 1− 1+ ··· π π 2π 2π     x2 x2 x2 = 1− 2 1− 2 1 − 2 ··· . π 4π 9π

(2.13)

Iz (2.12) i (2.13) dobijamo x2 x4 x6 1− + − + ··· = 3! 5! 7!

    x2 x2 x2 1− 2 1− 2 1 − 2 ··· . π 4π 9π

(2.14)

Ako u relaciji (2.14) uporedimo koeficijente uz x2 dobijamo   1 1 1 1 − =− + + + ··· 3! π 2 4π 2 9π 2 odakle se dobija jednakost (2.11). 5

Bazelski problem je poznati problem iz matematiˇcke analize koji je u vezi sa teorijom brojeva. Postavio ga je Pietro Mengoli (1626-1686), italijanski matematiˇcar, 1644. godine, a rijeˇsio ga je Leonhard Euler 1735. god. Dobio je ime po gradu Bazelu iz koga je bio Jakov Bernuli koji nije znao da ga rijeˇsi. 6 Detaljnije se moˇze vidjeti npr. u radu: C. J. Sangwin, An infinite series of surprises, +Plus Magazine, University of Cambridge, 2002.

84

2.4. Beskonaˇ cne sume Ojler je koriste´ci ovu metodu dobio i +∞ X 1 π4 = , k4 90 k=1

+∞ +∞ X X π6 224 76977927π 26 1 1 = , kao i = . k6 945 k 26 27! k=1

k=1

Primjer 61. Pokazati da je +∞ X k=1

π2 1 = . (2k − 1)2 8

(2.15)

Rjeˇsenje. Koristimo Ojlerovu metodu. Za funkciju cos x vrijedi cos x = 1 −

x2 x4 x6 + − + ··· . 2! 4! 6!

(2.16)

S druge strane nule funkcije cos x su ± (2k−1)π , k = 1, 2, . . . . Prema tome, 2 vrijedi        2x 2x 2x 2x 2x 2x cos x = 1 − 1+ 1− 1+ 1− 1+ ··· π π 3π 3π 5π 5π     4x2 4x2 4x2 1− 2 2 1 − 2 2 ··· . = 1− 2 π 3 π 5 π (2.17) Iz (2.16) i (2.17) dobijamo 1−

x2 x4 x6 + − + ··· = 2! 4! 6!

    4x2 4x2 4x2 1− 2 1− 2 2 1 − 2 2 ··· , π 3 π 5 π

a odavde uporeduju´ci koeficijent uz x2 dobijamo −

1 4 4 4 = − 2 − 2 2 − 2 2 − ··· , 2! π 3 π 5 π

odakle slijedi (2.15). Napomena 2.2. Primjetimo, da se suma reciproˇcnih vrijednosti kvadrata moˇze rastaviti na sumu reciproˇcnih vrijednosti parnih i sumu neparnih. Suma parnih je ˇcetvrtina sume svih, pa je suma neparnih 3/4 sume svih reciproˇcnih vrijednosti kvadrata.

Glava 2. Binomni koeficijenti i sume

2.5

85

Primjena izvoda i integrala

Pretpostavimo da je S(x) =

+∞ X

ak xk ,

k=0

tada vrijedi 1. Pravilo izvoda, S 0 (x) =

+∞ X

kak xk−1 =

k=1

+∞ X

(k + 1)ak+1 xk ,

k=0

2. Pravilo integrala, Zx S(t)dt = 0

+∞ X k=0

ak

xk+1 , k+1

za sve x za koje dati redovi na desnim stranama konvergiraju. Ova pravila, u nekim sluˇcajevima, mogu posluˇziti da se izraˇcunaju odredene sume. Ilustrova´cemo to na nekoliko primjera. Primjer 62. Izraˇcunati         1 n n n 1 n n 1 + − · · · + (−1) . − 2 1 3 2 n+1 n 0 Rjeˇsenje. Iz binomne formule         n n n 2 n n n (1 − x) = − x+ x − · · · + (−1) xn , 0 1 2 n koriste´ci pravilo integrala dobijamo (1 − x)n+1 1 − + = n+1 n+1         n 1 n 2 1 n 3 n n+1 n 1 x− x + x − · · · + (−1) x . 0 2 1 3 2 n+1 n Odavde, za x = 1, dobijamo da je         n 1 n 1 n 1 n 1 − + − · · · + (−1)n = . 2 1 3 2 n+1 n n+1 0

86

2.6. Princip ukljuˇ cenja-iskljuˇ cenja

Primjer 63. Izraˇcunati

n P

k2k .

k=0

Rjeˇsenje. Iz n X

xk =

k=0

1 − xn+1 , 1−x

koriste´ci pravilo izvoda, dobijamo n X

kxk−1 =

k=0

1 − (n + 1)xn + nxn+1 , (1 − x)2

ako sada stavimo x = 2, dobijamo

n P

k2k = (n − 1)2n + 1. Dakle,

k=0 n X

k2k = (n − 1)2n+1 + 2.

k=0

Napomena 2.3. Prethodni primjer se moˇze rijeˇsiti koriste´ci, metodu perturbacije (primjer 55). Primjer 64. Pokazati da je +∞ X (−1)k−1 k=1

2k − 1

=

π . 4

(2.18)

Rjeˇsenje. Iz +∞

X 1 = (−1)k x2k , 1 + x2 k=0

koriste´ci pravilo integrala imamo +∞ +∞ 2k+1 X X x2k−1 k x = (−1)k−1 . arctan x = (−1) 2k + 1 2k − 1 k=0

k=1

Ako u posljednjoj jednakosti stavimo x = 1 dobijamo (2.18).

2.6

Princip ukljuˇ cenja-iskljuˇ cenja

Sljede´ca teorema je poznata kao princip ukljuˇcenja-iskljuˇcenja. Koristi se osim u kombinatorici i u teoriji vjerovatno´ce.

Glava 2. Binomni koeficijenti i sume

87

TEOREMA 2.4. Za konaˇcne skupove A1 , A2 , . . . , An vaˇzi n n [ X X X |Ai ∩ Aj | + |Ai ∩ Aj ∩ Ak | − · · · |Ai | − Ai = i=1

i=1

1≤i