gcd
Greatest (positive) Common Divisor
Syntax
gpcd = gcd(P) [gpcd, U] = gcd(P)
Arguments
 P
array of decimal integers, encoded integers, or of polynomials.
 gpcd
single element of
P
type: the greatest common divisor of allP
components. U
Square matrix of the
P
type, with integer components or of minimal degrees. Its last columnB = U(:,$)
holds Bezout coefficients, such thatB(1)*P(1) + B(2)*P(2) + .... + B($)*P($) == gpcd
.
Description
[gpcd, U] = gcd(P)
computes the greatest common divisor
gpcd
of components of P
, and an unimodular matrix
U
.
If P
components are decimal or encoded integers, they are priorly
converted into int64
signed integers.
If P
has an unsigned inttype uint8
,
uint16
, uint32
or uint64
,
U
gets the corresponding signed inttype.
When P
are integers, the returned GCD is always positive.
When a second output is expected, an unimodular matrix U
of the
P
type is returned, such that
size(U) == [length(P) length(P)]
matrix(P,1,1)*U = [0...0 gpcd]
withlength(P)1
leading zerosdet(U)
is1
or1
.
Its last column provides Bezout coefficients.
gcd([0 0]) returns 0 . 
For big P values (smaller but of the order of 2^63, depending also
on the number of input values), results may be corrupted by integer overflow and
wrapping (int8(127)+1 == 128). 
Examples
// With polynomials s = %s; p = [s s*(s+1)^2 2*s^2+s^3]; [GCD, U] = gcd(p) p*U // With encoded integers V = uint16([2^2*3^5 2^3*3^2 2^2*3^4*5]) [GCD, U] = gcd(V) typeof(GCD) typeof(U) V*U // With decimal integers V = [2^2*3^5 2^3*3^2 2^2*3^4*5]; [GCD, U] = gcd(V) type(GCD) type(U) V*U gcd([0 60]) gcd([0 0])
See also
History
Version  Description 
6.0.1 

Report an issue  
<< factorial  Discrete mathematics  lcm >> 