5.133. gcd

DESCRIPTIONLINKS
Origin

[DenmatGotliebDucasse07]

Constraint

𝚐𝚌𝚍(πš‡,𝚈,πš‰)

Arguments
πš‡πšπšŸπšŠπš›
πšˆπšπšŸπšŠπš›
πš‰πšπšŸπšŠπš›
Restrictions
πš‡β‰₯0
𝚈β‰₯0
πš‰β‰₯0
Purpose

Enforce the fact that πš‰ is the greatest common divisor of πš‡ and 𝚈.

Example
(24,60,12)

The 𝚐𝚌𝚍 constraint holds since 12 is the greatest common divisor of 24 and 60.

Typical
πš‡>1
𝚈>1
Symmetry

Arguments are permutable w.r.t. permutation (πš‡,𝚈) (πš‰).

Algorithm

In [DenmatGotliebDucasse07] a filtering algorithm for the 𝚐𝚌𝚍 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.

See also

common keyword: πš™πš˜πš πšŽπš›Β (abstract interpretation).

Keywords

constraint arguments: ternary constraint.

constraint type: arithmetic constraint, predefined constraint.

filtering: abstract interpretation.