Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have to find the greatest common divisor of $a=78$ and $b=132$.

I have worked out to

$$\begin{align} 132 & = 78 \times 1 + 54 \\ 78 & = 54 \times 1 + 24 \\ 54 & = 24 \times 2 + 6 \\ 24 & = 6 \times 4 + 0 \end{align}$$

and back substituted

$$\begin{align} 6 & = 54 - 24 \times 2 \\ & = 54 - (78 - 54) \times 2 \\ & = 3 \times 54 - 78 \times 2 \end{align}$$

However I don't seem to be able to work back to $132$ ?

Can someone explain / help?

share|improve this question
add comment

2 Answers

up vote 7 down vote accepted

As you've experienced first-hand, back-substitution is messy and can lead to errors. It's better to append an identity-augmented matrix to accumulate the Bezout identity as you compute the Euclidean remainder sequence, e.g. below (from an old post - tailored to your example)

For example, to solve  mx + ny = gcd(x,y) one begins with
two rows  [m   1    0], [n   0    1], representing the two
equations  m = 1m + 0n,  n = 0m + 1n. Then one executes
the Euclidean algorithm on the numbers in the first column,
doing the same operations in parallel on the other columns,

Here is an example:  d =  x(132) + y(78)  proceeds as:

                      in equation form    | in row form
                    ----------------------+------------
                   132 =  1(132) +  0(78) |132   1   0
                    78 =  0(132) +  1(78) | 78   0   1
 row1 -   row2  ->  54 =  1(132) -  1(78) | 54   1  -1
 row2 -   row3  ->  24 = -1(132) +  2(78) | 24  -1   2
 row3 - 2 row4  ->   6 =  3(132) -  5(78) |  6   3  -5
 row4 - 4 row5  ->   0 =-13(132) + 22(78) |  0 -13  22

Above the row operations are those resulting from applying
the Euclidean algorithm to the numbers in the first column,

        row1 row2 row3 row4 row5
namely: 132,  78,  54,  24,   6  = Euclidean remainder sequence
                    |    |
for example        54-2(24) = 6, the 3rd step in Euclidean algorithm

becomes:      row3 - 2 row4 = row5  on the identity-augmented matrix.

In effect we have row-reduced the first two rows to the last two.
The matrix effecting the reduction is in the bottom right corner.
It starts as the identity, and is multiplied by each elementary
row operation matrix, hence it accumulates the product of all
the row operations, namely:

       [  3  -5] [132  1  0]  =  [6   3  -5]
       [-13  22] [ 78  0  1]     [0 -13  22]

The 1st row is the particular  solution:  6 =  3 (132) - 5 (78)
The 2nd row is the homogeneous solution:  0 = -13(132) + 22(78),
so the general solution is any linear combination of the two:

       n row1 + m row2  ->  6n = (3n-13m) 132 + (22m-5n) 78

The same row/column reduction techniques tackle arbitrary
systems of linear Diophantine equations. Such techniques
generalize easily to similar coefficient rings possessing a
Euclidean algorithm, e.g. polynomial rings F[x] over a field, 
Gaussian integers Z[i]. There are many analogous interesting
methods, e.g. search on keywords: Hermite / Smith normal form, 
invariant factors, lattice basis reduction, continued fractions,
Farey fractions / mediants, Stern-Brocot tree / diatomic sequence.
share|improve this answer
    
wow, i didnt knew there is another way to work on GCD. –  optimus Apr 23 '11 at 9:37
add comment

From the first equation you have $54=132-78$.

By plugging this into the last one you get $6=3(132-78)-2\cdot78=3\cdot132-5\cdot78.$

share|improve this answer
    
ok, i got it. thank you –  optimus Apr 22 '11 at 13:10
add comment

Your Answer

 
discard

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.