100'  NAME--EUCLID
110'
120'  DESCRIPTION--FINDS THE GREATEST COMMON DIVISOR OF TWO INTEGERS,
130'  TOGETHER WITH THE WEIGHTING FACTORS BY WHICH THE GCD IS
140'  EXPRESSIONABLE AS A LINEAR COMBINATION OF THE TWO NUMBERS.
150'
160'  SOURCE--UNKNOWN
170'
180'  INSTRUCTIONS--ENTER PAIRS OF INTEGERS AS DATA IN 570 AND FOLLOWING.
190'
200'
210'  *  *  *  *  *  *  *   MAIN PROGRAM   *  *  *  *  *  *  *  *  *
220'
230   DIM Q(50),X(50),Y(50)
240 READ A,B
250 IF A>-1 THEN 270
260 GOTO 600
270 PRINT "NUMBERS :" A,
280 IF A > 999 THEN 300
290 PRINT " ",
300 PRINT B
310 FOR I = 0 TO 40
320  LET Q(I)=INT(A/B)
330  LET R=A-B*Q(I)
340  LET A=B
350  LET B=R
360  IF R=0 THEN 380
370  NEXT I
380 LET K=I-1
390 LET X(0)=1
400 LET X(1)=Q(1)
410 LET Y(0)=Q(0)
420 LET Y(1)=1+Q(0)*Q(1)
430 FOR I=2 TO K
440 LET X(I)=X(I-2)+X(I-1)*Q(I)
450 LET Y(I)=Y(I-2)+Y(I-1)*Q(I)
460 NEXT I
470 PRINT "WEIGHTS :"X(K)"   ",-Y(K)
480 PRINT "** GCD ** :" A;
490 IF A=1 THEN 530
500 PRINT
510 PRINT
520 GOTO 240
530 PRINT
540 PRINT "RELATIVELY PRIME"
550 PRINT
560 GOTO 240
570 DATA 144,200,1024,2048, 123,556
580 REM DATA IN 590 PART OF PROGRAM.
590 DATA -1,-1
600 END