Here is a patch which addresses both Mark's suggestions.

* math.gcd() now work with arbitrary Python objects implementing __index__.
* fractions.gcd() and Fraction's constructor now use math.gcd() if both arguments are int, but also support non-ints (e.g. Fractions or floats).
* fractions.gcd() now is deprecated.

But before committing I want to experiment with simpler implementation and compare it with current complex implementation. If the difference will be not too large, we could use simpler implementation.