3. Zadatak

Dokažimo da je uvjet da su $2^{x_i}-1$ i $2^{x_j}-1$ relativno prosti ekvivalentan uvjetu da su $x_i$ i $x_j$ relativno prosti.

Pretpostavimo prvo da $x_i$ i $x_j$ nisu relativno prosti. Tada postoji prirodni broj $d>1$ koji dijeli $x_i$ i $x_j$. Tada su brojevi $2^{x_i}-1$ i $2^{x_j}-1$ oba djeljivi s $2^d-1$ pa nisu relativno prosti.

Pretpostavimo sada da su $x_i$ i $x_j$ relativno prosti, te označimo s $m$ najveći zajednički djelitelj brojeva $2^{x_i}-1$ i $2^{x_j}-1$. Tada postoje cijeli brojevi $a$ i $b$ takvi da je $ax_i+bx_j=1$. Jedan od brojeva $a$ i $b$ je pozitivan, a drugi negativan. Bez smanjenja općenitosti, neka je $a>0$ i $b<0$, te označimo $c=-b>0$. Tada je $ax_i=cx_j+1$, pri čemu su $a,c\in\mathbb N$. Sada imamo: $$m\mid2^{x_i}-1,\quad2^{x_i}-1\mid2^{ax_i}-1.$$

Nadalje, $$2^{ax_i}-1=2^{cx_j+1}-1=2\cdot2^{cx_j}-1=2\cdot(2^{cx_j}-1)+1,$$ pa zaključujemo da $$m\mid2\cdot(2^{cx_j}-1)+1.$$

S druge strane, $$m\mid2^{x_j}-1,\quad2^{x_j}-1\mid2^{cx_j}-1,\quad2^{cx_j}-1\mid2\cdot(2^{cx_j}-1),$$ iz čega zaključujemo da $$m\mid2\cdot(2^{cx_j}-1),$$ što znači da $m$ dijeli dva uzastopna prirodna broja pa je $m=1$.

Zaključujemo da je $M(n)$ zapravo najveći broj brojeva koje možemo izabrati iz skupa $i\in\{1,2,\ldots,n\}$ tako da su svaka dva relativno prosta.

Pretpostavimo da je prirodni broj $k$ prost. Tada među izabranih $M(k-1)$ brojeva možemo dodati broj $k$ jer je on relativno prost sa svima njima. Dakle, u promatranom slučaju je $M(k)>M(k-1)$. Zaključujemo da je $M(k)=M(k-1)$ moguće jedino u slučaju kada je $k$ složen.