Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 3 down vote accepted

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$.

share|cite|improve this answer

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'$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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