kako da rastaviš broj na proste činioce, primeniš Euklidov algoritam i čitaš kongruenciju kao jednakost ostataka.
Matoteka · Centar znanja · Lekcija 6
Deljivost celih brojeva kongruencije i Euklidov algoritam
Ova lekcija pretvara ostatke pri deljenju u ozbiljan alat. Učiš kako da razdvojiš proste i složene brojeve, kako da brzo nađeš NZD i NZS, i kako da modularno razmišljaš kada tražiš poslednju cifru ili ispituješ ostatke.
mešanje delioca i sadržalaca, kao i prerano zaustavljanje Euklidovog algoritma pre poslednjeg nenultog ostatka.
zadaci sa NZD/NZS, ostacima pri deljenju i poslednjom cifrom velikog stepena broja.
45 do 60 minuta pažljivog rada
osnovne operacije sa celim brojevima i siguran rad sa brojevnim izrazima
traženje NZD i NZS, čitanje ostataka i prepoznavanje perioda u modularnim zadacima
canvas simulator Euklidovog algoritma sa kongruencijama po zadatom modulu
Brza navigacija
Kretanje kroz lekciju
Najstabilniji redosled je: zašto ova tema postoji, kako se nalazi modul i argument, kako se prelazi između oblika, pa tek onda Moivreova formula i koreni.
1. Zašto je ova lekcija važna
Teorija brojeva trenira preciznost koja se kasnije traži svuda
Deljivost izgleda elementarno, ali upravo ovde se uči disciplina rada sa ostatkom, faktorima i redom koraka. To je osnova za zadatke sa poslednjom cifrom, parametarskim uslovima i svim situacijama gde moraš da zaključiš nešto o broju bez njegovog direktnog računanja.
Gde se ova tema vraća kasnije
u kongruencijama i ostacima pri deljenju
u zadacima sa periodama i poslednjom cifrom stepena
u racionalnim izrazima i razlaganju na faktore, gde NZD i NZS ubrzavaju računanje
Zašto je važna na prijemnom
ETF i MATF često imaju zadatke sa ostacima i modularnim obrascima
brzo nalaženje NZD i NZS štedi vreme u složenijim numeričkim zadacima
pogrešan ostatak ili loše vođen Euklidov algoritam lako obori ceo zadatak
Glavna poruka
Ako naučiš da misliš u deliocima, faktorima i ostacima, mnogo ređe ćeš računati „na silu“.
2. Deljivost i prosti brojevi
Od zapisa a | b do faktorizacije na proste činioce
Deljivost je precizan način da kažeš da jedan broj ulazi u drugi bez ostatka. Iz te jedne ideje nastaju prosti brojevi, rastavljanje na činioce i kasnije NZD i NZS.
Šta znači a | b
\[a \mid b \Longleftrightarrow \exists k \in \mathbb{Z} \text{ tako da je } b = ak\]
Čita se: broj \(a\) deli broj \(b\). To znači da pri deljenju broja \(b\) brojem \(a\) nema ostatka.
Prosti i složeni brojevi
Prirodan broj veći od \(1\) je prost ako ima tačno dva pozitivna delioca: \(1\) i samog sebe. Ako ih ima više, broj je složen.
Primer: \(13\) je prost, a \(12\) je složen.
Važna napomena: broj \(1\) nije ni prost ni složen.
Faktorizacija na proste činioce
\[84 = 2^2 \cdot 3 \cdot 7\]
Rastavljanje na proste činioce je osnovna „lična karta“ broja. Iz nje se lako čitaju delioci, NZD i NZS.
Korisni testovi deljivosti
sa \(2\): poslednja cifra je parna
sa \(3\): zbir cifara je deljiv sa \(3\)
sa \(5\): poslednja cifra je \(0\) ili \(5\)
sa \(9\): zbir cifara je deljiv sa \(9\)
\[360 = 2^3 \cdot 3^2 \cdot 5\]
Kada broj rastaviš na proste činioce, dobijaš preglednu strukturu umesto jedne „zbijene“ cifarske forme.
Mikro-provera: zašto broj 1 nije prost?
Zato što prost broj mora imati tačno dva pozitivna delioca. Broj \(1\) ima samo jednog pozitivnog delioca: samog sebe.
3. NZD, NZS i Euklidov algoritam
Najveći zajednički delilac dolazi iz ostataka, ne iz pogađanja
NZD i NZS su dva lica istog odnosa među brojevima. Jedan govori koliki je najveći zajednički delilac, a drugi koliki je najmanji zajednički sadržalac. Euklidov algoritam je najbrži sistematičan put do NZD-a.
Najveći zajednički delilac
\[\operatorname{NZD}(a,b)\]
To je najveći prirodan broj koji deli i \(a\) i \(b\). Ako je NZD jednak \(1\), brojevi su uzajamno prosti.
Najmanji zajednički sadržalac
\[\operatorname{NZS}(a,b)\]
To je najmanji prirodan broj koji je deljiv i sa \(a\) i sa \(b\). Važan je pri sabiranju razlomaka i usklađivanju perioda.
Korak Euklidovog algoritma
\[a = bq + r,\qquad 0 \le r < b\]
Zatim umesto para \((a,b)\) posmatraš par \((b,r)\). Postupak se ponavlja dok ostatak ne postane nula.
Formula između NZD i NZS
\[\operatorname{NZD}(a,b)\cdot \operatorname{NZS}(a,b)=|ab|\]
Za pozitivne cele brojeve ova formula daje najbrži prelaz sa NZD-a na NZS i obrnuto.
\[84 = 30 \cdot 2 + 24\]
\[30 = 24 \cdot 1 + 6\]
\[24 = 6 \cdot 4 + 0\]
\[\operatorname{NZD}(84,30)=6\]
Poslednji nenulti ostatak je traženi NZD. To je signal da algoritam nije „serija podela“, nego pažljivo vođen niz ostataka.
Mikro-provera: ako je NZD(a,b)=1, da li to znači da je jedan od brojeva nužno prost?
Ne znači. Na primer, \(8\) i \(9\) su uzajamno prosti, ali ni jedan ni drugi nije prost.
4. Kongruencije i ostaci
Kongruencija znači da dva broja ostavljaju isti ostatak
Modularno razmišljanje ne gleda ceo broj, nego njegov ostatak pri deljenju izabranim modulom. Upravo to omogućava elegantna rešenja zadataka sa poslednjom cifrom i periodama stepena.
Definicija kongruencije
\[a \equiv b \pmod m \Longleftrightarrow m \mid (a-b)\]
To je isto što i tvrdnja da \(a\) i \(b\) daju isti ostatak pri deljenju sa \(m\).
Kako se čita ostatak
\[17 \equiv 5 \pmod{12}\]
Pošto važi \(17-5=12\), razlika je deljiva sa \(12\). Zato su \(17\) i \(5\) u istoj klasi ostataka modulo \(12\).
Klase ostataka modulo 10
Ako te zanima poslednja cifra broja, dovoljno je da radiš modulo \(10\), jer poslednja cifra i ostatak pri deljenju sa \(10\) nose istu informaciju.
Zašto se cifre stepena ponavljaju
\[7^1 \equiv 7,\; 7^2 \equiv 9,\; 7^3 \equiv 3,\; 7^4 \equiv 1 \pmod{10}\]
Ostatci ulaze u ciklus. Kada vidiš periodu, ne moraš računati ceo veliki stepen.
Pedagoški trik
Kongruenciju uvek čitaj kao „isti ostatak“, a ne samo kao novi simbol za jednakost.
Mikro-provera: da li iz 29 ≡ 5 (mod 12) sledi da su brojevi jednaki?
Ne. Sledi samo da imaju isti ostatak pri deljenju sa \(12\). Jednaki bi bili samo kada bi imali istu vrednost, a ovde je razlika \(24\).
5. Interaktivni laboratorijum
Prati korake Euklidovog algoritma i odmah proveri kongruencije
Izaberi par brojeva ili unesi svoj. Canvas prikazuje svaki korak oblika a = bq + r, dok desno automatski dobijaš NZD, NZS, faktorizaciju i ostatke modulo zadatog broja.
Svaki red predstavlja jedan korak deljenja sa ostatkom. Poslednji nenulti ostatak je NZD.
Aktivni par brojeva
Posmatramo brojeve \(a=84\) i \(b=30\), uz modul \(m=10\).\[\operatorname{NZD}(84,30)=6,\qquad \operatorname{NZS}(84,30)=420\]Algoritam kreće od većeg broja, pa se problem smanjuje preko ostataka dok ne stigne do nule.
\[84 = 2^{2} \cdot 3 \cdot 7\]\[30 = 2 \cdot 3 \cdot 5\]Brza analiza
NZD\(6\)
Ovo je najveći zajednički delilac oba broja.
NZS\(420\)
Najmanji prirodan broj deljiv i sa \(a\) i sa \(b\).
Uzajamna prostostNe
Postoji zajednički delilac veći od 1.
Ostatak 84 mod 10\(84 \equiv 4 \pmod{10}\)
Ostatak 30 mod 10\(30 \equiv 0 \pmod{10}\)
Kongruentni mod mNe
Brojevi nemaju isti ostatak modulo 10.
Kako da čitaš rezultat: NZD dolazi iz Euklidovog algoritma, NZS iz veze sa proizvodom, a kongruencija iz poređenja ostataka modulo \(m\).
Kako da učiš iz ovog laboratorijuma
Pokušaj da prvo sam izračunaš NZD pa tek onda proveri ekran. Menjaj parove i gledaj kako se broj koraka smanjuje kada su brojevi bliski.
6. Vođeni primeri
Tri tipična pitanja koja moraš umeti da rešiš
Svaki primer naglašava drugu vrstu misaonog poteza: faktorizaciju, algoritam ili modularnu periodu.
Faktorizacija i NZD/NZS
Nađi NZD i NZS brojeva \(360\) i \(84\).
1
\(360 = 2^3 \cdot 3^2 \cdot 5\)
2
\(84 = 2^2 \cdot 3 \cdot 7\)
3
Za NZD uzimaš zajedničke proste činioce sa manjim eksponentima.
\[2^2 \cdot 3 = 12\]
4
Za NZS uzimaš sve prisutne činioce sa većim eksponentima.
\[2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520\]
Euklidov algoritam bez preskakanja koraka
Nađi \(\operatorname{NZD}(252,198)\).
\[252 = 198 \cdot 1 + 54\]
\[198 = 54 \cdot 3 + 36\]
\[54 = 36 \cdot 1 + 18\]
\[36 = 18 \cdot 2 + 0\]
\[\operatorname{NZD}(252,198)=18\]
Ne zaustavljaj se kod prvog „lepog“ broja. Staješ tek kada ostatak postane nula.
Poslednja cifra velikog stepena
Odredi poslednju cifru broja \(7^{23}\).
1
Radi modulo \(10\), jer te zanima poslednja cifra.
2
Perioda za stepene broja \(7\) modulo \(10\) je \(7,9,3,1\), dužine \(4\).
3
Pošto je \(23 \equiv 3 \pmod{4}\), uzimaš treći član ciklusa.
\[7^{23} \equiv 7^3 \equiv 3 \pmod{10}\]
Poslednja cifra je \(3\).
7. Ključni zapisi
Formule i rečenice koje treba da razumeš bez zastoja
Ove kartice služe da povežeš simbol sa značenjem i tipičnom upotrebom u zadatku.
Osnovna definicija
\[a \mid b \Longleftrightarrow b = ak\]
Nema ostatka pri deljenju broja \(b\) brojem \(a\).
Tačno dva pozitivna delioca
\[p>1,\quad p \text{ je prost } \Longleftrightarrow \text{delioci su } 1 \text{ i } p\]
Broj \(1\) nije prost i to moraš izričito pamtiti.
Korak sa ostatkom
\[a = bq + r,\qquad 0 \le r < b\]
Par \((a,b)\) zamenjuješ parom \((b,r)\).
Veza preko proizvoda
\[\operatorname{NZD}(a,b)\cdot \operatorname{NZS}(a,b)=|ab|\]
Za pozitivne brojeve ovo je najbrža veza između dve veličine.
Isti ostatak
\[a \equiv b \pmod m \Longleftrightarrow m \mid (a-b)\]
Kongruentni brojevi ne moraju biti jednaki, ali imaju isti ostatak modulo \(m\).
Poseban slučaj
\[\operatorname{NZD}(a,b)=1\]
Tada brojevi nemaju zajedničke proste činioce osim \(1\).
8. Česte greške
Greške koje redovno kvare zadatke iz deljivosti
Ovo nisu opšti saveti, nego konkretni padovi koncentracije koji se stalno ponavljaju.
Broj \(1\) se proglašava prostim
Nije prost, jer nema tačno dva pozitivna delioca. Ovo je standardna zamka.
NZS se automatski uzima kao proizvod
To važi samo za uzajamno proste brojeve. U suprotnom moraš uračunati zajedničke činioce pravilno.
Euklidov algoritam se prekida prerano
Tačan odgovor je poslednji nenulti ostatak, ne prvi mali ili „simpatičan“ broj koji se pojavi usput.
Kongruencija se čita kao obična jednakost
Iz \(29 \equiv 5 \pmod{12}\) ne sledi da je \(29=5\), nego samo da imaju isti ostatak modulo \(12\).
9. Veza sa prijemnim zadacima
Kako se ova tema zaista pojavljuje na ispitima
Na težim prijemnim zadacima retko se traži samo jedna definicija. Obično moraš da spojiš više ideja: ostatke, periodu, prost rastav ili Euklidov algoritam.
Tipične forme zadataka
poslednja cifra ili ostatak velikog stepena
traženje NZD i NZS velikih brojeva
poređenje ostataka preko kongruencija
parametarski uslovi koji skrivaju deljivost
Prijemni kontrolna lista
1. proveri da li treba faktorizacija ili Euklid
2. ako je zadatak o cifri, misli modulo \(10\)
3. traži periodu ostataka umesto direktnog računanja
4. rezultat na kraju proveri povratno kroz deljivost
Prijemni refleks
Kada vidiš ogroman stepen ili nezgodan ostatak, prvo pitaj „koji je pravi modul?“.
10. Vežbe
Kratka provera razumevanja
Reši samostalno, pa tek onda otvori rešenje.
Zadatak 1: Prost ili složen
Odredi da li je broj \(91\) prost ili složen.
Rešenje
\[91 = 7 \cdot 13\]
Broj \(91\) je složen, jer ima bar još delioca pored \(1\) i samog sebe.
Zadatak 2: NZD i NZS
Nađi \(\operatorname{NZD}(72,90)\) i \(\operatorname{NZS}(72,90)\).
Rešenje
\[72 = 2^3\cdot 3^2,\qquad 90 = 2\cdot 3^2 \cdot 5\]
\[\operatorname{NZD}(72,90)=2\cdot 3^2=18\]
\[\operatorname{NZS}(72,90)=2^3\cdot 3^2\cdot 5=360\]
Zadatak 3: Kongruencija
Proveri da li važi \(47 \equiv 11 \pmod{12}\).
Rešenje
\[47-11=36\]
Pošto je \(36\) deljivo sa \(12\), zaista važi \(47 \equiv 11 \pmod{12}\).
Zadatak 4: Poslednja cifra
Odredi poslednju cifru broja \(3^{25}\).
Rešenje
\[3^1 \equiv 3,\; 3^2 \equiv 9,\; 3^3 \equiv 7,\; 3^4 \equiv 1 \pmod{10}\]
\[25 \equiv 1 \pmod{4}\]
\[3^{25} \equiv 3^1 \equiv 3 \pmod{10}\]
Poslednja cifra je \(3\).
Glavni uvid lekcije
Ostatak nije sporedan podatak
Preko ostatka vodiš Euklidov algoritam, preko ostatka čitaš kongruenciju, a preko ostatka rešavaš i zadatke sa poslednjom cifrom.
Najvažniji princip
\[a = bq + r \qquad \Longrightarrow \qquad \text{ostatak vodi sledeći korak razmišljanja}\]
11. Završni rezime
Šta treba da zapamtiš iz ove lekcije
Ako ove tvrdnje možeš samostalno da objasniš, lekcija je dobro savladana.
1. Deljivost
Zapis \(a \mid b\) znači da pri deljenju broja \(b\) brojem \(a\) nema ostatka.
2. Prosti brojevi
Prost broj ima tačno dva pozitivna delioca, a broj \(1\) nije ni prost ni složen.
3. Faktorizacija
Rastavljanje na proste činioce pomaže da brzo čitaš delioce, NZD i NZS.
4. Euklidov algoritam
Završava se kada ostatak postane nula; poslednji nenulti ostatak je NZD.
5. NZD i NZS
Za pozitivne brojeve važi \(\operatorname{NZD}(a,b)\cdot\operatorname{NZS}(a,b)=ab\).
6. Kongruencije
Kongruencija \(a \equiv b \pmod m\) znači da \(a\) i \(b\) daju isti ostatak modulo \(m\).
7. Prijemni fokus
Za zadatke sa poslednjom cifrom i velikim stepenima najvažnije je da pronađeš pravi modul i periodu ostataka.