In linear combinations, the basic property is if there are two integer quantities, say $a$ and $d$, then any integer multiplied to the two will again lead to an integer; i.e. $ax + dy, \forall a,b,x,y \in \mathbb{Z} $ is also an integer. This is based on the closure of integers w.r.t. addition.
In g.c.d. computation of d = qa + r, with d(dividend), a(divisor), q(quotient), r(remainder), there may be many common divisors but if smaller than g.c.d., then not a linear combination of $a$ and $r$.
I am unable to make a proof for the above that is rigorous, as the below attempt shows the failure of my rigorous approach.
If $c$ is a common divisor of $d$ and $a$, then $d = nc, a = mc, \exists n,m \in \mathbb {Z}$. So, $d = qa + r => c(n-m) = r$. Also, $n \ge m$ as $d \ge a$.
So, $c\mid r$ also. Alternately, the divisibility of r by c can be derived by the linear combination: $r = d -qa$, i.e. if the linear combination $c\mid d$ & $c \mid qa$; then $c \mid (d -qa)$, and hence $c \mid r$.
Also, gcd will make use of two linear combinations at each step: (i) $d = qa + r$, (ii) $r = d - qa$. By (i), any common divisor $d^{'}$ of $a$ & $r$ is also a divisor of $d$. Similarly, by (ii) the same common divisor $d^{'}$ of $d$ and $a$ is also a divisor of $r$.
Answer
Let $g$ be the greatest common divisor of $a$ and $b$.
If $d=ax+by$ for some integers $x$ and $y$, then $g$ divides $d=ax+by$, and hence $g\le d$.
Hope this helps.
No comments:
Post a Comment