Logged In: YES 
user_id=31435

Changed Resolution to None since this was opened again.

I still don't like this.  It's a wart no matter how you cut 
it:  implement the egcd meaning, and it's still a wart, 
because the "multiplicative inverse" meaning doesn't always 
make sense.  For example, pow(4, -1, 6) -- 4 has no 
multiplicative inverse mod 6.  The best it can return is 2, 
i.e. the best pow(i, -1, k) can return is an integer x s.t. 
i*x is congruent to gcd(i, k) mod k.  But Python provides 
no way to get the gcd, so there's no way (short of 
computing gcd separately) to know what the result of pow
(i, -1, k) really means (and it doesn't mean "inverse" 
unless the gcd is 1; OTOH, raise an exception if the gcd 
isn't one, and then you've artificially ruled out 
legitimate uses of egcd apparently not related to Paul's 
particular interest today).

The natural way to spell egcd as a library routine would 
return the gcd too; e.g.,

def egcd(aorig, borig):
.    """Return (g, i) s.t. g=gcd(aorig, borig) and i*aorig 
% borig = g."""
.    a, b = aorig, borig
.    a1, a2 = 1, 0
.    while b:
.        q, r = divmod(a, b)
.        a1, a2 = a2, a1-q*a2
.        a, b = b, r
.    if __debug__:
.        b1, r = divmod(a - a1*aorig, borig)
.        assert r == 0
.        assert a1*aorig + b1*borig == a
.    return a, a1