2
$\begingroup$

I encountered the following fact:

Suppose $A$ is any set of non-negative integers which is closed under addition and has greatest common divisor 1. Then $A$ must contain all but finitely many non-negative integers.

The proof presented relied on a lemma that effectively shows that there exists an $m=m(A)$ such that for all $n\in A$ with $n\geq m$ on has that $n$ can be written as a linear combination of elements of $A$ with nonnegative coefficients. The proof of this lemma is not entirely difficult but, I was wondering if there is an especially elegant one or two line proof of the fact above?

  • 0
    @Arturo Of course. Thanx2012-06-04

1 Answers 1

1

If $x,y\in A$, $x and $\gcd(x,y)=1$ (such a pair must exist) then $S=\{y,2y,\ldots,xy\}\subset A$ covers all residue classes modulo $x$ so $S+\{kx|k\in \mathbb{Z}^+\}$ includes every number $\ge xy$.

(This is short, but I don't know if you'd consider it "especially elegant," particularly if you need convincing of the "such a pair must exist" claim.)

Edit: Here's a proof for the missing step.

Let $\gcd(x_1,x_2,\ldots,x_n)=1$ for $x_i \in A, n>2$. Then by Bezout's identity there are $u,v\in \mathbb{Z}$ with $ux_1+vx_2=\gcd(x_1,x_2)$. Choose $k$ so that $kx_3\ge\max(-u,-v)$, then $ x_2' = (kx_3+u)x_1+(kx_3+v)x_2 \in A \\ x_2' \equiv \gcd(x_1,x_2) \pmod{x_3}\\ \gcd(x_2',x_3) = \gcd(x_1,x_2,x_3) \\ \gcd(x_2',x_3,\ldots,x_n)=\gcd(x_1,x_2,\ldots,x_n)=1 $ Thus given a set of $n>2$ elements of $A$ with $\gcd=1$ we can find a set with $n-1$ elements with $\gcd=1$. $A$ must contain a finite such set, so we can repeat this procedure to reduce the size until we have a pair of relatively prime elements.

In case it's necessary, to see that $A$ must have a finite set of elements with $\gcd=1$, choose any element $x$ with prime factorization $x=\prod p_i^{a_i}$. By definition $A$ must contain a $y_i$ such that $p_i \nmid y_i$, otherwise $p_i \mid \gcd(A)$. Then $\gcd(\{x\}\cup\{y_i\}_i)=1$.

Now this is probably as complicated as your original proof...

  • 0
    Thank you, while I think that this is of the same flavor as the solution I'm thinking of, your rephrasing is what I'm looking for.2012-06-05