I like the idea of having some integer math functions like this in the
stdlib; whether in the math module or elsewhere doesn't matter much.  In
particular I remember having to implement xgcd on several separate
occasions for unrelated applications, each time requiring about the same
head scratching as before, and wishing it was in the stdlib so that
could be avoided.  This type of function is complicated enough to not
rattle immediately off the fingertips, but not complicated enough to be
worth looking up in a reference book.

http://bugs.python.org/issue457066 has some discussion of xgcd and
modular inverses.