3. Zadatak

S $M(a,b)$ označavamo najveću zajedničku mjeru brojeva $a$ i $b$. Poznato je da vrijedi $M(a,b)=M(b,a-b)$.

Stoga imamo:

$$\begin{aligned}M(8n+7,5n+6)&=M(5n+6,3n+1)=M(3n+1,2n+5)\\&=M(2n+5,n-4)=M(n-4,n+9)=M(n-4,13).\end{aligned}$$

Kako je $13$ prost broj, zajednička mjera broja $13$ i još nekog broja može biti samo $1$ ili $13$.

Preostaje pokazati da se oba slučaja mogu dogoditi. Na primjer,

$$\begin{aligned}n=1&\quad\Longrightarrow\quad M(11,15)=1\\n=4&\quad\Longrightarrow\quad M(26,39)=13.\end{aligned}$$