MetaMath '24

\textbf{Definicija:}\\ Najveći zajednički djelitelj (mjera) prirodnih brojeva $m$ i $n$ je najveći prirodni broj koji dijeli i $m$ i $n$ (dosta logično). Ako je taj broj jednak $1$, onda kažemo da su $m$ i $n$ relativno prosti. Inače se za označavanje najvećeg zajedničkog djelitelja od $m$ i $n$ koristi neka od oznaka: $M(m, n), nzd(m, n), gcd(m, n)$. Ja preferiram $gcd(m, n)$, a vi koristite onu koja vam se najviše sviđa. To da su $m$ i $n$ relativno prosti (odnosno da je $gcd(m, n) = 1$) možemo zapisati kao: $m \perp n$. Možda se na prvu koncept mjere čini nasumičan, jako brzo će imati bitnu ulogu kod rješavanja zadataka iz teorije brojeva. Ovaj teorem je ono što upotpunjuje mjeru: \textbf{Euklidov algoritam:}\\ Neka su $m$ i $n$ prirodni i $m > n$. Tada vrijedi: $gcd(m, n) = gcd(m - n, n)$. Ovaj teorem obično koristimo kao alat za pronalaženje najvećeg zajedničkog djelitelja dvaju brojeva. Želimo primjenjivati Euklidov algoritam dok ne dobijemo dva broja kojima znamo odrediti mjeru.\\ \textbf{Dokaz Euklidovog algoritma, primjer kako koristiti prethodna svojstva:}\\ Stavimo $k := gcd(m - n, n)$ i dokažimo da $k$ dijeli i $m$ i $n$. Iz definicije najvećeg zajedničkog djelitelja imamo $k | m - n$ i $k | n$, a sada $k$ dijeli $m - n$ i $n$ pa dijeli i njihovu sumu, odnosno $k | m$. Pretpostavimo sada da postoji neki $l > k$ koji dijeli $m$ i $n$. Za njega onda vrijedi da dijeli njihovu razliku, odnosno $l | m - n$ pa vidimo da je $l$ zajednički djelitelj od $m - n$ i $n$, a veći je od $k$ i dolazimo do kontradikcije jer je $k$ najveći zajednički djelitelj tih brojeva. Ovdje zaključujemo da $k$ uistinu jest mjera brojeva $m$ i $n$.\\ U idućem zadatku pokazujemo primjere na kojima se koristi Euklidov algoritam, a vi kao odgovor na ovo pitanje napišite koliko je $gcd(12, 18)$.