Grade 12 2010 Problem 3

Za dani prirodni broj $n$ neka je $M(n)$ najveći prirodni broj za koji je moguće konstruirati niz prirodnih brojeva $x_{1},x_{2},\ldots ,x_{M(n)}\in \{2,3,\ldots ,n\}$ tako da vrijedi:

Za svaka dva različita broja $i,j\in \{1,2,\ldots ,M(n)\}$ brojevi $2^{x_i} - 1$ i $2^{x_j} - 1$ su relativno prosti.

Ako je $M(k) = M(k - 1)$ za neki prirodni broj $k > 1$, dokaži da je $k$ složen.