ODREĐIVANJE NZD I NZS POMOĆU EUKLIDOVOG ALGORITMA

Euklidov algoritam je dobio naziv po Grčkom matematičaru Euklidu i koristi se za efikasno određivanje najvećeg zajedničkog delioca, kao i određivanje najmanjeg zajedničkog sadržalaca dva ili više celih brojeva.Euklidov algoritam,  jedan je od najstarijih poznatih matematičkih algoritama. Prvi put je opisan u Euklidovim „Elementima“ pre više od 2000 godina, a njegova osnovna struktura ostala je nepromenjena do danas. Ovaj algoritam se koristi za efikasno pronalaženje najvećeg zajedničkog delioca (GCD) dva ili više celih brojeva. Njegova jednostavnost, preciznost i široka primena čine ga jednim od najvažnijih alata u matematičkim i algoritamskim disciplinama.Euklidov algoritam se prvenstveno koristi za pronalaženje najvećeg zajedničkog delioca (GCD) dva broja. Ovo je korisna procedura u mnogim matematičkim i inženjerskim problemima, jer omogućava uprošćavanje razlomaka, analizu cikličnih procesa i rešavanje problema deljivosti. Osim za pronalaženje GCD, algoritam se koristi i za izračunavanje najmanje zajedničke komponente (LCM) dva broja, što dodatno povećava njegovu praktičnu vrednost.Zašto je to važno?

Euklidov algoritam se široko koristi u različitim oblastima:

• Matematika: Algoritam se koristi u teoriji brojeva za rešavanje problema deljivosti, kao i za generisanje proširenih verzija algoritma koje omogućavaju rešavanje Diofantovih jednačina.
• Programiranje: Kao jedan od osnovnih algoritama, često se koristi u softverskom inženjerstvu i algoritamskim izazovima. Njegova efikasnost i jednostavnost čine ga savršenim primerom algoritamske optimizacije.
• Kriptografija: U savremenim aplikacijama, Euklidski algoritam je ključni element u algoritmima za generisanje i analizu kriptografskih ključeva, kao što su RSA i Diffie-Hellman protokoli.

Određivanje najvećeg zajedničkog delioca NZD

​Oređivanje  NZD-a dva broja  A i B  zasniva se na činjenici da:
I A i B su deljivi sa NZD
Ostatak deljenja A i B je takođe deljiv sa NZD
To znači da ako su A i B celi brojevi čiji se NZD traži, i ako označimo da je d=NZD, p-rezultat deljenja a q-ostatak deljenja, onda se može napisati:
A = p*B+q , p i q su celi brojevi
Dakle, A, B i q su deljivi sa d
Pogledajmo to na sledećem primeru za brojeve A=48 i B=28
Odredimo prvo NZD:
Na slici pod a je prikazan klasičan način određivanja NZD-a i to je u ovom slučaju 4.
Na slici pod b se vidi da se NZD sadrži i u broju 48 i 28, ali i u ostatku deljenja ta dva broja. Dakle, možemo reći da:
48=1*28+20
što odgovara izrazu 1:
A = p*B+q , p i q su celi brojevi
Vidi se na slici pod b) da će B i q biti deljivi sa NZD.
Ako sada uzmemo da tražimo NZD za B i q, tj. za 28 i 20 videli bi smo da je NZD isti.
Ponavljanjem postupka deljenja prethodnog delioca sa ostatkom deljenja sve dok u jednoj iteraciji ostatak deljenja ne bude nula, doći ćemo do broja koji predstavlja NZD. Poslednji rezultat deljenja je zapravo broj koji tražimo. U našem primeru, to je broj 4. Vidi sliku pod c).
Prethodni postupak je poznat kao Euklidov algoritam.​

Primeri i kontekst

Pored primera sa A=48 i B=28, uključivanje više različitih primera sa većim brojevima može da ilustruje robusnost Euklidovog algoritma.

• Primer sa većim brojevima. Hajde da izračunamo NZD za A=987654 i B=123456. Ovo naglašava efikasnost algoritma, čak i sa značajnim numeričkim ulazima, naglašavajući njegovu primenljivost u računarskim kontekstima.
• Primena u stvarnom svetu: Kriptografija. U kriptografskim algoritmima kao što je RSA, Euklidov algoritam igra ključnu ulogu u izračunavanju modularnih inverza. Demonstracija ovog slučaja upotrebe može pokazati kako algoritam podržava moderne bezbednosne sisteme, čineći teorijski aspekt povezanim sa scenarijima iz stvarnog sveta.
• Određivanje NZS -a korišćenjem NZD-a.Primer izračunavanja najmanjeg zajedničkog sadržaoca(NZS) dva broja koristeći njihov NZD može proširiti kontekst:

NZS(A,B)=∣A*B∣/NZD(A,B)

​Pokazivanje kako Euklidov algoritam indirektno pomaže u pronalaženju LCM-a bi podvukao njegovu svestranost.

Određivanje NZD-a algoritam:

​Program učitava dva cela broja a i b i određuje NZD za ta dva broja. Sa a je označen veći od ta dva, a sa b manji.
​Kod koji rešava ovaj problem na iterativan način bi bio:
​Prvo se učitavaju dva cela broja x i y, proverava se koji je veći i koji je manji i smeštaju se u promenljive
a-veći između x i y
b-manji između x i y
Iterativnim postupkom se dalje, ponavlja postupak traženja ostatka deljenja delioca i ostatka u deljenja prethodne iteracije. Postupak se ponavlja dok je ostatak deljenja različit od nule. Poslednji delilac u while petlji je zapravo traženi NZD.
Više o petljama u C jeziku pročitajte na web strani: Petlje u programskom jeziku C/C++

Određivanje NZD-a rekurzijom - algoritam:

​Umesto iterativno kroz while petlju ovaj problem se može rešiti i rekurzivno: ​Funkcija NZDRek prima dva parametra a i b, i to tako da je prvi veći od drugog. Ako je ostatak deljenja r jednak nuli vraća se drugi broj, to jest delilac. Ako nije, postupak se ponavlja tako što funkcija poziva samu sebe i menja parametre, tako da je prvi, deljenik u stvari prethodni delilac tj. drugi parametar u prethodnom pozivu. Na drugom mestu je ostatak deljenja iz prethodnog rekurzivnog poziva.
Više o funkcijama pročitajte na web strani: Funkcije u C/C++

Određivanje najmanjeg zajedničkog sadržalaca NZS

​Najmanji zajednički sadržalac se može odrediti tako što se prvo odredi NZD i onda iz izraza
NZS(a,b)*NZD(a,b) = a*b
određuje NZS
NZS = a/(NZD(a,b)  *b;
U prethodno opisanom primeru za brojeve 48 i 28: Na slici pod a) se vidi kako se određuje NZD, a na slici pod b) NZS za brojeve 48 i 28. Na slici pod c) je pokazano da je proizvod NZD i NZS jednak proizvodu brojeva 28 i 48, tj. u nekom opštem slučaju a i b.
Sledeći kod će prema tome izračunati NZS, na osnovu NZD:

Prošireni Euklidov algoritam

Uvod u prošireni euklidski algoritam je moćno proširenje standardnog Euklidovog algoritma. Dok Euklidov algoritam određuje najveći zajednički delilac (NZD) dva cela broja, proširena verzija takođe pronalazi cele brojeve x i y koji zadovoljavaju jednačinu:

ax+by=GCD(a,b)

Ova dodatna funkcionalnost ga čini neprocenjivim u oblastima kao što su rešavanje linearnih Diofantovih jednačina i modularna aritmetika.

Matematika iza algoritma:
Rešavanje Diofantovih jednačina su jednačine gde se rešenja traže u celim brojevima. Prošireni Euklidov algoritam pruža konstruktivan način da se pronađu takva rešenja za jednačinu
ax+by=d,
gde je d NZD za a i b. Radeći unazad od euklidskih koraka, on određuje koeficijente x i y. Ovaj proces osigurava da je jednačina zadovoljena ovim celim brojevima.

Praktične primene u kriptografiji i teoriji brojeva.
Prošireni Euklidov algoritam se široko koristi u:

• Kriptografija: Računanje modularnih inverza u algoritmima kao što je RSA za efikasno šifrovanje i dešifrovanje.
• Teorija brojeva: Rešavanje linearnih kongruencija i pronalaženje celih brojeva koji zadovoljavaju određena modularna svojstva.
• Računarstvo: Primene u heširanju, kompresiji podataka i teoriji kodiranja. Iterativne i rekurzivne implementacije sa objašnjenjima
  

Algoritam se može implementirati i na iterativni i na rekurzivni način. Evo objašnjenja za svaki:
Iterativna implementacija:
Iterativni pristup izračunava NZD uz istovremeno održavanje koeficijenata x i y. Algoritam skladišti srednje vrednosti i ažurira ih kako se proces deljenja odvija. Ovo je efikasno za okruženja u kojima je dubina steka ograničenje.

Rekurzivna implementacija:
Rekurzivni metod prati intuitivniji pristup, direktno rešavajući za x i y dok odmotava rekurzivne pozive. Ovo je generalno jednostavnije za razumevanje i implementaciju, ali može biti ograničeno dubinom rekurzije u nekim programskim okruženjima.

Primer: Modularni inverz i rešavanje kongruencija
Pronalaženje modularnog inverza: Da biste izračunali modularni inverz od a % m(a modul m), koristite prošireni euklidov algoritam da biste pronašli k tako da je ax+my=1. Vrednost k po modulu m je inverzna. Primer koda:
#include <iostream>
#include <tuple>

// Funkcija za proširen Euklidov algoritam
std::tuple<int, int, int> extended_gcd(int a, int b) {
if (b == 0) {
return {a, 1, 0};
    }

int gcd, x1, y1;
std::tie(gcd, x1, y1) = extended_gcd(b, a % b);

int x = y1;
int y = x1 - (a / b) * y1;

return {gcd, x, y};
}

// Testiranje funkcije
int main() {
int a = 48, b = 18;
int gcd, x, y;

std::tie(gcd, x, y) = extended_gcd(a, b);

 std::cout << "NZD: " << gcd << ", x: " << x << ", y: " << y << std::endl;

return 0;
}Objašnjenje:

1. Ulazni parametri: Funkcija prima dva cela broja a i b.
2. Rekurzija: Kada je b jednako 0, funkcija vraća NZD kao a, i koeficijente x = 1, y = 0.
3. Rekurzivni poziv: Poziva se funkcija sa b i a % b.
4. Izračunavanje koeficijenata: Vrednosti x i y se računaju na osnovu rezultata iz rekurzivnog poziva.
5. Tuple: Korišćenje std::tuple za vraćanje tri vrednosti (GCD, x, y).

Primer:Za ulazne vrednosti a = 48 i b = 18, funkcija bi vratila:

• NZD: 6
• x: -1
• y: 3

Ovo znači da je 6=48⋅(−1)+18⋅36 

---

---

Korisni članci

---

---