Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Some computational results on a problem concerning powerful numbers


Authors: A. J. Stephens and H. C. Williams
Journal: Math. Comp. 50 (1988), 619-632
MSC: Primary 11R11; Secondary 11A51, 11R27, 11Y16, 11Y40
DOI: https://doi.org/10.1090/S0025-5718-1988-0929558-3
MathSciNet review: 929558
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let D be a positive square-free integer and let $ X + Y\sqrt D $ be the fundamental unit in the order with Z-basis $ \{ 1,\sqrt D \} $. An algorithm, which is of time complexity $ O({D^{1/4 + \varepsilon }})$ for any positive $ \varepsilon $, is developed for determining whether or not $ D\vert Y$. Results are presented for a computer run of this algorithm on all $ D < {10^8}$. The conjecture of Ankeny, Artin and Chowla is verified for all primes $ \equiv 1\,\pmod 4$ less than $ {10^9}$.


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

  • [1] N. C. Ankeny, E. Artin & S. Chowla, "The class number of real quadratic number fields," Ann. of Math., v. 56, 1952, pp. 479-493. MR 0049948 (14:251h)
  • [2] B. D. Beach, H. C. Williams & C. R. Zarnke, Some Computer Results on Units in Quadratic and Cubic Fields, Proc. 25th Summer Meeting Canad. Math. Congr., Lakehead Univ., 1971, pp. 609-648. MR 0337887 (49:2656)
  • [3] G. Chrystal, Textbook of Algebra, part 2, 2nd ed., Dover reprint, New York, 1969, pp. 423-490.
  • [4] P. Erdős, "Consecutive numbers," Eureka 38, 1975/76, pp. 3-8.
  • [5] A. Granville, "Powerful numbers and Fermat's Last Theorem," C. R. Math. Rep. Acad. Sci. Canada, v. 8, 1986, pp. 215-218. MR 841645 (87h:11010)
  • [6] H. W. Lenstra, Jr., On the Calculation of Regulators and Class Numbers of Quadratic Fields, London Math. Soc. Lecture Note Series, vol. 56, 1982, pp. 123-150. MR 697260 (86g:11080)
  • [7] R. A. Mollin & P. G. Walsh, "A note on powerful numbers, quadratic fields, and the Pellian," C. R. Math. Rep. Acad. Sci. Canada, v. 8, 1986, pp. 109-111. MR 831787 (87g:11020)
  • [8] L. J. Mordell, "On a Pellian equation conjecture," Acta Arith., v. 6, 1960, pp. 137-144. MR 0118699 (22:9470)
  • [9] Oskar Perron, Die Lehre von den Kettenbrüchen, 2nd ed., Chelsea, New York, 1950. MR 0037384 (12:254b)
  • [10] R. J. Schoof, "Quadratic fields and factorization," Computational Methods in Number Theory (H. W. Lenstra, Jr. and R. Tijdemann, eds.), Math. Centrum Tracts, Number 155, Part II, Amsterdam, 1983, pp. 235-286. MR 702519 (85g:11118b)
  • [11] D. Shanks, Class Number, A Theory of Factorization and Genera, Proc. Sympos. Pure Math., vol. 20 (1969 Institute on Number Theory), Amer. Math. Soc., Providence, R. I., 1971, pp. 415-440. MR 0316385 (47:4932)
  • [12] D. Shanks, The Infrastructure of a Real Quadratic Field and Its Applications, Proc. 1972 Number Theory Conference, Boulder, 1972, pp. 217-224. MR 0389842 (52:10672)
  • [13] R. Soleng, "A computer investigation of units in quadratic number fields," unpublished manuscript.
  • [14] H. C. Williams, "A numerical investigation into the length of the period of the continued fraction expansion of $ \sqrt D $," Math. Comp., v. 34, 1981, pp. 593-601. MR 606518 (82f:10011)
  • [15] H. C. Williams & M. C. Wunderlich, "On the parallel generation of the residues for the continued fraction factoring algorithm," Math. Comp., v. 48, 1987, pp. 405-423. MR 866124 (88i:11099)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11R11, 11A51, 11R27, 11Y16, 11Y40

Retrieve articles in all journals with MSC: 11R11, 11A51, 11R27, 11Y16, 11Y40


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1988-0929558-3
Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society