While Tim's expression might look (superficially) like C, the five-line alternative isn't exactly an inspiring example of Pythonicity, is it?
diff = x - x_base if diff and gcd(diff, n) > 1: return gcd(diff, n) # or
if (x - x_base) and gcd(x - x_base, n) > 1: return gcd(x - x_base, n)and have the interpreter handle the optimization, or apply an lru_cache? ;-)