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?

  • 1
    What do you mean by "Has greatest common divisor 1"? Who has that? Obviously not all elements of $A$, as if $a\in A\,$ , then also $a+a=2a\in A$ , and $\,(a,2a)\neq 1\,$...2012-06-04
  • 0
    @DonAntonio: It makes perfect sense to talk about the gcd of a set of numbers; for a PID, it is exactly the generator of the ideal generated by the set.2012-06-04
  • 0
    @Arturo Never heard of that...so if I have $\,A:=\{3,4,8\}\,$ say, then the gcd of $A$ is $\,24\,$ , as $\,\langle 3,4,8\rangle_\mathbb{Z} = 24\mathbb{Z}\leq \mathbb{Z}\,$? , and thus the OP is asking about a set of natural numbers that the ideal generated in the integers by them is $\mathbb{Z}\,$?2012-06-04
  • 1
    @DonAntonio: What makes you think that the ideal generated by $3$, $4$, and $8$ is generated by $24$? It's generated by $1$, since it contains $4-3$. The gcd of a *set* of of numbers $\{a_i\}$ is the nonnegative number $d$ that satisfies the universal definition: it divides each $a_i$, and any common divisor of all $a_i$ divides $d$. In the case of $\mathbb{Z}$ (or any PID) it coincides with a generator of the ideal they generate. That's why we have "*pairwise coprime*" to refer to a set in which *every pair* of elements has gcd 1, as opposed to "coprime" to mean the gcd of the whole set is 1.2012-06-04
  • 0
    I was thinking of the ideal $\,3\mathbb{Z}\cap 4\mathbb{Z}\cap 8\mathbb{Z}\,$...anyway, then it is *always* the unit ideal when among the numbers are two coprime...right?2012-06-04
  • 0
    @DonAntonio: Yes; but you can have the unit ideal even when any two numbers are *not* coprime; e.g., $\gcd(6,10,15) = 1$, even though $\gcd(6,10)=2\gt 1$, $\gcd(6,15) = 3\gt 1$, $\gcd(10,15)=5\gt 1$.2012-06-04
  • 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
    What if $A$ is all the positive integer sums of $\{6,10,15\}\,$, as written in one of the comments above? What such pair must exist in this case?2012-06-04
  • 0
    6 and 25 works.2012-06-04
  • 0
    Of course, one can be a multiple of "first" ones. Thanx2012-06-04
  • 0
    Or even $16=10+6$ and $15$.2012-06-04
  • 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