MATLAB Function Reference |
Syntax
Description
G = gcd(A,B)
returns an array containing the greatest common divisors of the corresponding elements of integer arrays A
and B
. By convention, gcd(0,0)
returns a value of 0
; all other inputs return positive integers for G
.
[G,C,D] = gcd(A,B)
returns both the greatest common divisor array G
, and the arrays C
and D
, which satisfy the equation: A(i).*C(i) + B(i).*D(i) = G(i)
. These are useful for solving Diophantine equations and computing elementary Hermite transformations.
Examples
The first example involves elementary Hermite transformations.
For any two integers a
and b
there is a 2
-by-2
matrix E
with integer entries and determinant = 1
(a unimodular matrix) such that:
where g
is the greatest common divisor of a
and b
as returned by the command
[g,c,d] = gcd(a,b).
In the case where a = 2
and b = 4
:
In the next example, we solve for x
and y
in the Diophantine equation 30x + 56y = 8
.
By the definition, for scalars c
and d
:
Comparing this to the original equation, a solution can be read by inspection:
See Also
References
[1] Knuth, Donald, The Art of Computer Programming, Vol. 2, Addison-Wesley: Reading MA, 1973. Section 4.5.2, Algorithm X.
gcbo | gcf |
© 1994-2005 The MathWorks, Inc.