C     ALGORITHM 386 COLLECTED ALGORITHMS FROM ACM.
C     ALGORITHM APPEARED IN COMM. ACM, VOL. 13, NO. 07,
C     P. 447.
      SUBROUTINE GCDN
     *  (N,A,Z,IGCD)
C   N     NUMBER OF INTEGERS
C   A(I)  INPUT ARRAY OF N INTEGERS, A(I) IS USED AS WORKING STORAGE,
C         INPUT IS DESTROYED
C   Z(I)  OUTPUT ARRAY OF N MULTIPLIERS
C   IGCD  OUTPUT, GREATEST COMMON DIVISOR OF THE A(I) INTEGERS
C
      DIMENSION A(50),Z(50)
      INTEGER A,Z,C1,C2,Y1,Y2,Q
C FIND FIRST NON-ZERO INTEGER
      DO 1 M = 1,N
      IF(A(M) .NE.0) GO TO 3
    1 Z(M)=0
C ALL ZERO INPUT RESULTS IN ZERO GCD AND ALL ZERO MULTIPLIERS
      IGCD=0
      RETURN
C IF LAST NUMBER IS THE ONLY NON-ZERO NUMBER, EXIT IMMEDIATELY
    3 IF(M.NE.N) GO TO 4
      IGCD=A(M)
      Z(M)=1
      RETURN
    4 MP1= M+1
      MP2= M+2
C CHECK THE SIGN OF A(M)
      ISIGN=0
      IF(A(M).GE.0) GO TO 5
      ISIGN=1
      A(M)=-A(M)
C CALCULATE GCD VIA N-1 APPLICATIONS OF THE GCD ALGORITHM FOR TWO
C INTEGERS. SAVE THE MULTIPLIERS.
    5 C1= A(M)
      DO 30 I=MP1,N
      IF(A(I).NE.0) GO TO 7
      A(I) = 1
      Z(I)= 0
      GO TO 25
    7 Y1=1
      Y2=0
      C2=IABS(A(I))
   10 Q= C2/C1
      C2= C2-Q*C1
C TESTING BEFORE COMPUTING Y2 AND BEFORE COMPUTING Y1 BELOW SAVES N-1
C ADDITIONS AND N-1 MULTIPLICATIONS.
      IF(C2.EQ.0) GO TO 20
      Y2= Y2-Q*Y1
      Q =C1/C2
      C1 = C1- Q*C2
      IF(C1.EQ.0) GO TO 15
      Y1 = Y1 - Q*Y2
      GO TO 10
   15 C1 = C2
      Y1 = Y2
   20 Z(I)= (C1 - Y1*A(M))/A(I)
      A(I)=Y1
      A(M)=C1
C TERMINATE GCD CALCULATIONS IF GCD EQUALS ONE.
   25 IF(C1.EQ.1) GO TO 60
   30 CONTINUE
   40 IGCD=A(M)
C CALCULATE MULTIPLIERS
      DO 50 J= MP2,I
      K = I-J+2
      KK=K+1
      Z(K)=Z(K)*A(KK)
   50 A(K)=A(K)*A(KK)
      Z(M)=A(MP1)
      IF(ISIGN.EQ.0) GO TO 100
      Z(M)=-Z(M)
  100 RETURN
C GCD FOUND, SET REMAINDER OF THE MULTIPLIERS EQUAL TO ZERO.
   60 IP1= I+1
      DO 65 J= IP1,N
   65 Z(J) =0
      GO TO 40
      END