Show that there exists $(k, n) \in \mathbb{N}^2$ such that $P \cap [\![ n, +\infty [\![ = k \mathbb{N} \cap [\![ n, +\infty [\![$

Question

The exercise

Let $P \subseteq \mathbb{N}$ non-empty such that $\forall a, b \in P, a+b \in P$. Show that there exists $(k, n) \in \mathbb{N}^2$ such that $P \cap [\![ n, +\infty [\![ = k \mathbb{N} \cap [\![ n, +\infty [\![$.

My try

We easily get: $\forall (a_1, \dots a_p) \in P, \forall (l_1, \dots, l_p) \in \mathbb{N}, l_1 a_1+\dots+l_pa_p \in P$.

The case $P = \{ 0 \}$ is trivial, so let's assume $P - \{ 0 \}$ is non-empty and denote $m$ its minimum. I'm not sure this approach will work because if I take as $P$ the subset of finite sums of prime numbers, I can't even figure the values of $k$ and $n$.

I think there is a link with the gcd of some elements of $P$, but which ones? The "smallest" ones?

Thanks for the help.

Answer 1

The answer was given by Greg Martin in a comment, let me write it down.

Let $k = \inf \{d \in \mathbb{N}^*:\ \exists p_1,...,p_n: \gcd(p_1,...,p_m)=d\}$.

We have $P \subset k\mathbb{N}$. Conversely, we can also find $n$ large enough so that $ k\mathbb{N} \cap [\![n,\infty[\![ \subset P \cap [\![n,\infty[\![$.

You can see at the following link a proof that a solution to the coin problem exists. Namely, with $p_1,...,p_m$ such that $\gcd(p_1,...,p_m)=k$, there exists $n$ such that for all $q \ge n$ with $k | q$, there exist $a_1,...,a_m \in \mathbb{N}$ such that $\sum \limits_{i=1}^m a_ip_i = kq$. Since $P$ is stable under addition, $\sum \limits_{i=1}^m a_ip_i \in P$, so $k \mathbb{N} \cap [\![n,\infty[\![ \subset P \cap [\![n, \infty[\![$.

Combining both gives you $P \cap [\![n, \infty[\![ = k\mathbb{N} \cap [\![n,\infty[\![$.