#!/usr/bin/perl -l

use strict;
use warnings;

my (@r, @t, @s);
my @q;
my $m = 1;

my $a = $ARGV[0];
my $b = $ARGV[1];

$r[0] = $a; $r[1] = $b;
$t[0] = 0; $t[1] = 1;
$s[0] = 1; $s[1] = 0;

while ($r[$m] != 0) {
	$q[$m] = int($r[$m-1] / $r[$m]);
	$r[$m+1] = $r[$m-1] - ($q[$m] * $r[$m]);
	$s[$m+1] = $s[$m-1] - ($q[$m] * $s[$m]);
	$t[$m+1] = $t[$m-1] - ($q[$m] * $t[$m]);

	printf ("%d*%d + %d*%d = %d\n", $s[$m], $a, $t[$m], $b, $r[$m]);
	$m++;
}

$m--;

print "gcd($a,$b) = $r[$m]";
my $result = $s[$m]*$a + $t[$m]*$b;
printf ("%d*%d + %d*%d = %d\n", $s[$m], $a, $t[$m], $b, $result);