Kongruencije i operacije po modulu

🎯 Cilj lekcije

Objasni zapis kongruencije i odredi ostatak.
Primijeni sabiranje, oduzimanje i množenje po modulu.
Izračunaj ostatak velikog stepena i objasni ograničenje dijeljenja.

1. Prije početka

Pripremi papir i olovku. Tokom čitanja zapiši šta je poznato, šta tražiš i koji uslovi vrijede. Prvo pokušaj predvidjeti odgovor, zatim ga uporedi s računom.

2. Razumij pojam

Sat se vraća na iste oznake nakon 12 sati. Dani u sedmici ponavljaju se nakon 7 dana. Modularni račun opisuje takve cikluse pomoću ostataka pri dijeljenju.

3. Pravila i veze

a≡b (mod n) znači da n dijeli a−b, uz prirodan n≥1. Brojevi imaju isti ostatak pri dijeljenju s n. Kongruencije istog modula smiješ sabirati, oduzimati i množiti; smiješ podizati na prirodan stepen. Dijeljenje nije automatski dozvoljeno. Iz 2·1≡2·4 (mod 6) ne slijedi 1≡4 (mod 6). Skraćivanje faktorom uz isti modul dozvoljeno je ako je faktor uzajamno prost s modulom.

4. Istraži primjere

Izaberi slučaj. Predvidi rezultat prije promjene, zatim objasni šta se na prikazu promijenilo.

Slučaj:

8 ≡ 1 (mod 7); kazaljka pokazuje ostatak.

5. Rješenje korak po korak

2¹⁰⁰ (mod 7)Tražiš ostatak stepena pri dijeljenju sa 7.

2¹ ≡ 2, 2² ≡ 4, 2³ ≡ 1 (mod 7)Ostaci se ponavljaju u ciklusu dužine 3.

100=3·33+1 ⇒ 2¹⁰⁰ ≡ 1³³·2 ≡ 2 (mod 7)Izdvoji potpun broj ciklusa i jedan preostali faktor.

2⁴=16 = 7·2+2 ✓Novi ciklus ponovo počinje ostatkom 2. Traženi ostatak je 2.

Riješeni primjeri

Vježbaj uz riješene primjere. Za svaki tip zadatka slijede tri primjera. Pokušaj sam zapisati sljedeći red, pa otkrij postupak korak po korak.

Ostatak i kongruencija — tri riješena primjera

Primjer 1: Ostatak i kongruencija

Odredi ostatak pri dijeljenju 14 sa 3 i napiši kongruenciju.

14=3 · 4 + 2Zapiši dijeljenje s ostatkom.

0 ≤ 2 < 3Ostatak mora biti manji od pozitivnog djelioca.

14 ≡ 2 (mod 3)Kongruencija izražava isti ostatak.

14 − 2=12 = 3 · 4 ✓Razlika je djeljiva modulom.

Primjer 2: Ostatak i kongruencija

Odredi ostatak pri dijeljenju 19 sa 4 i napiši kongruenciju.

19=4 · 4 + 3Zapiši dijeljenje s ostatkom.

0 ≤ 3 < 4Ostatak mora biti manji od pozitivnog djelioca.

19 ≡ 3 (mod 4)Kongruencija izražava isti ostatak.

19 − 3=16 = 4 · 4 ✓Razlika je djeljiva modulom.

Primjer 3: Ostatak i kongruencija

Odredi ostatak pri dijeljenju 27 sa 5 i napiši kongruenciju.

27=5 · 5 + 2Zapiši dijeljenje s ostatkom.

0 ≤ 2 < 5Ostatak mora biti manji od pozitivnog djelioca.

27 ≡ 2 (mod 5)Kongruencija izražava isti ostatak.

27 − 2=25 = 5 · 5 ✓Razlika je djeljiva modulom.

Računanje s ostacima — tri riješena primjera

Primjer 1: Računanje s ostacima

Odredi ostatak zbira 14 + 17 pri dijeljenju sa 3.

14 ≡ 2 (mod 3)Prvi sabirak zamijeni njegovim ostatkom.

17 ≡ 2 (mod 3)Dodavanje modula ne mijenja ostatak.

14 + 17 ≡ 4 ≡ 1 (mod 3)Saberi ostatke i ponovo ih svedi.

31=3 · 10 + 1 ✓Provjeri stvarnim dijeljenjem zbira.

Primjer 2: Računanje s ostacima

Odredi ostatak zbira 19 + 23 pri dijeljenju sa 4.

19 ≡ 3 (mod 4)Prvi sabirak zamijeni njegovim ostatkom.

23 ≡ 3 (mod 4)Dodavanje modula ne mijenja ostatak.

19 + 23 ≡ 6 ≡ 2 (mod 4)Saberi ostatke i ponovo ih svedi.

42=4 · 10 + 2 ✓Provjeri stvarnim dijeljenjem zbira.

Primjer 3: Računanje s ostacima

Odredi ostatak zbira 27 + 32 pri dijeljenju sa 5.

27 ≡ 2 (mod 5)Prvi sabirak zamijeni njegovim ostatkom.

32 ≡ 2 (mod 5)Dodavanje modula ne mijenja ostatak.

27 + 32 ≡ 4 ≡ 4 (mod 5)Saberi ostatke i ponovo ih svedi.

59=5 · 11 + 4 ✓Provjeri stvarnim dijeljenjem zbira.

Ostatak velikog stepena: korak po korak

Izračunaj male stepene i dokaži ciklus. Ako se pojavi ostatak 1, grupiši faktore do tog stepena. Za eksponent djeljiv dužinom ciklusa ostatak nije automatski 0.

Primjer 1: Ostatak velikog stepena

Odredi ostatak 2¹⁰⁰ pri dijeljenju sa 7.

2³ = 8 ≡ 1 (mod 7)Tri faktora 2 daju ostatak 1.

100 = 3·33 + 1Odredi koliko ima cijelih grupa i koliko faktora ostaje.

2¹⁰⁰ ≡ (2³)³³·2 ≡ 1³³·2 ≡ 2 (mod 7)Traženi ostatak je 2.

Primjer 2: Ostatak velikog stepena

Odredi ostatak 3²⁰ pri dijeljenju sa 8.

3² = 9 ≡ 1 (mod 8)Uoči grupu od dva faktora.

20 = 2·10Nema preostalih faktora.

3²⁰ ≡ (3²)¹⁰ ≡ 1¹⁰ ≡ 1 (mod 8)Ostatak je 1; eksponent sa ostatkom 0 ne daje ostatak broja 0.

Primjer 3: Ostatak velikog stepena

Odredi posljednju cifru 7²³.

7¹ ≡ 7, 7² ≡ 9, 7³ ≡ 3, 7⁴ ≡ 1 (mod 10)Posljednja cifra je ostatak pri dijeljenju sa 10.

23 = 4·5+3Izdvoji pet potpunih ciklusa.

7²³ ≡ (7⁴)⁵·7³ ≡ 1⁵·3 ≡ 3 (mod 10)Posljednja cifra je 3.

Samostalno: Odredi ostatak 2⁵⁰ pri dijeljenju sa 7 i posljednju cifru 3¹².

Provjeri postupak

2³≡1 (mod7);50=3·16+2, pa ostatak 4. Za3⁴≡1 (mod10),12=4·3, pa posljednja cifra1.

6. Primijeni i provjeri

Primjer i zadatak: Danas je ponedjeljak. Za 100 dana je 100≡2 (mod 7), pa će biti srijeda. U modulu 5: 8+9≡3+4≡2; 8·9≡3·4≡2. Za negativne brojeve −1≡4 (mod 5), jer −1−4=−5. Oduzimanje u modulu 6:17−29≡5−5≡0, jer −12 dijeljen sa 6 daje ostatak 0. Uobičajeni ostaci su 0,1,...,n−1.

Pokrij rješenje i ponovi postupak. Promijeni jedan podatak, riješi novi zadatak i provjeri ga istom metodom. Objasni zašto se odabrano pravilo može primijeniti.

Samostalni zadaci s provjerom

Zadatak 1. Izračunaj(17+29) mod 6 i(17·29) mod 6.

Provjeri rješenje i postupak

17≡5 i 29≡5; zbir≡10≡4, proizvod≡25≡1 (mod 6).

Zadatak 2. Nađi ostatak 3²⁰ pri dijeljenju sa 8.

Provjeri rješenje i postupak

3²=9≡1 (mod 8), pa 3²⁰=(3²)¹⁰≡1. Ostatak 1.

Zadatak 3. Smiješ li iz 2a≡2b (mod 6) zaključiti a≡b (mod 6)? Daj primjer.

Provjeri rješenje i postupak

Ne. a=1,b=4 daje 2≡8 (mod 6), ali 1 nije kongruentno 4. Faktor 2 nije uzajamno prost s 6.

7. Česte greške

⚠️ Česte greške

Kongruencija nije obična jednakost cijelih brojeva.
Ne dijeli obje strane proizvoljnim brojem uz isti modul.
Smanji izložilac po dužini dokazanog ciklusa, ne naslijepo po modulu.

8. Provjeri znanje

1. 17 mod 5 je

2. 3·4 mod 5 je

3. 2¹⁰⁰ mod 7 je

Svaki pokušaj ti pokazuje šta već razumiješ. Ako pogriješiš, ponovi pravila i primjer korak po korak, pa riješi sličan zadatak na papiru.

Izvor zahtjeva: Predmetni kurikulum KS, Matematika, označena str. 42. Objašnjenja i zadaci su vlastiti sadržaj portala.