MATLAB Functions | Help Desk |
gcd
Greatest common divisor
G = gcd(A,B) [G,C,D] = gcd(A,B)
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.
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:
E * [a;b] = [g,0],where
g
is the greatest common divisor of a
and b
as returned by the command E
equals:
c d -b/g a/gIn the case where
a = 2
and b = 4
:
[g,c,d] = gcd(2,4) g = 2 c = 1 d = 0So that:
E = 1 0 -2 1In the next example, we solve for
x
and y
in the Diophantine equation 30x + 56y = 8
.
[g,c,d] = gcd(30,56) g = 2 c = -13 d = 7By the definition, for scalars
c
and d
:
30(-13) + 56(7) = 2
,
Multiplying through by 8/2:
Comparing this to the original equation, a solution can be read by inspection:30(-13
*4) + 56(7
*4) = 8
x = (-13*4) = -52; y = (7*4) = 28
lcm
Least common multiple
[1] Knuth, Donald, The Art of Computer Programming, Vol. 2, Addison-Wesley: Reading MA, 1973. Section 4.5.2, Algorithm X.