Proportionally modular diophantine inequalities and the Stern-Brocot tree

Abstract:

Given positive integers $a,b$ and $c$ to compute a generating system for the numerical semigroup whose elements are all positive integer solutions of the inequality $a x \mathbf {mod} b\leq cx$ is equivalent to computing a Bézout sequence connecting two reduced fractions. We prove that a proper Bézout sequence is completely determined by its ends and we give an algorithm to compute the unique proper Bézout sequence connecting two reduced fractions. We also relate Bézout sequences with paths in the Stern-Brocot tree and use this tree to compute the minimal positive integer solution of the above inequality.