I strongly agree with Mark's revised plan:
1. add a fast C-coded math.gcd returning the actual greatest (in normal ordered int sense) common divisor;
2. use this for reduction of fractions in the fractions module to speed up operations on fractions.
3. revised fractions.gcd docstring "Return signed version of math.gcd.  ..."
I think this would be double win (users get fast, 'proper' gcd; fractions work faster too).