Osnovna teorema aritmetike

Iz Vikipedije, slobodne enciklopedije
Idi na navigaciju Idi na pretragu

Osnovna teorema aritmetike ili „teorema o jedinstvenoj faktorizaciji” jeste tvrđenje da svaki prirodan broj veći od 1 je ili prost broj ili se može na jedinstven način predstaviti kao proizvod prostih brojeva, do nivoa redosleda činilaca. Na primer

1200 = 24 × 31 × 52 = 3 × 2 × 2 × 2 × 2 × 5 × 5 = 5 × 2 × 3 × 2 × 5 × 2 × 2 = itd.

odnosno, prvo je značajno da se broj 1200 može predstaviti kao proizvod prostih brojeva, i drugo to su uvek isključivo četiri dvojke, jedna trojka i dve petice (eventualno u drugačijem rasporedu).

Svaki prirodan broj je moguće napisati kao , gde je — prost broj, pri čemu je takva prezentacija tačna do redosleda činilaca.
gde su — prosti brojevi, i — prirodni brojevi.

Važno je primetiti da se broj 1 ne tretira kao prost broj, jer faktorizacija više ne bi bila jednoznačna, kao kod 2 = 2×1 = 2×1×1 = ...

Osnovna teorema[uredi]

Prosti brojevi, odnosno prim-brojevi su oni koji imaju samo dva tačna delioca: jedinicu i samog sebe. To je slučaj sa 2, 3, 5, 7, 11, 13,17, 19, 23, .... Po konvenciji smatra se da 1 nije prost broj. Prostih brojeva ima beskonačno mnogo, ali što dalje napredujemo u skupu prirodnih brojeva, to ih sve ređe nalazimo: između 1 i 10 imamo 4 prosta broja, što čini 40%; između 1 i 100 ima 25 prostih brojeva, tj. 25%; između 1 i 1000 ima ih 144, dakle 14,4%; ...; između 1 i milijardu (109), ima ih 48 254 942, tj. manje od 4,8%. Upravo oni, prosti brojevi, su i najveća zagonetka aritmetike. U to se možemo uveriti na svakom koraku.

Primer
Prosti brojevi su blizanci ako im je razlika dva (blizanci su 3 i 5, ili 4001 i 4003). Pitanje bez odgovora u današnjoj matematici je: ima li blizanaca beskonačno ili ne?

Ipak, još pre par hiljada godina Euklid je dokazao osnovno pravilo aritmetike: svaki prirodan broj je ili prost broj ili je proizvod prostih brojeva. U savremenoj formulaciji osnovni stav aritmetike glasi: svaki prirodan broj može se predstaviti u obliku proizvoda prostih faktora i i njegovo predstavljanje je jedinstveno do poretka faktora. To će biti rečeno još preciznije u teoremi 2, u nizu od tri naredne teoreme.

Faktori[uredi]

Teorema 1
Ako je n prirodan broj, onda je n proizvod prostih faktora.
Dokaz
Za prost broj n tvrđenje važi očigledno, on je proizvod jedinice i samog sebe. Tvrđenje svakako važi za brojeve n = 1, 2, 3 i možda za još neke. Pretpostavimo da tvrđenje važi za sve složene brojeve manje od n. Ako je i broj n složen broj, tada postoji ceo broj c takav da je 1<c<n, c|n (ovo poslednje čitamo "c deli n", što znači da je broj n deljiv brojem c). Označimo sa m najmanji od pomenutih brojeva c. Takav m ne može biti složen broj, jer bi tada postojao ceo broj k, takav da je 1<k<m, k|m, što bi značilo i k|n. Međutim, to je kontradikcija sa pretpostavkom da je m najmanji prirodan broj koji je delitelj od n. Dakle, broj m je prost broj. Označimo ga sa p1. Tada mora biti n=p1n1, gde je 1<n1<n. Matematička indukcija će dalje dati da se i broj n1 može zatim faktorisati. Prema tome, može se faktorisati i polazni broj n. Kraj dokaza.
Primer 1
U samoposluzi se jaja prodaju u pakovanjima od po dvanaest jaja. Svako od tih pakovanja možemo raspakovati u po tri manja paketa sa po četiri jajeta, zato što je broj 12 deljiv sa 3 i sa 4, tako da je 3h4=12.
Primer 2
Da bismo rastavili neki broj na proste činioce postupno ćemo proveravati da li je deljiv sa dva, sa tri, sa pet, i redom sa prostim brojevima. Za to možemo koristiti kriterijume deljivosti. Recimo, 156=2h78=2h2h39=2h2h3h13. Dakle, 2, 2, 3, 13 su prosti brojevi, faktori broja 156.
Kriterijumi deljivosti
broj je deljiv sa 2 ako se završava sa nulom ili parnom cifrom;
deljiv je sa 3, ako je zbir cifara deljiv sa 3;
sa 5 ako se završava nulom ili peticom;
broj je deljiv sa 11 ako je zbir cifara tog broja na neparnim pozicijama oduzet od zbira njegovih cifara na parnim pozicijama jednak nuli ili je deljiv sa 11.

Kanonski oblik[uredi]

Grupišući jednake proste faktore broja n, onda se prirodan broj može predstaviti u obliku

gde je Takvo predstavljanje nazivamo kanonski oblik broja n.
Teorema 2
Svaki prirodan broj ima jedinstven kanonski oblik.
Dokaz
Na osnovu teoreme 1 kanonsko predstavljanje postoji, a kanonski oblik prostog broja je, očigledno, jedinstven. Za ostale brojeve, dokaz izvodimo svođenjem na kontradikciju. Pretpostavimo da postoji prirodan broj koji se može predstaviti u kanonskom obliku na dva različita načina. Neka je n najmanji takav broj Nijedan od brojeva p ne može se pojaviti u obe kanonske reprezentacije broja n zbog pretpostavke o minimalnosti n. Brojeve je uvek moguće poredati po veličini i recimo Za proste faktore i važi pa možemo uzeti da je Neka je Iz sledi gde je Dakle broj n-u može se napisati u obliku gde su prosti brojevi, za Međutim, iz povlači rastavljanje na proste faktore, na primer pa sledi drugačiji zapis broja gde nema prostog faktora To proizilazi iz i sa druge strane jer nije delitelj od Dakle broj n-u ima dve različite faktorizacije, jer samo jedna od njih sadrži prost faktor To važi i u slučaju kada je Međutim, a to je u kontradikciji sa pretpostavkom o minimalnosti broja n. Dakle, ne postoji ceo broj veći od 1 koji se može na dva načina predstaviti u kanonskom obliku. Kraj dokaza.


To je osnovna teorema aritmetike. Postoji mnogo različitih dokaza ove teoreme i nijedan nije trivijalan, jer se na kraju oslanja na posebnosti skupa prirodnih brojeva u odnosu, recimo na njegove zatvorene podskupove. Na primer, skup parnih brojeva je podskup skupa svih prirodnih brojeva N i takođe je zatvoren na operacije sabiranja i množenja, kao i N. Parni brojevi koji pri deljenju sa 4 daju ostatak 2, to su brojevi oblika 4k+2, nazivaju se parno-prosti. Svaki paran broj može se predstaviti u obliku proizvoda parno-prostih brojeva. Međutim, razlaganje na parno-proste faktore nije uvek jedinstveno. Broj 360 može se faktorisati na parno-proste brojeve na više načina: 2x2x90=2x6x30=2x10=6x6x10.

Reprezentacije[uredi]

Teorema 3
Neka su brojevi c i n dati u kanonskom obliku
Tada je ako i samo ako je za
Dokaz
Sledi iz gde je Kraj dokaza.

Vidi još[uredi]