d := new(Int).GCD(x, y, a, b)
	x.Mul(x, a)
	y.Mul(y, b)
	x.Add(x, y)

	return x.Cmp(d) == 0
}

// euclidExtGCD is a reference implementation of Euclid's
// extended GCD algorithm for testing against optimized algorithms.
// Requirements: a, b > 0
func euclidExtGCD(a, b *Int) (g, x, y *Int) {
	A := new(Int).Set(a)
	B := new(Int).Set(b)

	// A = Ua*a + Va*b
	// B = Ub*a + Vb*b