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

  • $\begingroup$ 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. $\endgroup$ – André Nicolas Dec 6 '12 at 19:37
  • $\begingroup$ @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 $\endgroup$ – Mat Dec 6 '12 at 19:47
  • $\begingroup$ 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? $\endgroup$ – André Nicolas Dec 6 '12 at 19:58
  • $\begingroup$ 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 :) $\endgroup$ – Mat Dec 6 '12 at 20:01
  • $\begingroup$ @AndréNicolas, as you have suggested I changed the notation in my question $\endgroup$ – 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'$.


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.