Previous Up Next

5.6.2  GCD : gcd igcd

gcd or igcd denotes the gcd (greatest common divisor) of several integers (for polynomials, see also 5.26.7).
gcd or igcd returns the GCD of integers.
Input :

gcd(18,15)

Output :

3

Input :

gcd(18,15,21,36)

Output :

3

Input :

gcd([18,15,21,36])

Output :

3

We can also put as parameters two lists of same size (or a matrix with 2 rows), in this case gcd returns the greatest common divisor of the elements with same index (or in the same column).
Input :

gcd([6,10,12],[21,5,8])

or :

gcd([[6,10,12],[21,5,8]])

Output :

[3,5,4]

An example
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]

So we now have to prove that :
If n≠5+k*7 (for k ∈ ℤ), 4n+1 and 5n+3 are mutually prime, and n=5+k*7 (for k ∈ ℤ), then the greatest common divisor of 4n+1 and 5n+3 is 7.


Previous Up Next