How to show that $gcd(a_1,a_2,cdots,a_k) = 1$ implies that there exist a non-negative solution to...












4














I was reading about the Coin-problem and I am unable to fully understand the following argument:




On the other hand, whenever the GCD equals 1, the set of integers that cannot be expressed as a conical combination of ${ a_1, a_2, …, a_n }$ is bounded according to Schur's theorem, and therefore the Frobenius number exists.




Here the author is arguing for the existence of a non-negative solution to the linear Diophantine equation (LDE)
$$sum_{i=1}^{k}a_ix_i =n text{}$$
for large enough $n.$ Now I tried to understand the proof of the Schur theorem here enter link description here (Page 98), but I am not sure that I understand it fully. In particular, I don't understand why the generating function associated with the sequence $h_n$ that counts the number of solutions to the LDE is
$$H(x)= prod_{i=1}^{k}left(frac{1}{1-x^{a_i}}right).$$



Once we have $H(x)$ we can deduce that
$$h_nsim frac{n^{k−1}}{(k − 1)!a_1a_2 ··· a_k}$$
as $nto infty.$ How does this exactly show that for large enough $n,$ $h_n>0?$ Is it because the $frac{n^{k−1}}{(k − 1)!a_1a_2 ··· a_k}>0?$










share|cite|improve this question




















  • 2




    Yes.$phantom{}$
    – Jack D'Aurizio
    yesterday






  • 3




    Consider just the case $k=2,a_1=3,a_2=7$ for clarity. Can you see that the coefficient of $x^n$ in $$(1+x^3+x^6+x^9+ldots)(1+x^7+x^{14}+x^{21}+ldots)$$ is exactly the number of ways for writing $n$ as $3A+7B$?
    – Jack D'Aurizio
    yesterday








  • 1




    Well, by geometric series $(1+x^3+x^6+ldots)=frac{1}{1-x^3}$ and $(1+x^7+x^{14}+ldots)=frac{1}{1-x^7}$.
    – Jack D'Aurizio
    yesterday






  • 2




    The meromorphic function $frac{1}{(1-x^3)(1-x^7)}$ has a double pole at $x=1$ but the other singularities are all simple poles. Any simple pole provides a bounded contribution, since the coefficients of $frac{1}{1-xxi}$ have unit modulus for $xiin S^1$, hence the magnitude of the representation function is linear, since $[x^n]frac{1}{(1-x)^2}=Theta(n)$.
    – Jack D'Aurizio
    yesterday








  • 1




    Linear and with a bounded perturbation implies strictly positive from some point on - the hidden constant in $Theta$ is not really important, but it can be derived from stars and bars.
    – Jack D'Aurizio
    yesterday


















4














I was reading about the Coin-problem and I am unable to fully understand the following argument:




On the other hand, whenever the GCD equals 1, the set of integers that cannot be expressed as a conical combination of ${ a_1, a_2, …, a_n }$ is bounded according to Schur's theorem, and therefore the Frobenius number exists.




Here the author is arguing for the existence of a non-negative solution to the linear Diophantine equation (LDE)
$$sum_{i=1}^{k}a_ix_i =n text{}$$
for large enough $n.$ Now I tried to understand the proof of the Schur theorem here enter link description here (Page 98), but I am not sure that I understand it fully. In particular, I don't understand why the generating function associated with the sequence $h_n$ that counts the number of solutions to the LDE is
$$H(x)= prod_{i=1}^{k}left(frac{1}{1-x^{a_i}}right).$$



Once we have $H(x)$ we can deduce that
$$h_nsim frac{n^{k−1}}{(k − 1)!a_1a_2 ··· a_k}$$
as $nto infty.$ How does this exactly show that for large enough $n,$ $h_n>0?$ Is it because the $frac{n^{k−1}}{(k − 1)!a_1a_2 ··· a_k}>0?$










share|cite|improve this question




















  • 2




    Yes.$phantom{}$
    – Jack D'Aurizio
    yesterday






  • 3




    Consider just the case $k=2,a_1=3,a_2=7$ for clarity. Can you see that the coefficient of $x^n$ in $$(1+x^3+x^6+x^9+ldots)(1+x^7+x^{14}+x^{21}+ldots)$$ is exactly the number of ways for writing $n$ as $3A+7B$?
    – Jack D'Aurizio
    yesterday








  • 1




    Well, by geometric series $(1+x^3+x^6+ldots)=frac{1}{1-x^3}$ and $(1+x^7+x^{14}+ldots)=frac{1}{1-x^7}$.
    – Jack D'Aurizio
    yesterday






  • 2




    The meromorphic function $frac{1}{(1-x^3)(1-x^7)}$ has a double pole at $x=1$ but the other singularities are all simple poles. Any simple pole provides a bounded contribution, since the coefficients of $frac{1}{1-xxi}$ have unit modulus for $xiin S^1$, hence the magnitude of the representation function is linear, since $[x^n]frac{1}{(1-x)^2}=Theta(n)$.
    – Jack D'Aurizio
    yesterday








  • 1




    Linear and with a bounded perturbation implies strictly positive from some point on - the hidden constant in $Theta$ is not really important, but it can be derived from stars and bars.
    – Jack D'Aurizio
    yesterday
















4












4








4







I was reading about the Coin-problem and I am unable to fully understand the following argument:




On the other hand, whenever the GCD equals 1, the set of integers that cannot be expressed as a conical combination of ${ a_1, a_2, …, a_n }$ is bounded according to Schur's theorem, and therefore the Frobenius number exists.




Here the author is arguing for the existence of a non-negative solution to the linear Diophantine equation (LDE)
$$sum_{i=1}^{k}a_ix_i =n text{}$$
for large enough $n.$ Now I tried to understand the proof of the Schur theorem here enter link description here (Page 98), but I am not sure that I understand it fully. In particular, I don't understand why the generating function associated with the sequence $h_n$ that counts the number of solutions to the LDE is
$$H(x)= prod_{i=1}^{k}left(frac{1}{1-x^{a_i}}right).$$



Once we have $H(x)$ we can deduce that
$$h_nsim frac{n^{k−1}}{(k − 1)!a_1a_2 ··· a_k}$$
as $nto infty.$ How does this exactly show that for large enough $n,$ $h_n>0?$ Is it because the $frac{n^{k−1}}{(k − 1)!a_1a_2 ··· a_k}>0?$










share|cite|improve this question















I was reading about the Coin-problem and I am unable to fully understand the following argument:




On the other hand, whenever the GCD equals 1, the set of integers that cannot be expressed as a conical combination of ${ a_1, a_2, …, a_n }$ is bounded according to Schur's theorem, and therefore the Frobenius number exists.




Here the author is arguing for the existence of a non-negative solution to the linear Diophantine equation (LDE)
$$sum_{i=1}^{k}a_ix_i =n text{}$$
for large enough $n.$ Now I tried to understand the proof of the Schur theorem here enter link description here (Page 98), but I am not sure that I understand it fully. In particular, I don't understand why the generating function associated with the sequence $h_n$ that counts the number of solutions to the LDE is
$$H(x)= prod_{i=1}^{k}left(frac{1}{1-x^{a_i}}right).$$



Once we have $H(x)$ we can deduce that
$$h_nsim frac{n^{k−1}}{(k − 1)!a_1a_2 ··· a_k}$$
as $nto infty.$ How does this exactly show that for large enough $n,$ $h_n>0?$ Is it because the $frac{n^{k−1}}{(k − 1)!a_1a_2 ··· a_k}>0?$







combinatorics number-theory generating-functions additive-combinatorics formal-power-series






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited yesterday









Batominovski

33.9k33292




33.9k33292










asked yesterday









Hello_World

3,90821630




3,90821630








  • 2




    Yes.$phantom{}$
    – Jack D'Aurizio
    yesterday






  • 3




    Consider just the case $k=2,a_1=3,a_2=7$ for clarity. Can you see that the coefficient of $x^n$ in $$(1+x^3+x^6+x^9+ldots)(1+x^7+x^{14}+x^{21}+ldots)$$ is exactly the number of ways for writing $n$ as $3A+7B$?
    – Jack D'Aurizio
    yesterday








  • 1




    Well, by geometric series $(1+x^3+x^6+ldots)=frac{1}{1-x^3}$ and $(1+x^7+x^{14}+ldots)=frac{1}{1-x^7}$.
    – Jack D'Aurizio
    yesterday






  • 2




    The meromorphic function $frac{1}{(1-x^3)(1-x^7)}$ has a double pole at $x=1$ but the other singularities are all simple poles. Any simple pole provides a bounded contribution, since the coefficients of $frac{1}{1-xxi}$ have unit modulus for $xiin S^1$, hence the magnitude of the representation function is linear, since $[x^n]frac{1}{(1-x)^2}=Theta(n)$.
    – Jack D'Aurizio
    yesterday








  • 1




    Linear and with a bounded perturbation implies strictly positive from some point on - the hidden constant in $Theta$ is not really important, but it can be derived from stars and bars.
    – Jack D'Aurizio
    yesterday
















  • 2




    Yes.$phantom{}$
    – Jack D'Aurizio
    yesterday






  • 3




    Consider just the case $k=2,a_1=3,a_2=7$ for clarity. Can you see that the coefficient of $x^n$ in $$(1+x^3+x^6+x^9+ldots)(1+x^7+x^{14}+x^{21}+ldots)$$ is exactly the number of ways for writing $n$ as $3A+7B$?
    – Jack D'Aurizio
    yesterday








  • 1




    Well, by geometric series $(1+x^3+x^6+ldots)=frac{1}{1-x^3}$ and $(1+x^7+x^{14}+ldots)=frac{1}{1-x^7}$.
    – Jack D'Aurizio
    yesterday






  • 2




    The meromorphic function $frac{1}{(1-x^3)(1-x^7)}$ has a double pole at $x=1$ but the other singularities are all simple poles. Any simple pole provides a bounded contribution, since the coefficients of $frac{1}{1-xxi}$ have unit modulus for $xiin S^1$, hence the magnitude of the representation function is linear, since $[x^n]frac{1}{(1-x)^2}=Theta(n)$.
    – Jack D'Aurizio
    yesterday








  • 1




    Linear and with a bounded perturbation implies strictly positive from some point on - the hidden constant in $Theta$ is not really important, but it can be derived from stars and bars.
    – Jack D'Aurizio
    yesterday










2




2




Yes.$phantom{}$
– Jack D'Aurizio
yesterday




Yes.$phantom{}$
– Jack D'Aurizio
yesterday




3




3




Consider just the case $k=2,a_1=3,a_2=7$ for clarity. Can you see that the coefficient of $x^n$ in $$(1+x^3+x^6+x^9+ldots)(1+x^7+x^{14}+x^{21}+ldots)$$ is exactly the number of ways for writing $n$ as $3A+7B$?
– Jack D'Aurizio
yesterday






Consider just the case $k=2,a_1=3,a_2=7$ for clarity. Can you see that the coefficient of $x^n$ in $$(1+x^3+x^6+x^9+ldots)(1+x^7+x^{14}+x^{21}+ldots)$$ is exactly the number of ways for writing $n$ as $3A+7B$?
– Jack D'Aurizio
yesterday






1




1




Well, by geometric series $(1+x^3+x^6+ldots)=frac{1}{1-x^3}$ and $(1+x^7+x^{14}+ldots)=frac{1}{1-x^7}$.
– Jack D'Aurizio
yesterday




Well, by geometric series $(1+x^3+x^6+ldots)=frac{1}{1-x^3}$ and $(1+x^7+x^{14}+ldots)=frac{1}{1-x^7}$.
– Jack D'Aurizio
yesterday




2




2




The meromorphic function $frac{1}{(1-x^3)(1-x^7)}$ has a double pole at $x=1$ but the other singularities are all simple poles. Any simple pole provides a bounded contribution, since the coefficients of $frac{1}{1-xxi}$ have unit modulus for $xiin S^1$, hence the magnitude of the representation function is linear, since $[x^n]frac{1}{(1-x)^2}=Theta(n)$.
– Jack D'Aurizio
yesterday






The meromorphic function $frac{1}{(1-x^3)(1-x^7)}$ has a double pole at $x=1$ but the other singularities are all simple poles. Any simple pole provides a bounded contribution, since the coefficients of $frac{1}{1-xxi}$ have unit modulus for $xiin S^1$, hence the magnitude of the representation function is linear, since $[x^n]frac{1}{(1-x)^2}=Theta(n)$.
– Jack D'Aurizio
yesterday






1




1




Linear and with a bounded perturbation implies strictly positive from some point on - the hidden constant in $Theta$ is not really important, but it can be derived from stars and bars.
– Jack D'Aurizio
yesterday






Linear and with a bounded perturbation implies strictly positive from some point on - the hidden constant in $Theta$ is not really important, but it can be derived from stars and bars.
– Jack D'Aurizio
yesterday












2 Answers
2






active

oldest

votes


















0














A simple approach to the title:



Thanks to Bezout, there is some (not necessarily) integer combination of the $a_i$s that makes $1$. Add a large enough multiple of $a_1$ to each coefficient to make it non-negative and call the sum $k$; we have $kequiv 1 pmod{a_1}$.



Now any number $ge ka_1$ is a non-negative combination of the $a_i$s. Namely, let $n$ be the desired number, and let $m=nbmod a_1$. Then $mk$ is a positive combination, and we can add some multiple of $a_1$ to make it $n$ instead, since $mkequiv npmod{a_1}$ and $mk<n$ because $m<a_1$.






share|cite|improve this answer























  • How do you get the coefficients all integers though? I see that $k=sum c_ia_i$ where each $c_i$ is rational....
    – Mike
    2 hours ago










  • *nonegative rational
    – Mike
    2 hours ago










  • @Mike: It's a generalization of Bézout's identity. (How would they become non-integral?)
    – Henning Makholm
    2 hours ago












  • Ahh. Gotcha. That makes sense. BUT, there is a direct way to show all this though, without having to refer to Bezout's indentity--my answer above. [I did just edit it for clarity ]
    – Mike
    2 hours ago












  • @Mike: Your "direct way" seems to look a lot longer than mine, though.
    – Henning Makholm
    2 hours ago



















0














We first do this for $k =2$.



LEt us assume WLOG that $a_1 < a_2$. If gcd$(a_1,a_2)=1$ then $a_2 mod a_1 in left(mathbb{Z}/a_1 mathbb{Z}right)^{times}$. So there exists a multiplicative inverse $m_2 in left(mathbb{Z}/a_1 mathbb{Z}right)^{times}$ of $a_2$; or equivalently, there exists a nonegative integer $m_2 < a_1$ such that $m_2 times a_2 equiv_{a_1} 1$. This implies the following: There exists integers $m_2$ and $m_1$; $|m_2| < a_1$ and so $|m_1| leq a_2+1$ such that $m_2a_2 = 1 + m_1a_1$, or equivalently, $m_2a_2-m_1a_1 = 1$.



So let $y$ be a sufficiently large integer, and let $k in {0,1,ldots, a_1-1}$ be such that $Na_1 + k = y$. Then $Na_1 +k(m_2a_2-m_1a_1) = y$, and
$N-km_1$ is positive if $N > km_1$, where $k < a_1$ and $m_1 leq a_2+1$. This will hold if $y$ is at least $a_1(a_1+1)(a_2+1)$. This completes the case for $k=2$.



Having established this for $k=2$ we now use induction to show this holds for general $k$. In particular, let ${a_1,a_2,ldots, a_{k+1}}$ be a set of positive integers where the greatest common divisor is 1. We show using induction on $k$ that every integer $Y$ can be expressed $Y = sum_{i=1}^{k+1} M_ia_i$. To this end, let $c =$gcd$(a_k,a_{k+1})$. Then by induction, for any sufficiently large integer $y$, there are nonegative integers $M_k$ and $M_{k+1}$ such that $M_ka_k+M_{k+1}a_{k+1} = cy$. So pick $y$ sufficiently large such that gcd$(a_1,ldots, a_{k-1}, cy) = 1$; indeed any $y$ sufficiently large satisfying gcd$(a_1,ldots, a_{k-1}, y) = 1$ will do [make sure you see why], and there is indeed such a positive integer $y$ [make sure you see why].



Then by the inductive hypothesis for any sufficiently large integer $Y$ there exist nonegative integers $M_1,ldots, M_{k-1}, M_y$ such that
$cyM_y + sum_{i=1}^{k-1} M_ia_i = Y$, as $cy$ itself satisfies $cy = M_ka_k+M_{k+1}a_{k+1}$ the result follows.





ETA: HOWEVER, we do note that, setting $A = max {a_1,ldots, a_k}$ that we may assume WLOG that $k leq 1+log A$. Or more precisely, there is a subset $S$ of ${1,ldots, k}$ of cardinality $log A$ such that gcd${a_i; i in S}$ is 1. Then it would suffice to show that every significantly large number $Y$ can be written $Y=sum_{i in S} M_ia_i$ where each $M_i$ is a nonnegative integer.



Indeed, each $a_i$ can be written as a product of at most $log A$ primes. So we build a set $a_{i_1},a_{i_2},a_{i_l}; l leq 1+log A$ such that gcd${a_{i_1},ldots, a_{i_l}} = 1$. Let us assume that using induction, that gcd${a_{i_1},ldots, a_{i_j}}$ is a composite number that has at most $log A -j+1$ prime factors $p_1ldots p_{log A-j}$. Then there exists an $a_i$ such that at least one of $p_1,ldots, p_{log A-j+1}$ doesn't divide $a_i$. Then gcd${a_{i_1},ldots, a_{i_j}, a_i}$ is a composite number that has at most $log A -j$ prime factors.






share|cite|improve this answer























  • Editted for clarity. Caught a crucial typo!
    – Mike
    2 hours ago











Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3060106%2fhow-to-show-that-gcda-1-a-2-cdots-a-k-1-implies-that-there-exist-a-non-n%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes









0














A simple approach to the title:



Thanks to Bezout, there is some (not necessarily) integer combination of the $a_i$s that makes $1$. Add a large enough multiple of $a_1$ to each coefficient to make it non-negative and call the sum $k$; we have $kequiv 1 pmod{a_1}$.



Now any number $ge ka_1$ is a non-negative combination of the $a_i$s. Namely, let $n$ be the desired number, and let $m=nbmod a_1$. Then $mk$ is a positive combination, and we can add some multiple of $a_1$ to make it $n$ instead, since $mkequiv npmod{a_1}$ and $mk<n$ because $m<a_1$.






share|cite|improve this answer























  • How do you get the coefficients all integers though? I see that $k=sum c_ia_i$ where each $c_i$ is rational....
    – Mike
    2 hours ago










  • *nonegative rational
    – Mike
    2 hours ago










  • @Mike: It's a generalization of Bézout's identity. (How would they become non-integral?)
    – Henning Makholm
    2 hours ago












  • Ahh. Gotcha. That makes sense. BUT, there is a direct way to show all this though, without having to refer to Bezout's indentity--my answer above. [I did just edit it for clarity ]
    – Mike
    2 hours ago












  • @Mike: Your "direct way" seems to look a lot longer than mine, though.
    – Henning Makholm
    2 hours ago
















0














A simple approach to the title:



Thanks to Bezout, there is some (not necessarily) integer combination of the $a_i$s that makes $1$. Add a large enough multiple of $a_1$ to each coefficient to make it non-negative and call the sum $k$; we have $kequiv 1 pmod{a_1}$.



Now any number $ge ka_1$ is a non-negative combination of the $a_i$s. Namely, let $n$ be the desired number, and let $m=nbmod a_1$. Then $mk$ is a positive combination, and we can add some multiple of $a_1$ to make it $n$ instead, since $mkequiv npmod{a_1}$ and $mk<n$ because $m<a_1$.






share|cite|improve this answer























  • How do you get the coefficients all integers though? I see that $k=sum c_ia_i$ where each $c_i$ is rational....
    – Mike
    2 hours ago










  • *nonegative rational
    – Mike
    2 hours ago










  • @Mike: It's a generalization of Bézout's identity. (How would they become non-integral?)
    – Henning Makholm
    2 hours ago












  • Ahh. Gotcha. That makes sense. BUT, there is a direct way to show all this though, without having to refer to Bezout's indentity--my answer above. [I did just edit it for clarity ]
    – Mike
    2 hours ago












  • @Mike: Your "direct way" seems to look a lot longer than mine, though.
    – Henning Makholm
    2 hours ago














0












0








0






A simple approach to the title:



Thanks to Bezout, there is some (not necessarily) integer combination of the $a_i$s that makes $1$. Add a large enough multiple of $a_1$ to each coefficient to make it non-negative and call the sum $k$; we have $kequiv 1 pmod{a_1}$.



Now any number $ge ka_1$ is a non-negative combination of the $a_i$s. Namely, let $n$ be the desired number, and let $m=nbmod a_1$. Then $mk$ is a positive combination, and we can add some multiple of $a_1$ to make it $n$ instead, since $mkequiv npmod{a_1}$ and $mk<n$ because $m<a_1$.






share|cite|improve this answer














A simple approach to the title:



Thanks to Bezout, there is some (not necessarily) integer combination of the $a_i$s that makes $1$. Add a large enough multiple of $a_1$ to each coefficient to make it non-negative and call the sum $k$; we have $kequiv 1 pmod{a_1}$.



Now any number $ge ka_1$ is a non-negative combination of the $a_i$s. Namely, let $n$ be the desired number, and let $m=nbmod a_1$. Then $mk$ is a positive combination, and we can add some multiple of $a_1$ to make it $n$ instead, since $mkequiv npmod{a_1}$ and $mk<n$ because $m<a_1$.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited 16 hours ago

























answered 16 hours ago









Henning Makholm

238k16303538




238k16303538












  • How do you get the coefficients all integers though? I see that $k=sum c_ia_i$ where each $c_i$ is rational....
    – Mike
    2 hours ago










  • *nonegative rational
    – Mike
    2 hours ago










  • @Mike: It's a generalization of Bézout's identity. (How would they become non-integral?)
    – Henning Makholm
    2 hours ago












  • Ahh. Gotcha. That makes sense. BUT, there is a direct way to show all this though, without having to refer to Bezout's indentity--my answer above. [I did just edit it for clarity ]
    – Mike
    2 hours ago












  • @Mike: Your "direct way" seems to look a lot longer than mine, though.
    – Henning Makholm
    2 hours ago


















  • How do you get the coefficients all integers though? I see that $k=sum c_ia_i$ where each $c_i$ is rational....
    – Mike
    2 hours ago










  • *nonegative rational
    – Mike
    2 hours ago










  • @Mike: It's a generalization of Bézout's identity. (How would they become non-integral?)
    – Henning Makholm
    2 hours ago












  • Ahh. Gotcha. That makes sense. BUT, there is a direct way to show all this though, without having to refer to Bezout's indentity--my answer above. [I did just edit it for clarity ]
    – Mike
    2 hours ago












  • @Mike: Your "direct way" seems to look a lot longer than mine, though.
    – Henning Makholm
    2 hours ago
















How do you get the coefficients all integers though? I see that $k=sum c_ia_i$ where each $c_i$ is rational....
– Mike
2 hours ago




How do you get the coefficients all integers though? I see that $k=sum c_ia_i$ where each $c_i$ is rational....
– Mike
2 hours ago












*nonegative rational
– Mike
2 hours ago




*nonegative rational
– Mike
2 hours ago












@Mike: It's a generalization of Bézout's identity. (How would they become non-integral?)
– Henning Makholm
2 hours ago






@Mike: It's a generalization of Bézout's identity. (How would they become non-integral?)
– Henning Makholm
2 hours ago














Ahh. Gotcha. That makes sense. BUT, there is a direct way to show all this though, without having to refer to Bezout's indentity--my answer above. [I did just edit it for clarity ]
– Mike
2 hours ago






Ahh. Gotcha. That makes sense. BUT, there is a direct way to show all this though, without having to refer to Bezout's indentity--my answer above. [I did just edit it for clarity ]
– Mike
2 hours ago














@Mike: Your "direct way" seems to look a lot longer than mine, though.
– Henning Makholm
2 hours ago




@Mike: Your "direct way" seems to look a lot longer than mine, though.
– Henning Makholm
2 hours ago











0














We first do this for $k =2$.



LEt us assume WLOG that $a_1 < a_2$. If gcd$(a_1,a_2)=1$ then $a_2 mod a_1 in left(mathbb{Z}/a_1 mathbb{Z}right)^{times}$. So there exists a multiplicative inverse $m_2 in left(mathbb{Z}/a_1 mathbb{Z}right)^{times}$ of $a_2$; or equivalently, there exists a nonegative integer $m_2 < a_1$ such that $m_2 times a_2 equiv_{a_1} 1$. This implies the following: There exists integers $m_2$ and $m_1$; $|m_2| < a_1$ and so $|m_1| leq a_2+1$ such that $m_2a_2 = 1 + m_1a_1$, or equivalently, $m_2a_2-m_1a_1 = 1$.



So let $y$ be a sufficiently large integer, and let $k in {0,1,ldots, a_1-1}$ be such that $Na_1 + k = y$. Then $Na_1 +k(m_2a_2-m_1a_1) = y$, and
$N-km_1$ is positive if $N > km_1$, where $k < a_1$ and $m_1 leq a_2+1$. This will hold if $y$ is at least $a_1(a_1+1)(a_2+1)$. This completes the case for $k=2$.



Having established this for $k=2$ we now use induction to show this holds for general $k$. In particular, let ${a_1,a_2,ldots, a_{k+1}}$ be a set of positive integers where the greatest common divisor is 1. We show using induction on $k$ that every integer $Y$ can be expressed $Y = sum_{i=1}^{k+1} M_ia_i$. To this end, let $c =$gcd$(a_k,a_{k+1})$. Then by induction, for any sufficiently large integer $y$, there are nonegative integers $M_k$ and $M_{k+1}$ such that $M_ka_k+M_{k+1}a_{k+1} = cy$. So pick $y$ sufficiently large such that gcd$(a_1,ldots, a_{k-1}, cy) = 1$; indeed any $y$ sufficiently large satisfying gcd$(a_1,ldots, a_{k-1}, y) = 1$ will do [make sure you see why], and there is indeed such a positive integer $y$ [make sure you see why].



Then by the inductive hypothesis for any sufficiently large integer $Y$ there exist nonegative integers $M_1,ldots, M_{k-1}, M_y$ such that
$cyM_y + sum_{i=1}^{k-1} M_ia_i = Y$, as $cy$ itself satisfies $cy = M_ka_k+M_{k+1}a_{k+1}$ the result follows.





ETA: HOWEVER, we do note that, setting $A = max {a_1,ldots, a_k}$ that we may assume WLOG that $k leq 1+log A$. Or more precisely, there is a subset $S$ of ${1,ldots, k}$ of cardinality $log A$ such that gcd${a_i; i in S}$ is 1. Then it would suffice to show that every significantly large number $Y$ can be written $Y=sum_{i in S} M_ia_i$ where each $M_i$ is a nonnegative integer.



Indeed, each $a_i$ can be written as a product of at most $log A$ primes. So we build a set $a_{i_1},a_{i_2},a_{i_l}; l leq 1+log A$ such that gcd${a_{i_1},ldots, a_{i_l}} = 1$. Let us assume that using induction, that gcd${a_{i_1},ldots, a_{i_j}}$ is a composite number that has at most $log A -j+1$ prime factors $p_1ldots p_{log A-j}$. Then there exists an $a_i$ such that at least one of $p_1,ldots, p_{log A-j+1}$ doesn't divide $a_i$. Then gcd${a_{i_1},ldots, a_{i_j}, a_i}$ is a composite number that has at most $log A -j$ prime factors.






share|cite|improve this answer























  • Editted for clarity. Caught a crucial typo!
    – Mike
    2 hours ago
















0














We first do this for $k =2$.



LEt us assume WLOG that $a_1 < a_2$. If gcd$(a_1,a_2)=1$ then $a_2 mod a_1 in left(mathbb{Z}/a_1 mathbb{Z}right)^{times}$. So there exists a multiplicative inverse $m_2 in left(mathbb{Z}/a_1 mathbb{Z}right)^{times}$ of $a_2$; or equivalently, there exists a nonegative integer $m_2 < a_1$ such that $m_2 times a_2 equiv_{a_1} 1$. This implies the following: There exists integers $m_2$ and $m_1$; $|m_2| < a_1$ and so $|m_1| leq a_2+1$ such that $m_2a_2 = 1 + m_1a_1$, or equivalently, $m_2a_2-m_1a_1 = 1$.



So let $y$ be a sufficiently large integer, and let $k in {0,1,ldots, a_1-1}$ be such that $Na_1 + k = y$. Then $Na_1 +k(m_2a_2-m_1a_1) = y$, and
$N-km_1$ is positive if $N > km_1$, where $k < a_1$ and $m_1 leq a_2+1$. This will hold if $y$ is at least $a_1(a_1+1)(a_2+1)$. This completes the case for $k=2$.



Having established this for $k=2$ we now use induction to show this holds for general $k$. In particular, let ${a_1,a_2,ldots, a_{k+1}}$ be a set of positive integers where the greatest common divisor is 1. We show using induction on $k$ that every integer $Y$ can be expressed $Y = sum_{i=1}^{k+1} M_ia_i$. To this end, let $c =$gcd$(a_k,a_{k+1})$. Then by induction, for any sufficiently large integer $y$, there are nonegative integers $M_k$ and $M_{k+1}$ such that $M_ka_k+M_{k+1}a_{k+1} = cy$. So pick $y$ sufficiently large such that gcd$(a_1,ldots, a_{k-1}, cy) = 1$; indeed any $y$ sufficiently large satisfying gcd$(a_1,ldots, a_{k-1}, y) = 1$ will do [make sure you see why], and there is indeed such a positive integer $y$ [make sure you see why].



Then by the inductive hypothesis for any sufficiently large integer $Y$ there exist nonegative integers $M_1,ldots, M_{k-1}, M_y$ such that
$cyM_y + sum_{i=1}^{k-1} M_ia_i = Y$, as $cy$ itself satisfies $cy = M_ka_k+M_{k+1}a_{k+1}$ the result follows.





ETA: HOWEVER, we do note that, setting $A = max {a_1,ldots, a_k}$ that we may assume WLOG that $k leq 1+log A$. Or more precisely, there is a subset $S$ of ${1,ldots, k}$ of cardinality $log A$ such that gcd${a_i; i in S}$ is 1. Then it would suffice to show that every significantly large number $Y$ can be written $Y=sum_{i in S} M_ia_i$ where each $M_i$ is a nonnegative integer.



Indeed, each $a_i$ can be written as a product of at most $log A$ primes. So we build a set $a_{i_1},a_{i_2},a_{i_l}; l leq 1+log A$ such that gcd${a_{i_1},ldots, a_{i_l}} = 1$. Let us assume that using induction, that gcd${a_{i_1},ldots, a_{i_j}}$ is a composite number that has at most $log A -j+1$ prime factors $p_1ldots p_{log A-j}$. Then there exists an $a_i$ such that at least one of $p_1,ldots, p_{log A-j+1}$ doesn't divide $a_i$. Then gcd${a_{i_1},ldots, a_{i_j}, a_i}$ is a composite number that has at most $log A -j$ prime factors.






share|cite|improve this answer























  • Editted for clarity. Caught a crucial typo!
    – Mike
    2 hours ago














0












0








0






We first do this for $k =2$.



LEt us assume WLOG that $a_1 < a_2$. If gcd$(a_1,a_2)=1$ then $a_2 mod a_1 in left(mathbb{Z}/a_1 mathbb{Z}right)^{times}$. So there exists a multiplicative inverse $m_2 in left(mathbb{Z}/a_1 mathbb{Z}right)^{times}$ of $a_2$; or equivalently, there exists a nonegative integer $m_2 < a_1$ such that $m_2 times a_2 equiv_{a_1} 1$. This implies the following: There exists integers $m_2$ and $m_1$; $|m_2| < a_1$ and so $|m_1| leq a_2+1$ such that $m_2a_2 = 1 + m_1a_1$, or equivalently, $m_2a_2-m_1a_1 = 1$.



So let $y$ be a sufficiently large integer, and let $k in {0,1,ldots, a_1-1}$ be such that $Na_1 + k = y$. Then $Na_1 +k(m_2a_2-m_1a_1) = y$, and
$N-km_1$ is positive if $N > km_1$, where $k < a_1$ and $m_1 leq a_2+1$. This will hold if $y$ is at least $a_1(a_1+1)(a_2+1)$. This completes the case for $k=2$.



Having established this for $k=2$ we now use induction to show this holds for general $k$. In particular, let ${a_1,a_2,ldots, a_{k+1}}$ be a set of positive integers where the greatest common divisor is 1. We show using induction on $k$ that every integer $Y$ can be expressed $Y = sum_{i=1}^{k+1} M_ia_i$. To this end, let $c =$gcd$(a_k,a_{k+1})$. Then by induction, for any sufficiently large integer $y$, there are nonegative integers $M_k$ and $M_{k+1}$ such that $M_ka_k+M_{k+1}a_{k+1} = cy$. So pick $y$ sufficiently large such that gcd$(a_1,ldots, a_{k-1}, cy) = 1$; indeed any $y$ sufficiently large satisfying gcd$(a_1,ldots, a_{k-1}, y) = 1$ will do [make sure you see why], and there is indeed such a positive integer $y$ [make sure you see why].



Then by the inductive hypothesis for any sufficiently large integer $Y$ there exist nonegative integers $M_1,ldots, M_{k-1}, M_y$ such that
$cyM_y + sum_{i=1}^{k-1} M_ia_i = Y$, as $cy$ itself satisfies $cy = M_ka_k+M_{k+1}a_{k+1}$ the result follows.





ETA: HOWEVER, we do note that, setting $A = max {a_1,ldots, a_k}$ that we may assume WLOG that $k leq 1+log A$. Or more precisely, there is a subset $S$ of ${1,ldots, k}$ of cardinality $log A$ such that gcd${a_i; i in S}$ is 1. Then it would suffice to show that every significantly large number $Y$ can be written $Y=sum_{i in S} M_ia_i$ where each $M_i$ is a nonnegative integer.



Indeed, each $a_i$ can be written as a product of at most $log A$ primes. So we build a set $a_{i_1},a_{i_2},a_{i_l}; l leq 1+log A$ such that gcd${a_{i_1},ldots, a_{i_l}} = 1$. Let us assume that using induction, that gcd${a_{i_1},ldots, a_{i_j}}$ is a composite number that has at most $log A -j+1$ prime factors $p_1ldots p_{log A-j}$. Then there exists an $a_i$ such that at least one of $p_1,ldots, p_{log A-j+1}$ doesn't divide $a_i$. Then gcd${a_{i_1},ldots, a_{i_j}, a_i}$ is a composite number that has at most $log A -j$ prime factors.






share|cite|improve this answer














We first do this for $k =2$.



LEt us assume WLOG that $a_1 < a_2$. If gcd$(a_1,a_2)=1$ then $a_2 mod a_1 in left(mathbb{Z}/a_1 mathbb{Z}right)^{times}$. So there exists a multiplicative inverse $m_2 in left(mathbb{Z}/a_1 mathbb{Z}right)^{times}$ of $a_2$; or equivalently, there exists a nonegative integer $m_2 < a_1$ such that $m_2 times a_2 equiv_{a_1} 1$. This implies the following: There exists integers $m_2$ and $m_1$; $|m_2| < a_1$ and so $|m_1| leq a_2+1$ such that $m_2a_2 = 1 + m_1a_1$, or equivalently, $m_2a_2-m_1a_1 = 1$.



So let $y$ be a sufficiently large integer, and let $k in {0,1,ldots, a_1-1}$ be such that $Na_1 + k = y$. Then $Na_1 +k(m_2a_2-m_1a_1) = y$, and
$N-km_1$ is positive if $N > km_1$, where $k < a_1$ and $m_1 leq a_2+1$. This will hold if $y$ is at least $a_1(a_1+1)(a_2+1)$. This completes the case for $k=2$.



Having established this for $k=2$ we now use induction to show this holds for general $k$. In particular, let ${a_1,a_2,ldots, a_{k+1}}$ be a set of positive integers where the greatest common divisor is 1. We show using induction on $k$ that every integer $Y$ can be expressed $Y = sum_{i=1}^{k+1} M_ia_i$. To this end, let $c =$gcd$(a_k,a_{k+1})$. Then by induction, for any sufficiently large integer $y$, there are nonegative integers $M_k$ and $M_{k+1}$ such that $M_ka_k+M_{k+1}a_{k+1} = cy$. So pick $y$ sufficiently large such that gcd$(a_1,ldots, a_{k-1}, cy) = 1$; indeed any $y$ sufficiently large satisfying gcd$(a_1,ldots, a_{k-1}, y) = 1$ will do [make sure you see why], and there is indeed such a positive integer $y$ [make sure you see why].



Then by the inductive hypothesis for any sufficiently large integer $Y$ there exist nonegative integers $M_1,ldots, M_{k-1}, M_y$ such that
$cyM_y + sum_{i=1}^{k-1} M_ia_i = Y$, as $cy$ itself satisfies $cy = M_ka_k+M_{k+1}a_{k+1}$ the result follows.





ETA: HOWEVER, we do note that, setting $A = max {a_1,ldots, a_k}$ that we may assume WLOG that $k leq 1+log A$. Or more precisely, there is a subset $S$ of ${1,ldots, k}$ of cardinality $log A$ such that gcd${a_i; i in S}$ is 1. Then it would suffice to show that every significantly large number $Y$ can be written $Y=sum_{i in S} M_ia_i$ where each $M_i$ is a nonnegative integer.



Indeed, each $a_i$ can be written as a product of at most $log A$ primes. So we build a set $a_{i_1},a_{i_2},a_{i_l}; l leq 1+log A$ such that gcd${a_{i_1},ldots, a_{i_l}} = 1$. Let us assume that using induction, that gcd${a_{i_1},ldots, a_{i_j}}$ is a composite number that has at most $log A -j+1$ prime factors $p_1ldots p_{log A-j}$. Then there exists an $a_i$ such that at least one of $p_1,ldots, p_{log A-j+1}$ doesn't divide $a_i$. Then gcd${a_{i_1},ldots, a_{i_j}, a_i}$ is a composite number that has at most $log A -j$ prime factors.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited 2 hours ago

























answered 20 hours ago









Mike

3,089211




3,089211












  • Editted for clarity. Caught a crucial typo!
    – Mike
    2 hours ago


















  • Editted for clarity. Caught a crucial typo!
    – Mike
    2 hours ago
















Editted for clarity. Caught a crucial typo!
– Mike
2 hours ago




Editted for clarity. Caught a crucial typo!
– Mike
2 hours ago


















draft saved

draft discarded




















































Thanks for contributing an answer to Mathematics Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3060106%2fhow-to-show-that-gcda-1-a-2-cdots-a-k-1-implies-that-there-exist-a-non-n%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

Mario Kart Wii

What does “Dominus providebit” mean?

Antonio Litta Visconti Arese