Rastavljanje na proste činioce

Svaki složen broj može se zapisati kao proizvod prostih brojeva. Na primer, broj $12$ možemo napisati kao $2 \cdot 2 \cdot 3$ , a broj $30$ kao $2 \cdot 3 \cdot 5$ . Ovakav zapis naziva se rastavljanje na proste činioce.

Sadržaj

Osnovni pojmovi
1. Primeri

Osnovni pojmovi

Prost i složen broj. Prirodan broj veći od $1$ je prost ako ima tačno dva delioca, $1$ i samog sebe (na primer $2, 3, 5, 7, 11$ ). Ako ima i drugih delilaca, broj je složen. Broj $1$ nije ni prost ni složen.

Svaki prirodan broj $n > 1$ može se rastaviti na proizvod prostih brojeva, i to na jedinstven način (do redosleda činilaca). Kada jednake proste činioce grupišemo u stepene, rastavljanje na proste činioce zapisujemo ovako:

$n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}$

gde su $p_1, p_2, \dots, p_k$ različiti prosti brojevi, a $a_1, a_2, \dots, a_k$ prirodni izložioci. Na primer, $360 = 2^3 \cdot 3^2 \cdot 5$ .

Broj rastavljamo tako što ga redom delimo najmanjim prostim brojem koji ga deli, pa količnik ponovo delimo, sve dok ne dođemo do $1$ . Prosti brojevi kojima smo delili, poređani po veličini, čine rastavljanje.

Zadatak. Rastaviti broj $504$ na proste činioce.

Rešenje.

Delimo redom najmanjim prostim brojem koji deli tekući broj, sve do $1$ . U levoj koloni je broj, u desnoj delilac:

Broj	Delilac
504	2
252	2
126	2
63	3
21	3
7	7
1

Prosti činioci su brojevi iz desne kolone; jednake grupišemo u stepene:

$504 = 2^3 \cdot 3^2 \cdot 7$

Da proveriš da li je neki broj $N$ prost, dovoljno je da ga probaš podeliti prostim brojevima do $\sqrt{N}$ . Ako nijedan ne deli $N$ , broj je prost. Na primer, za $73$ je $\sqrt{73} \approx 8{,}5$ , pa proveravaš samo $2, 3, 5$ i $7$ ; nijedan ne deli $73$ , pa je $73$ prost.

1. Primeri

Sledeći tipovi zadataka pokazuju kako se rastavljanje na proste činioce i osobine prostih brojeva koriste u praksi. Za svaki tip prvo je opisano šta se traži, a zatim kako se do rešenja dolazi.

1.1. Potpun kvadrat i potpun kub

Ovde se pitamo da li je broj potpun kvadrat ili potpun kub, ili kojim najmanjim brojem ga treba pomnožiti da to postane. Na primer: kojim najmanjim prirodnim brojem treba pomnožiti $150$ da bismo dobili potpun kvadrat?

Odgovor se čita iz izložilaca u rastavljanju na proste činioce.

Broj je potpun kvadrat ako i samo ako su svi izložioci u njegovom rastavljanju na proste činioce parni.

Broj je potpun kub ako i samo ako su svi izložioci deljivi sa $3$ .

Kada tražimo najmanji množilac, svaki izložilac dopunjujemo do prvog sledećeg parnog broja (za kvadrat), odnosno do prvog sledećeg umnoška broja $3$ (za kub).

Zadatak. Naći najmanji prirodan broj kojim treba pomnožiti $150$ da se dobije potpun kvadrat.

Rešenje.

Rastavljamo $150$ na proste činioce:

$150 = 2^1 \cdot 3^1 \cdot 5^2$

Izložioci činilaca $2$ i $3$ su neparni, a izložilac činioca $5$ je već paran. Da bi svi izložioci postali parni, dopunjujemo izložioce činilaca $2$ i $3$ za po $1$ :

$n = 2^1 \cdot 3^1 = 6$

Provera potvrđuje rezultat:

$150 \cdot 6 = 900 = 30^2$

Kod potpunog kuba cilj je da svaki izložilac postane deljiv sa $3$ . Sledeća tabela pokazuje dopunu za isti broj $150 = 2^1 \cdot 3^1 \cdot 5^2$ .

Činilac	Sada	Cilj	Dodati
2	1	3	2²
3	1	3	3²
5	2	3	5¹

Zadatak. Naći najmanji prirodan broj kojim treba pomnožiti $150$ da se dobije potpun kub.

Rešenje.

Iz tabele čitamo dopunu izložilaca:

$x = 2^2 \cdot 3^2 \cdot 5^1 = 4 \cdot 9 \cdot 5 = 180$

Provera:

$150 \cdot 180 = 27000 = 30^3$

1.2. Uzastopni brojevi iz proizvoda

Poznat je proizvod nekoliko uzastopnih brojeva, a traže se sami ti brojevi. Na primer: proizvod tri uzastopna cela broja je $504$ ; koji su to brojevi?

Umesto rešavanja jednačine visokog stepena, rastavimo dati proizvod na proste činioce, a zatim te činioce grupišemo u uzastopne brojeve.

Zadatak. Proizvod tri uzastopna cela broja je $504$ . Koji su to brojevi?

Rešenje.

Neka su brojevi $n-1$ , $n$ i $n+1$ , pa je:

$(n-1)\, n \,(n+1) = 504$

Pošto je proizvod pozitivan, a brojevi uzastopni, sva tri su pozitivna. Rastavljamo $504$ na proste činioce:

$504 = 2^3 \cdot 3^2 \cdot 7$

Prosti činilac $7$ mora „pripasti" jednom od tri broja. Preostale činioce grupišemo u vrednosti bliske broju $7$ :

$2^3 = 8, \qquad 3^2 = 9$

Dobijamo brojeve $7, 8, 9$ . Provera:

$7 \cdot 8 \cdot 9 = 504$

Traženi brojevi su $7$ , $8$ i $9$ .

Zadatak. Proizvod četiri uzastopna prirodna broja je $3024$ . Koji su to brojevi?

Rešenje.

Rastavljamo broj na proste činioce:

$3024 = 2^4 \cdot 3^3 \cdot 7$

Zbog činioca $7$ , jedan od brojeva je deljiv sa $7$ . Kako je $\sqrt[4]{3024} \approx 7{,}4$ , brojevi su jednocifreni, pa taj umnožak broja $7$ mora biti tačno $7$ . Time ostaju samo mogući skupovi:

$\{4,5,6,7\}, \quad \{5,6,7,8\}, \quad \{6,7,8,9\}, \quad \{7,8,9,10\}$

Broj $3024$ nije deljiv sa $5$ (ne završava se na $0$ ni $5$ ), pa nijedan od traženih brojeva ne sme biti deljiv sa $5$ . Time otpadaju svi skupovi koji sadrže $5$ ili $10$ , a ostaje jedino $\{6,7,8,9\}$ . Provera preostalih činilaca:

$6 \cdot 8 \cdot 9 = 2^4 \cdot 3^3 = 432$

što se poklapa sa preostalim prostim činiocima (bez sedmice). Traženi brojevi su $6, 7, 8, 9$ .

1.3. Kvadrat prostog broja pri deljenju sa 3

Zadatak. Neka je $p$ prost broj, $p > 3$ . Odrediti ostatak koji $p^2$ daje pri deljenju sa $3$ .

Rešenje.

Pošto je $p$ prost i veći od $3$ , nije deljiv sa $3$ , pa je oblika $p = 3k + 1$ ili $p = 3k + 2$ . Oba oblika obuhvatamo zapisom $p = 3k \pm 1$ .

Kvadriramo:

$p^2 = (3k \pm 1)^2 = 9k^2 \pm 6k + 1$

Iz prva dva člana izvlačimo $3$ :

$p^2 = 3(3k^2 \pm 2k) + 1$

Izraz u zagradi je ceo broj, pa je $p^2 = 3m + 1$ . Ostatak je $1$ .

Ovu činjenicu, $p^2 = 3m + 1$ , sada koristimo u dokazima deljivosti.

Zadatak. Neka je $p$ prost broj, $p > 3$ . Dokazati da je $8p^2 + 1$ deljivo sa $3$ .

Rešenje.

Pošto je $p > 3$ prost, važi $p^2 = 3m + 1$ za neki ceo broj $m$ . Zamenjujemo:

$8p^2 + 1 = 8(3m + 1) + 1 = 24m + 9$

Izvlačimo $3$ :

$24m + 9 = 3(8m + 3)$

Kako je $8m + 3$ ceo broj, izraz je deljiv sa $3$ . $\blacksquare$

1.4. Parnost i prosti brojevi

Kada se traže prosti brojevi koji zadovoljavaju neku jednačinu, ili se dokazuje da je izraz sa prostim brojem složen, često pomaže parnost. Na primer: naći sve proste brojeve $p$ i $q$ za koje je $3p + 2q = 52$ .

Ključ je da je $2$ jedini paran prost broj; svi ostali prosti brojevi su neparni. Analizom parnosti neku nepoznatu prisilimo da bude baš $2$ .

Zadatak. Odrediti sve proste brojeve $p$ i $q$ za koje važi $3p + 2q = 52$ .

Rešenje.

Izražavamo $3p$ i izvlačimo $2$ na desnoj strani:

$3p = 52 - 2q = 2(26 - q)$

Desna strana je parna, pa je i $3p$ parno. Kako je $3$ neparno, mora $p$ biti parno, a jedini paran prost broj je $2$ :

$p = 2$

Zamenom nalazimo $q$ :

$3 \cdot 2 + 2q = 52 \implies 2q = 46 \implies q = 23$

Broj $23$ je prost, pa je rešenje $(p, q) = (2, 23)$ .

Isti pristup radi i sa više nepoznatih; parnost tada može uzastopno da fiksira dve vrednosti.

Zadatak. Odrediti proste brojeve $p$ , $q$ i $r$ takve da je $2p + 3q + 4r = 302$ .

Rešenje.

Članovi $2p$ , $4r$ i $302$ su parni, pa iz jednačine sledi da je i $3q$ parno:

$3q = 302 - 2p - 4r = 2(151 - p - 2r)$

Kako je $3$ neparno, $q$ mora biti parno, dakle $q = 2$ . Zamenom i deljenjem sa $2$ :

$2p + 4r = 296 \implies p + 2r = 148$

Ponovo je $p = 148 - 2r = 2(74 - r)$ parno, pa je $p = 2$ . Odatle:

$2 + 2r = 148 \implies r = 73$

Broj $73$ je prost, pa je rešenje $(p, q, r) = (2, 2, 73)$ .

Parnost pomaže i u dokazima da je neki izraz sa prostim brojem složen.

Zadatak. Neka je $p$ prost broj. Dokazati da je $37 + p$ složen.

Rešenje.

Razmatramo dva slučaja.

Slučaj 1: $p = 2$ . Tada je:

$37 + 2 = 39 = 3 \cdot 13$

Broj ima delioce različite od $1$ i sebe, pa je složen.

Slučaj 2: $p > 2$ . Tada je $p$ neparno, a zbir dva neparna broja je paran:

$37 + p = 37 + (2k + 1) = 2(19 + k)$

Ovaj broj je deljiv sa $2$ i veći od $2$ , pa je složen.

Pošto je u oba slučaja $37 + p$ složen, tvrđenje je dokazano. $\blacksquare$

U zadacima gde se traže konkretni prosti brojevi lako se zaboravi poslednja provera: dobijenu vrednost treba potvrditi kao prost broj (na primer $23$ ili $73$ ), jer bez toga rešenje nije potpuno.

Rastavljanje na proste činioce

Sadržaj

Osnovni pojmovi

1. Primeri

1.1. Potpun kvadrat i potpun kub

1.2. Uzastopni brojevi iz proizvoda

1.3. Kvadrat prostog broja pri deljenju sa 3

1.4. Parnost i prosti brojevi

Lekcije iz iste oblasti

Deljivost celih brojeva

NZS i NZD

Pozicioni zapis celog broja

Zadaci za vežbanje