use integer;

for (my $i=0;$i<20;$i++) {
    my ($a,$b) = (int(rand 101),int(rand 101));
    my ($d,$x,$y) = egcd($a,$b);
    print "$a*$x+$b*$y=$d\n";
}

sub egcd($$) {
    my ($a,$b) = @_;

    if ($a<$b) {
	my ($d,$y,$x) = egcd($b,$a);
	return ($d,$x,$y);
    }
    return ($a,1,0) if $b==0;
    my $k = $a/$b;
    my ($d,$x,$y) = egcd($a-$k*$b,$b);
    return ($d,$x,$y - $k*$x);
}