6.5.1  GCD: gcd igcd Gcd

The gcd command finds the greatest common divisor (GCD) of a set of integers or polynomials. (See also Section 6.28.5 for polynomials.) It can be called with one or two arguments.
igcd is a synonym for gcd.

With one argument:

• gcd takes one argument:
  seq, a sequence or list of integers or polynomials.
• gcd(seq) returns the GCD of the elements of seq.

Examples.

• Input:
  gcd(18,15)
  Output:

  3

• Input:
  gcd(18,15,21,36)
  Output:

  3

• Input:
  gcd([18,15,21,36])
  Output:

  3

• Input:
  gcd(-5-12*i,11-10*i)
  Output:

  3+2 i

With two arguments:

• gcd takes 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).

Examples.

• Input:
  gcd([6,10,12],[21,5,8])
  or:
  gcd([[6,10,12],[21,5,8]])
  Output:

  ⎡ ⎣

  3,5,4

  ⎤ ⎦

• Find the greatest common divisor of 4n+1 and 5n+3 when n ∈ ℕ.
  Input:
  f(n):=gcd(4*n+1,5*n+3)
  then input:

  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;

  }

  then input:
  essai(20)
  Output:

  ⎡ ⎣

  −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.

The Gcd command is the inert form of gcd; namely, it evaluates to gcd, for later evaluation.

Examples.

• Input:
  Gcd(18,15)
  Output:

  gcd

  ⎛ ⎝

  18,15

  ⎞ ⎠

• Input:
  eval(Gcd(18,15))
  Output:

  3

  (See Section 6.12.1.)