How would I express this as a linear combination?

Question

I want to express 1 as a linear combination of 51781 and 4655.

I have a lot of other problems that consist of finding a linear combination but I just need to know do one so then I will be able to do them all.

What steps do I need to take to understand how to solve this?

Would this be my answer?

51781 = 11*4655+576

4655 = 8*576+47

576 = 12*47+12

47 = 3*12+11

12 = 1*11+1

11= 1*11+0

I presume that you mean an integer linear combination. Do you know the Euclidean algorithm? — Brian M. Scott, Dec 08 '13 at 23:54
See my edited comment for the answer. I wrote out all the steps since you did more of the work. — Stoof, Dec 09 '13 at 00:27

Stoof · Answer 1 · 2013-12-09T00:26:54.370

Hint: Use

If $a = bq + r$,

$a,b,q,r \in \mathbb Z, a \not = 0$ and $b \not = 0$ then

$\gcd(a,b) = \gcd(b,r)$

Which will expand to:

\begin{align*} a &= bq_1 + r_1 && 0 \leq r_1 < b\\ b &= r_1q_2 + r_2 && 0 \leq r_2 < r_1\\ r_1 &= r_2q_3 + r_3 && 0 \leq r_3 < r_2\\ r_2 &= r_3q_4 + r_4 && 0 \leq r_4 < r_3\\ & \vdots && \vdots \end{align*}

So for your problem: \begin{align*} 51781 &= 4655(11) + 576\\ 4655 &= 576(8) + 47\\ \dots \end{align*}

Once you get to the end you can just substitute back in the steps:

\begin{align*} 1 &= 12 - 11\\ &= (576 - 12 \cdot 47) - (47 - 3 \cdot 12)\\ &= 576 - 12 \cdot 47 + 3 \cdot 12\\ &= 576 - 13 \cdot 47 + 3 ( 576 - 12 \cdot 47)\\ &= 4(576) - 49(47)\\ &= 4(51781 - 11\cdot4655) - 49(4655 - 8\cdot576)\\ &= 4(51781) - 93(4655) + 392(576)\\ &= 4(51781) - 93(4655) + 392(51781 - 11 \cdot 4655)\\ 1 &= 51781(396) + 4655(-4405) \end{align*}

So that is your linear combination. All you have to do is substitute the steps you did to find the gcd and you will have the linear combination.

Which is the euclidean algorithm: http://en.wikipedia.org/wiki/Euclidean_algorithm

score 3 · Answer 2 · answered Dec 08 '13 at 23:56

3

You should use the Extended Euclidean algorithm

answered Dec 08 '13 at 23:56

Abramo

6,917

score 0 · Answer 3 · answered Dec 09 '13 at 00:02

0

Hint: find gcd of both, and use Euclidean algorithm

answered Dec 09 '13 at 00:02

waj cheema

129
1
2
9

score 0 · Answer 4 · answered Dec 09 '13 at 00:04

As the other users mentioned, the key is the Euclidean algorithm. But I will add the following: if you have two integers $x,y$, and you're wondering if for a fixed integer $c$ there exists a linear combination of $x$ and $y$ such that $ax+by=c$, with $a,b$ integers, then this will happen if and only $\gcd(x,y)$ divides $c$.

This result has the following consequence: once you have found integers $a,b$ such that $51781a+4655b=1$, then you also know that $$c=c\cdot 1=c(51781a+4655b)=51781(ca)+4655(cb).$$

How would I express this as a linear combination?

4 Answers4