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.

  1. Broj 1
  2. Prosti brojevi
  3. 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.