7.1.1 GCD
The gcd command finds the greatest common
divisor (GCD) of a set of integers or polynomials. (See also
Section 11.2.5 for polynomials.) It can be called with one or two
arguments.
-
gcd can take one argument:
seq, a sequence or list of integers or polynomials.
- gcd(seq) returns the GCD of the
elements of seq.
- Alternatively, gcd can take two arguments:
s and t, two lists of the same length containing integers or polynomials
(alternatively, a matrix m with two rows whose elements are
integers or polynomials).
- gcd(s,t) (or gcd(m)) returns
the list whose kth element is the GCD of the kth elements of s and
t (or the kth column of m).
The Gcd command is the inert form
of gcd; namely, it evaluates to gcd, for later evaluation.
Examples
With one argument:
With two arguments:
or:
| gcd([[6,10,12],[21,5,8]]) |
Find the greatest common divisor of 4n+1 and 5n+3 when n ∈
ℕ.
Then (in a program editor level):
| essai(n):={
local j,a,L;
L:=NULL;
for (j:=-n;j<n;j++) {
a:=f(j);
if (a!=1) {
L:=L,[j,a];
}
}
return L;
} |
Now:
|
| |
| ⎡
⎣ | −16,7 | ⎤
⎦ | , | ⎡
⎣ | −9,7 | ⎤
⎦ | , | ⎡
⎣ | −2,7 | ⎤
⎦ | ,
| ⎡
⎣ | 5,7 | ⎤
⎦ | , | ⎡
⎣ | 12,7 | ⎤
⎦ | , | ⎡
⎣ | 19,7 | ⎤
⎦ |
| | | | | | | | | | |
|
From this information, a reasonable conjecture would be that
gcd(4n+1,5n+3)=7 if n=7k−2 for some k ∈ ℤ and
gcd(4n+1,5n+3)=1 otherwise.
Since gcd(a,b)=gcd(a,b−c a) for integers a, b and c;
we have gcd(4n+1,5n+3)=gcd(4n+1,5n+3−(4n+1))=gcd(4n+1,n+2)=
gcd(4n+1−4(n+2),n+2)=gcd(−7,n+2)=gcd(7,n+2), and so
gcd(4n+1,5n+3)=7 if 7 divides n+2, namely n+2=7k or
n=7k−2, and gcd(4n+1,5n+3)=1 otherwise. This proves the
conjecture.
An inert form of GCD:
(See Section 9.1.1.)