## 5.158. gcd

Origin
Constraint

$\mathrm{𝚐𝚌𝚍}\left(𝚇,𝚈,𝚉\right)$

Arguments
 $𝚇$ $\mathrm{𝚍𝚟𝚊𝚛}$ $𝚈$ $\mathrm{𝚍𝚟𝚊𝚛}$ $𝚉$ $\mathrm{𝚍𝚟𝚊𝚛}$
Restrictions
 $𝚇>0$ $𝚈>0$ $𝚉>0$
Purpose

Enforce the fact that $𝚉$ is the greatest common divisor of $𝚇$ and $𝚈$.

Example
$\left(24,60,12\right)$

The $\mathrm{𝚐𝚌𝚍}$ constraint holds since 12 is the greatest common divisor of 24 and 60.

Typical
 $𝚇>1$ $𝚈>1$
Symmetry

Arguments are permutable w.r.t. permutation $\left(𝚇,𝚈\right)$ $\left(𝚉\right)$.

Arg. properties

Functional dependency: $𝚇$ determined by $𝚈$ and $𝚉$.

Algorithm

In [DenmatGotliebDucasse07] a filtering algorithm for the $\mathrm{𝚐𝚌𝚍}$ constraint was automatically derived from the Euclidian algorithm by using constructive disjunction and abstract interpretation in order to approximate the behaviour of the while loop of the Euclidian algorithm.