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
    $\begingroup$ 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\,$... $\endgroup$ – DonAntonio Jun 4 '12 at 1:43
  • $\begingroup$ @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. $\endgroup$ – Arturo Magidin Jun 4 '12 at 2:24
  • $\begingroup$ @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}\,$? $\endgroup$ – DonAntonio Jun 4 '12 at 2:31
  • 1
    $\begingroup$ @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. $\endgroup$ – Arturo Magidin Jun 4 '12 at 2:34
  • $\begingroup$ 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? $\endgroup$ – DonAntonio Jun 4 '12 at 2:39

If $x,y\in A$, $x<y$ 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...

  • $\begingroup$ 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? $\endgroup$ – DonAntonio Jun 4 '12 at 3:40
  • $\begingroup$ 6 and 25 works. $\endgroup$ – Zander Jun 4 '12 at 3:44
  • $\begingroup$ Of course, one can be a multiple of "first" ones. Thanx $\endgroup$ – DonAntonio Jun 4 '12 at 3:55
  • $\begingroup$ Or even $16=10+6$ and $15$. $\endgroup$ – Arturo Magidin Jun 4 '12 at 5:10
  • $\begingroup$ 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. $\endgroup$ – Alex R. Jun 5 '12 at 1:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.