use integer;

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

    if ($a % $d == 0) {
	my $u = ($a/$d)*$x;
	my $b_u = $b*$u;
	print "   u=$u, $b*$u=$b_u=$a (mod $n)\n";
    } else {
	print "   gcd($n,$b)=$d, does not divide $a, no solution\n";
    }
}

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

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