Computing efficiently the weighted greatest common divisor

Abstract

In this paper we included some basic properties for weighted greatest common divisors, and discuss how to speed up computing the weighted greatest common divisor. By ordering the 'weights' we are able to significantly shorten the operations to computing wgcd. In the absence of an efficient algorithm for computing wgcd by ordering the weights, and using $\gcd$, we significantly reduce the numbers for which we want to compute wgcd. As a final result in this paper we prove that: If $\mathbf{x}=(x_0,\dots ,x_n)\in {\mathbb{Z}}^{n+1}$, with weights $\mathfrak{w}=(q_0,\dots ,q_n)$ and $q_0\le \cdots \le q_n$, then ${\mathrm{wgcd}}_w(\mathbf{x})={\mathrm{wgcd}}_w(y_0,y_1,\dots ,y_n)$, where $y_i=\gcd (x_i,\dots ,x_n)$, and $y_0\le y_1\le \cdots \le y_n$.

arXiv comment12 pages