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

DOI:
https://doi.org/10.1090/S0025-5718-08-02173-X

Published electronically:
August 12, 2008

MathSciNet review:
2476582

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Given positive integers and to compute a generating system for the numerical semigroup whose elements are all positive integer solutions of the inequality 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.

**1.**A. Bogomolny,*Stern-Brocot Tree. Binary Encoding*; see the website: www.cut-the-knot.org/blue/encoding.shtml.**2.**Ronald L. Graham, Donald E. Knuth, and Oren Patashnik,*Concrete mathematics*, 2nd ed., Addison-Wesley Publishing Company, Reading, MA, 1994. A foundation for computer science. MR**1397498****3.**J. L. Ramírez-Alfonsín,*Complexity of the Frobenius problem*, Combinatorica**16**(1996), no. 1, 143–147. MR**1394516**, https://doi.org/10.1007/BF01300131**4.**J. L. Ramírez Alfonsín,*The Diophantine Frobenius problem*, Oxford Lecture Series in Mathematics and its Applications, vol. 30, Oxford University Press, Oxford, 2005. MR**2260521****5.**J. C. Rosales, P. A. García-Sánchez, J. I. García-García, and J. M. Urbano-Blanco,*Proportionally modular Diophantine inequalities*, J. Number Theory**103**(2003), no. 2, 281–294. MR**2020273**, https://doi.org/10.1016/j.jnt.2003.06.002**6.**J. C. Rosales, P. A. García-Sánchez and J. M. Urbano-Blanco,*The set of solutions of a proportionally modular diophantine inequality*, Journal of Number Theory 128 (2008), 453-467.**7.**J. C. Rosales and P. Vasco,*The smallest positive integer that is a solution of a proportionally modular diophantine inequality*, to appear in Mathematical Inequalities & Applications (2008), www.ele-math.com.**8.**J. J. Sylvester,*Mathematical questions with their solutions*, Educational Times 41 (1884), 21.

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:
https://doi.org/10.1090/S0025-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