3
$\begingroup$

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

  • 0
    @MichaelHardy Thank you, I will keep that in mind.2012-12-06

2 Answers 2

3

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

1

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