A Euclidean-Type Algorithm for the Weighted Greatest Common Divisor

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_0, …, x_n) ∈ ⁿ⁺¹\) with respect to a given weight vector \( = (q_0, …, q_n) ∈ ⁿ⁺¹\). 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(log min(|x_0|, |x_1|))\) modular operations, completely avoiding factorization. We extend the algorithm to arbitrary dimension using the recursive decomposition formula\[_{}() = (1,q_n)(_{{n}}({n}), x_n),\]where \({n} = (q_0, …, qₙ₋₁)\) and \({n} = (x_0, …, xₙ₋₁)\). The resulting algorithm computes the \(\) in \(O(nlog^3 M)\) bit operations, where \(M = max_i |x_i|\). Finally, we provide a complete implementation in Python and demonstrate its efficiency through numerical experiments.