Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Proportionally modular diophantine inequalities and the Stern-Brocot tree


Authors: M. Bullejos and J. C. Rosales
Journal: Math. Comp. 78 (2009), 1211-1226
MSC (2000): Primary 11D75, 20M14
Published electronically: August 12, 2008
MathSciNet review: 2476582
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11D75, 20M14

Retrieve articles in all journals with MSC (2000): 11D75, 20M14


Additional Information

M. Bullejos
Affiliation: Departamento de Álgebra, Universidad de Granada, 18071 Granada, Spain
Email: bullejos@ugr.es

J. C. Rosales
Affiliation: Departamento de Álgebra, Universidad de Granada, 18071 Granada, Spain
Email: jrosales@ugr.es

DOI: http://dx.doi.org/10.1090/S0025-5718-08-02173-X
PII: S 0025-5718(08)02173-X
Keywords: Diophantine inequation, numerical semigroup, Stern-Brocot tree
Received by editor(s): January 3, 2008
Received by editor(s) in revised form: April 4, 2008
Published electronically: August 12, 2008
Additional Notes: This work was partially supported by research projects MTM2005-03227 and MTM2007-62346
Article copyright: © Copyright 2008 American Mathematical Society