Previous Up Next

2.6.2  GCD : gcd igcd

gcd or igcd denotes the gcd (greatest common divisor) of several integers (for polynomials see also 2.25.7).
gcd or igcd returns the GCD of all 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 lines), in this case gcd returns the greatest common divisor of the elements with same index (or of 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 have now to prove that :
if n!=5+k*7 (for k ∈ ℤ), 4n+1 and 5n+3 are mutually prime,
and
if n=5+k*7 (for k ∈ ℤ), the greatest common divisor of 4n+1 and 5n+3 is 7.


Previous Up Next