# gcd as positive linear combination

Good evening,

I have a question concerning the euclidean algorithm.

One knows that for $a_1 , \ldots , a_n \in \mathbb{N}$ and $k\in \mathbb{N}$ there exist some $\lambda_i \in \mathbb{Z}$ such that :

$$\gcd(a_1, \ldots, a_n) = \frac{1}{k}\sum_{i=1}^n \lambda_i a_i$$

Here is my question: can one find a $m_0 \in \mathbb{N}$ that for every $m \geq m_0$ there are scalars $\mu_i \in \mathbb{N}$ such that:

$$\gcd(a_1, \ldots , a_n) = \frac{1}{m}\sum_{i=1}^n \mu_i a_i$$

Unfortunately I have only very rudimentary knowledge about number theory ...

With best regards Mat

• This cannot be. The $\gcd$ of the $n$ numbers $2,3,4,\dots,n+1$ is equal to $1$, but no linear combination of these $n$ numbers, with non-negative integer coefficients, can be $1$. But you may have another question in mind. – André Nicolas Dec 6 '12 at 19:37
• @AndréNicolas , well if you read the question carefully I asked for a positive linear combination which sums up to $k \text{GCD}(a_1,..., a_n)$ and $k\in\mathbb{N}$. With best regards Mat – Mat Dec 6 '12 at 19:47
• Well, I read the question carefully, and it said for $a_1,\dots$ and $k$, there exist $\dots$. So as far as the language of the question goes, the $a_i$ and $k$ are specified. That's why I suggested you might have another question in mind, such as. Maybe there exist* $k$. And is the $k$ early in the question connected to the $k$ towards the end? – André Nicolas Dec 6 '12 at 19:58
• Hello @AndréNicolas! Ok, may be my formulation is not very precise (sorry about that). This is what I meant: We know: For every choice of $a_1 , ... , a_n, k \in \mathbb{N}$ we can find $\lambda_i \in \mathbb{Z}$ such that : GCD($a_1, ... , a_n$) = $\frac{1}{{k}}\sum_{i=1}^n \lambda_i a_i$. Question: Does an integer $k_0 \in \mathbb{N}$ exist that for every $k > k_0$ one can find $\lambda_i \in \mathbb{N}$ such that GCD($a_1, ... , a_n$) = $\frac{1}{{k}}\sum_{i=1}^n \lambda_i a_i$ ? I hope I got it right this time :) – Mat Dec 6 '12 at 20:01
• @AndréNicolas, as you have suggested I changed the notation in my question – Mat Dec 6 '12 at 20:13

Let's say that $\gcd(a_1,\ldots,a_n)=d$ and $d=\displaystyle{\sum_{i=1}^{n}\lambda_ia_i}$ for some $\lambda_i\in \mathbb Z$.
Suppose that $s_i\in \mathbb N$ are sufficiently large such that $r_i=\lambda_i+s_ia_1a_2\ldots a_{i-1}a_{i+1}\ldots a_n>\dfrac{a_1}{d}|\lambda_i|$ and $\displaystyle{\sum_{i=1}^{n}r_ia_i}=m_0d$ for some $m_0\in \mathbb N$.
For all $r=0,1,\ldots,\dfrac{a_1}{d}-1$ we have $$(m_0+r)d=\displaystyle{\sum_{i=1}^{n}(r_i+r\lambda_i)a_i}$$ and $r_i+r\lambda_i>0$ for all $i.$
For $r\geq\dfrac{a_1}{d}$ if $r=q\dfrac{a_1}{d}+s$ with $q \in \mathbb N, \ s\in\left\{0,1,\ldots,\dfrac{a_1}{d}-1\right\}$ we have $$(m_0+r)d=(r_1+s\lambda_1+q)a_1+\displaystyle{\sum_{i=2}^{n}(r_i+s\lambda_i)a_i}$$ and $r_1+s\lambda_1+q>0, \ r_i+s\lambda_i>0$ for all $i\geq2.$
Therefore for every $m\geq m_o,\ \ md=\displaystyle{\sum_{i=1}^{n}\mu_i a_i}\Rightarrow d=\displaystyle{\frac{1}{m}\sum_{i=1}^{n}\mu_i a_i}$ for some $\mu_i\in \mathbb N$.

Recall that if $a$ and $b$ are relatively prime positive integers, and $w\gt ab$, then the linear Diophantine equation has a solution $(x,y)$ with $x$ and $y$ positive if $w\gt ab$.

Now suppose that $a$ and $b$ are not necessarily relatively prime, and let $d=\gcd(a,b)$. Let $a=d_a_1$ and $b=db_1$. If $m\gt a_1b_1$, then there exist positive integers $x$ and $y$ such that $a_1x+b_1y=m$. Multiplying by $d$, we find that $d=ax+by$, or equivalently $d=\frac{1}{m}(ax+by)$.

So in the case $n=2$, we can take $m_0=a_1b_1$.

For general $n$, the same procedure applies. Let $a_1,\dots,a_n$ be positive integers, with $\gcd$ equal to $d$, and let $a_i'=a_i/d$. One can show that every integer $\gt \prod_{i=1}^n a_i'$ is a positive linear combination of the $a_i'$.