Djeljivost brojeva
Sa Wikipedije, slobodne enciklopedije
Za prirodni broj a kažemo da je djeljiv sa prirodnim brojem.. b ( pišemo a : b) onda i samo onda ako postoji prirodni broj c takav da je a = bc. Broj b je mjera (divizior, djelitelj) broja a koji je višekratnik (multiplum) broja b.
Primjer
Za 15 : 3 postoji broj 5 takav da je 15 = 5 x 3.
Sadržaj |
[uredi] Prosti i složeni brojevi
prirodni broj veći od 1 djeljiv samim sobom i brojem 1 zove se prost broj.prosti brojevi veći od 1 koji nisu prosti su složeni.
Primjer
Prosti brojevi su 2, 3 ..., a složeni 4,6,...
Iz navedenog se vidi da su prirodni brojevi podijeljeni u tri klase.
- Broj 1
- Prosti brojevi
- Složeni brojevi
U skupu brojeva broj 1 ima poseban položaj, zato je izdvojen u posebnu klasu.
Djeljivost u skupu N može se proširiti na skup N0 i reći da je 0 djeljiva sa svakim prirodnim broj, jer je 0 = a x 0. broj 0 nije ni prost ni složen broj.
[uredi] Teorema 1
Ako je prirodni broj a djeljiv sa brojem c onda je svaki višekratnik od a djeljiv sa b.
Dokaz a = bc => an =b(cn).
[uredi] Teorema 2
Da bi suma (a + b) bila djeljiva sa c dovoljno je da svaki od brojeva a, b bude djeljiv sa c.
Dokaz
Ako je a = cm i b = cn (a + b) = cm + cn = c (m + n).
[uredi] Teorema 3
Da bi suma ( a + b) ,u kojoj je prvi broj djeljiv sa c, bila djeljiva sa c potrebno je da idrugi broj bude djeljiv sa c.
Dokaz a =cm, i (a + b ) = cn imamo cm + b = cn => cn – cn = b => b =c(m – n) .
[uredi] Teorema 4
Svaki prirodni broj djeljiv je sa bar jednim prostim brojem.
Dokaz
Za n > 1 Ako je n prost broj djeljiv je samim sobom, a ako je složen među njegovim djeljiteljima postoji najmanji. Označimo ga sa p. On mora biti prost broj, jer ako bi bio složen. Bilo bi p =km(k,m > 1). a= pq ili a = k (mq). U ovom slučaju p nebi bio najmanji prost broj kojim je a djeljiv, k bi bio manji.
[uredi] Teorema 5
Svaki složen broj možemo napisati kao proizvod složenih brojeva.
Dokaz
Neka je p1 najmanji prost broj, kojim je n djeljivo. Za q1 = n p1 imamo n = p1 q1. Ako je q1 složen , a p2 prost imamo q1 = p1 p2 q2 . ovaj postupak možemo nastaviti dok ne dođemo do oblika n = p1 p2... pn, a kako je n > p1 >q1 >q2 >... jednom ćemo doći do qn koji je prost broj.
Primjer
3224 = 2 x 3 x 7 x 7 x 11.
[uredi] Teorema 6
Prostih brojeva ima beskonačno mnogo
Dokaz Ako ih ima konačno mnogo onda postoji jedan koji je najveći. Označimo ga sa p. Posmatrajmo broj 1 x 2 x 3 x ..... x p + 1 . On je veći od svakog prostog broja i kao takav ne može biti prost. Nije djeljiv ni sa jednim prostim brojem ( pri dijeljenju uvijek ostane ostatak 1). Ovo znači da je ovaj skup beskonačan.
Ako u ovom skupu idemo ka većim brojevima prosti brojevi su sve rjeđi.
između brojeva 1 i 50 | između |
između 1 i 100 | ma 10 prostih brojeva |
između 10 i 1000 | ima 68 prostih brojev |
između 1000 i 2000 | ima 135 prostih brojeva |
[uredi] Teorema 7
Postoji po volji beskončno mnogo složenih brojeva.
Posmatrajmo broj 1 x 2 x3 x ..... x n = n! I brojeve 2 + n! 3 + n!..... Oni su djeljivi redom sa 2,3....
Primjer n = 5
2 + 5! =122 3 + 5! = 123 4 +5! = 124 5 + 5! = 125
[uredi] Eratestenovo sito
Ovo je mehanički postupak pronalaženja prostih brojeva koji nisu veći od n. Ispižemo sve brojeve od 2 do n. Pođemo od broja 2 i precrtavamo svaki drugi broj, zatim pođemo od broja 3 i precrtavamo svaki treći stim da brojimo i precrtane brojeve, pa od prvog neprecrtanog broja itd. Ovaj postupak ponavljamo dok ne dođemo do broja p za koje je p2 > n. Neprecrtani brojevi su prosti.
Primjer n =21
2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
Prosti brojevi su 2,3,5. 7, 11,13,17,19.