MetaMath '22

Koji je \textit{kardinalitet} (broj članova) skupa svih cijelih brojeva $n$ za koje je razlomak $\frac{40n+2}{15n-1}$ cijeli broj? \textbf{Rješenje:} Napomenimo odmah na početku rješenja kako je iz tvrdnje i dokaza Euklidovog algoritma jasno da vrijedi i $M(a,b)=M(a,b-ka)$, za svaki cijeli broj $k$. Naime, za pozitivan $k$ je to samo $k$ uzastopnih primjena (osnovnog) Euklidovog algoritma: $$M(a,b)=M(a,b-a)=M(a,(b-a)-a)=M(a,b-2a)=...=M(a,(b-(k-1)a)-a)=M(a,b-ka).$$ Sada raspisujemo: \begin{align*} M(40n-1,15n-1) &= M(40n - 1 - 2(15n-1),15n - 1) \\ &= M(10n+1,15n-1) \\ &= M(10n+1, 15n - 1 - (10n+1)) \\ &= M(10n+1,5n - 2) \\ &= M(10n+1 - 2(5n-2), 5n-2) \\ &= M(5,5n-2) = 1 \end{align*} U zadnjem koraku je najveći zajednički djelitelj $1$ jer broj $5n-2$ ne može biti djeljiv s $5$. Dakle, brojnik i nazivnik početnog razlomka su relativno prosti pa su jedini $n$ za koje taj razlomak može biti cijeli broj, oni za koje je vrijednost nazivnika $1$ ili $-1$. Očito je da je jedini takav broj $n=0$.