非负整数的一个子集S对于加法封闭

[（ヅ）]

已知这个集合所有元素的最大公约数为1

求证: 当某个整数足够大时，此整数一定是S的元素。即存在一个下界s > 0,当 x > s时，一定有x\in S

[TheMatrix]

已知这个集合所有元素的最大公约数为1

求证: 当某个整数足够大时，此整数一定是S的元素。即存在一个下界s > 0,当 x > s时，一定有x\in S

对加法封闭，那就是一个半群，semigroup。

已知这个子集元素没有公约数。

要证明的是从某个数开始往上的所有数都在这个子集中，也就是只有有限个正整数不在这个子集中。

。。。

[TheMatrix]

对加法封闭，那就是一个半群，semigroup。

已知这个子集元素没有公约数。

要证明的是从某个数开始往上的所有数都在这个子集中，也就是只有有限个正整数不在这个子集中。

。。。

先考虑两个生成元的情况。假设有两个数(a,b)互素，根据Bezout定理，它们可以组合出1这个数，那么它们的任意integer combination就可以生成全部整数集合。但是这里面有负系数的情况，如果子集S只对加法封闭的话，要排除负系数的情况。也就是要证明，当一个数足够大的时候，它一定有(a,b)的positive integer combination的表达。。。

[Caravel]

反证法行不行，假设无论多大的M, 都有更大是整数不属于集合，然后推出这个集合不封闭。

[YWY]

已知这个集合所有元素的最大公约数为1

求证: 当某个整数足够大时，此整数一定是S的元素。即存在一个下界s > 0,当 x > s时，一定有x\in S

Proof. It is not hard to see that there exists (finitely many) numbers s₁, ..., s_t in S such that their GCD is 1. So we have
1 = c₁s₁+ ...+ c_ts_t for some integers c₁, ..., c_t.
Consequently, for all integer k, we see
k = kc₁s₁+ ...+ kc_ts_t.

Now, fix any positive integer n in S. Let C = max{|nc₁|, ..., |nc_t|} and let s = Cs₁+ ...+ Cs_t, which is clearly in S. It suffices to show that s+k is in S for all k = 1, 2, ..., n-1; this is because the next number will be s+a, which is clearly in S; it then leads us the next cycle with similar arguments.

The claim that s+k is in S for all k = 1, 2, ..., n-1 follows from s = Cs₁+ ...+ Cs_t and the construction of C. (The key is that C is BIG ENOUGH.) More precisely, for all k = 1, 2, ..., n-1, we have
s + k = (C+kc₁)s₁+ ...+ (C+kc_t)s_t, which is clearly in S.

In summary, for the number s as chosen above, we have s + m in S for all m > 0. QED.

[nk]

Proof. It is not hard to see that there exists (finitely many) numbers s₁, ..., s_t in S such that their GCD is 1. So we have
1 = c₁s₁+ ...+ c_ts_t for some integers c₁, ..., c_t.
Consequently, for all integer k, we see
k = kc₁s₁+ ...+ kc_ts_t.

Now, fix any positive integer n in S. Let C = max{|nc₁|, ..., |nc_t|} and let s = Cs₁+ ...+ Cs_t, which is clearly in S. It suffices to show that s+k is in S for all k = 1, 2, ..., n-1; this is because the next number will be s+a, which is clearly in S; it then leads us the next cycle with similar arguments.

The claim that s+k is in S for all k = 1, 2, ..., n-1 follows from s = Cs₁+ ...+ Cs_t and the construction of C. (The key is that C is BIG ENOUGH.) More precisely, for all k = 1, 2, ..., n-1, we have
s + k = (C+kc₁)s₁+ ...+ (C+kc_t)s_t, which is clearly in S.

In summary, for the number s as chosen above, we have s + m in S for all m > 0. QED.

这个想法是对的，关键的是用 如果s₁, ..., s_t 的GCD 是1， 那么 1 = c₁s₁+ ...+ c_ts_t for some integers c₁, ..., c_t. （忘了这个定理的名字了，好像这个定理的证明使用 欧几里得辗转公式来证的）

我也打算这么做的，但没有去花时间去写出来。

[TheMatrix]

Proof. It is not hard to see that there exists (finitely many) numbers s₁, ..., s_t in S such that their GCD is 1. So we have
1 = c₁s₁+ ...+ c_ts_t for some integers c₁, ..., c_t.
Consequently, for all integer k, we see
k = kc₁s₁+ ...+ kc_ts_t.

Now, fix any positive integer n in S. Let C = max{|nc₁|, ..., |nc_t|} and let s = Cs₁+ ...+ Cs_t, which is clearly in S. It suffices to show that s+k is in S for all k = 1, 2, ..., n-1; this is because the next number will be s+a, which is clearly in S; it then leads us the next cycle with similar arguments.

The claim that s+k is in S for all k = 1, 2, ..., n-1 follows from s = Cs₁+ ...+ Cs_t and the construction of C. (The key is that C is BIG ENOUGH.) More precisely, for all k = 1, 2, ..., n-1, we have
s + k = (C+kc₁)s₁+ ...+ (C+kc_t)s_t, which is clearly in S.

In summary, for the number s as chosen above, we have s + m in S for all m > 0. QED.

你把我要找的positive integer combination的表达找到了。:)