The weighted greatest common divisor \ (\) is a fundamental tool in the arithmetic of weighted projective spaces, playing a key role in the definition of weighted heights. While the \ (\) can be computed via prime factorization or using an LCM-based formula, these methods become inefficient for large integers due to the cost of factorization. In this paper we introduce a Euclidean-type algorithm for computing the \ (\) of a tuple of integers \ (= (x₀, , xₙ) ^n+1\) with respect to a given weight vector \ (= (q₀, , qₙ) ^n+1\). For the two-dimensional case we prove that, under an appropriate ordering of the weights, the classical Euclidean reduction using modular arithmetic preserves the \ (\). This leads to an algorithm that runs in \ (O ( (|x₀|, |x₁|) ) \) modular operations, completely avoiding factorization. We extend the algorithm to arbitrary dimension using the recursive decomposition formula\_ () = (₁, ₐ䂸) (₍ (n), xₙ), \ (n = (q₀, , q₍-₁) \) and \ (n = (x₀, , x₍-₁) \). The resulting algorithm computes the \ (\) in \ (O (n³ M) \) bit operations, where \ (M = ᵢ |xᵢ|\). Finally, we provide a complete implementation in Python and demonstrate its efficiency through numerical experiments.
Orgest Zaka (Sun,) studied this question.