Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Products of prime powers in binary recurrence sequences. I. The hyperbolic case, with an application to the generalized Ramanujan-Nagell equation


Authors: A. Pethö and B. M. M. de Weger
Journal: Math. Comp. 47 (1986), 713-727
MSC: Primary 11D61; Secondary 11Y50
DOI: https://doi.org/10.1090/S0025-5718-1986-0856715-5
MathSciNet review: 856715
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We show how the Gelfond-Baker theory and diophantine approximation techniques can be applied to solve explicitly the diophantine equation $ {G_n} = wp_1^{{m_1}} \cdots p_t^{{m_t}}$ (where $ \{ {G_n}\} _{n = 0}^\infty $ is a binary recurrence sequence with positive discriminant), for arbitrary values of the parameters. We apply this to the equation $ {x^2} + k = p_1^{{z_1}} \cdots p_t^{{z_t}}$, which is a generalization of the Ramanujan-Nagell equation $ {x^2} + 7 = {2^z}$. We present algorithms to reduce upper bounds for the solutions of these equations. The algorithms are easy to translate into computer programs. We present an example which shows that in practice the method works well.


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

  • [1] A. Baker, Transcendental Number Theory, Cambridge Univ. Press, New York, 1975. MR 0422171 (54:10163)
  • [2] F. Beukers, "On the generalized Ramanujan-Nagell equation," I: Acta Arith., v. 38, 1981, pp. 389-410; II: Acta Arith., v. 39, 1981, pp. 113-123. MR 639621 (83a:10028b)
  • [3] A. Bremner, R. Calderbank, P. Hanlon, P. Morton & J. Wolfskill, "Two-weight ternary codes and the equation $ {y^2} = 4 \times {3^\alpha } + 13$," J. Number Theory, v. 16, 1983, pp. 212-234. MR 698166 (84m:10011)
  • [4] J.-H. Evertse, "On equations in S-units and the Thue-Mahler equation," Invent. Math., v. 75, 1984, pp. 561-584. MR 735341 (85f:11048)
  • [5] H. Hasse, "Über eine diophantische Gleichung von Ramanujan-Nagell und ihre Verallgemeinerung," Nagoya Math. J., v. 27, 1966, pp. 77-102. MR 0200237 (34:136)
  • [6] N. Koblitz, p-Adic Numbers. p-Adic Analysis and Zeta-Functions, Springer-Verlag, New York, 1977. MR 0466081 (57:5964)
  • [7] D. H. Lehmer, "On a problem of Størmer," Illinois J. Math., v. 8, 1964, pp. 57-79. MR 0158849 (28:2072)
  • [8] F. J. MacWilliams & N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977.
  • [9] K. Mahler, "Eine arithmetische Eigenschaft der rekurrierenden Reihen," Mathematika B (Leiden), v. 3, 1934, pp. 153-156.
  • [10] K. Mahler, "Über den grössten Primteiler spezieller Polynome zweiten Grades," Arch. Math. Naturvid. B, v. 41, 1935, pp. 3-26.
  • [11] M. Mignotte, "On the automatic resolution of certain diophantine equations," in EUROSAM 84, Proceedings, Lecture Notes in Comput. Sci., v. 174, Springer-Verlag, 1984, pp. 378-385. MR 779143 (86e:11021)
  • [12] A. PethÖ, "Perfect powers in second order recurrences," in Topics in Classical Number Theory, Colloq. Math. Soc. János Bolyai, vol. 34, Budapest, 1981, pp. 1217-1227. MR 781182 (86i:11009)
  • [13] A. Pethö, "Full cubes in the Fibonacci sequence," Publ. Math. Debrecen, v. 30, 1983, pp. 117-127. MR 733078 (85j:11027)
  • [14] A. Pethö, "On the solution of the diophantine equation $ {G_n} = {p^z}$," Proceedings EUROCAL 85, Linz, Austria, Vol. 2, Lecture Notes in Comput. Sci., vol. 204, Springer-Verlag, 1985, pp. 503-512. MR 826582 (87f:11021)
  • [15] A. J. van der Poorten, "Linear forms in logarithms in the p-adic case," in Transcendence Theory: Advances and Applications (A. Baker & D. W. Masser, eds.), Academic Press, London, 1977, pp. 29-57. MR 0498418 (58:16544)
  • [16] A. Schinzel, "On two theorems of Gelfond and some of their applications," Acta Arith., v. 13, 1967, pp. 177-236. MR 0222034 (36:5086)
  • [17] T. N. Shorey & R. Tudeman, Exponential Diophantine Equations, Cambridge Univ. Press, Cambridge, 1986. MR 891406 (88h:11002)
  • [18] C. Størmer, "Quelques théorèmes sur l'équation de Pell $ {x^2} - D{y^2} = \pm 1$ et leurs applications," Skrifter Videnskabs-selskabet I, Math.-Naturv. Kl., 1897, pp. 1-48.
  • [19] R. J. Stroeker & R. Tijdeman, "Diophantine equations," in Computational Methods in Number Theory (H. W. Lenstra, Jr. & R. Tijdeman, eds.), MC Tract 155, Amsterdam, 1982, pp. 321-369. MR 702521 (84i:10014)
  • [20] N. Tzanakis, "On the diophantine equation $ {y^2} - D = {2^k}$," J. Number Theory, v. 17, 1983, pp. 144-164.
  • [21] N. Tzanakis & J. Wolfskill, "On the diophantine equation $ {y^2} = 4{q^n} + 4q + 1$," J. Number Theory. (To appear.)
  • [22] N. Tzanakis & J. Wolfskill, "The diophantine equation $ {x^2} = 4{q^{a/2}} + 4q + 1$ with an application in coding theory." (To appear.)
  • [23] B. M. M. de Weger, "Products of prime powers in binary recurrence sequences II," Math. Comp., v. 47, 1986, pp. 729-739. MR 856716 (87m:11027b)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11D61, 11Y50

Retrieve articles in all journals with MSC: 11D61, 11Y50


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1986-0856715-5
Article copyright: © Copyright 1986 American Mathematical Society

American Mathematical Society