Numeri e numeri primi

[hos-juzamdjinn]

Mostrare che ogni numero intero positivo può essere scritto come somma di distinti numeri primi
(Per questo quesito, si assuma che uno sia un numero primo!!)

L'esercizio (del Larson) iniziava con un aiuto, ma vista la bravura di molti risolutori di questo forum l'ho volutamente omesso cmq al massimo lo posterò dopo.

[Sk_Anonymous]

Ritenere che $1$ sia primo è un'indecenza. Perciò mi concedo la libertà di riformulare il problema a modo mio:

Problema: mostrare che ogni intero $n > 0$ si può esprimere come somma di elementi distinti dell'insieme $K := \{1\} \cup P$, ove $P$ è l'insieme dei primi di $\mathbb{N}$.

Dim.: la tesi è ovvia se $n = 1$, $n = 2$ oppure $n = 3$. Fissato $n \in \mathbb{Z}^+$, ammettiamo perciò - per induzione estesa - che ogni intero $k = 1, 2, \ldots, n$ verifichi la condizione postulata dal problema. In base al teorema di Chebyshev, detto allora $p$ il massimo numero primo $\le n+1$, vale $(n+1)/2 < p < n+1$, purché sia $(n+1)/2 \ge 2$, i.e. $n \ge 3$. E allora $n+1-p \le (n+1)/2$. Senonché per ipotesi induttiva esistono $p_1, p_2, \ldots, p_m \in K$, a due a due distinti, tali che $n+1-p = p_1 + p_2 + ... + p_m$, per qualche $m \in \mathbb{Z}^+$. Da qui la tesi, siccome $p_i < p$, per ogni $i = 1, 2, ..., m$.