The AMS website will be down for maintenance on May 23 between 6:00am - 8:00am EDT. For questions please contact AMS Customer Service at or (800) 321-4267 (U.S. & Canada), (401) 455-4000 (Worldwide).


Remote Access St. Petersburg Mathematical Journal

St. Petersburg Mathematical Journal

ISSN 1547-7371(online) ISSN 1061-0022(print)



On the number of solutions of the congruence $ xy\equiv l\pmod{q}$ under the graph of a twice continuously differentiable function

Author: A. V. Ustinov
Translated by: N. B. Lebedinskaya
Original publication: Algebra i Analiz, tom 20 (2008), nomer 5.
Journal: St. Petersburg Math. J. 20 (2009), 813-836
MSC (2000): Primary 11L05, 11L07
Published electronically: July 21, 2009
MathSciNet review: 2492364
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A result by V. A. Bykovskiĭ (1981) on the number of solutions of the congruence $ xy\equiv l\pmod{q}$ under the graph of a twice continuously differentiable function is refined. As an application, Porter's result (1975) on the mean number of steps in the Euclidean algorithm is sharpened and extended to the case of Gauss-Kuzmin statistics.

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

  • 1. M. O. Avdeeva, Distribution of partial quotients in finite continued fractions, Preprint no. 4 Dal'nevost. Otdel. Ross. Akad. Nauk, Khabarov. Otdel. Inst. Prikl. Mat., Dal'nauka, Vladivostok, 2000. (Russian)
  • 2. V. A. Bykovskiĭ, Asymptotic properties of lattice points $ (a_1,a_2)$ that satisfy the congruence $ a_1a_2\equiv l({q})$, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 112 (1981), 5-25, 198; English transl. in J. Soviet Math. 25 (1984), no. 2. MR 0643990 (83d:10060)
  • 3. I. M. Vinogradov, \cyr Osobye varianty metoda trigonometricheskikh summ., Izdat. “Nauka”, Moscow, 1976 (Russian). MR 0469878
  • 4. A. V. Ustinov, On the statistical properties of finite continued fractions, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 322 (2005), no. Trudy po Teorii Chisel, 186–211, 255 (Russian, with English and Russian summaries); English transl., J. Math. Sci. (N.Y.) 137 (2006), no. 2, 4722–4738. MR 2138459,
  • 5. A. V. Ustinov, Asymptotic behavior of the first and second moments for the number of steps in the Euclidean algorithm, Izv. Ross. Akad. Nauk Ser. Mat. 72 (2008), no. 5, 189–224 (Russian, with Russian summary); English transl., Izv. Math. 72 (2008), no. 5, 1023–1059. MR 2473776,
  • 6. Tom M. Apostol, Mathematical analysis, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1974. MR 0344384
  • 7. T. Estermann, On Kloosterman’s sum, Mathematika 8 (1961), 83–86. MR 0126420,
  • 8. S. W. Graham and G. Kolesnik, van der Corput’s method of exponential sums, London Mathematical Society Lecture Note Series, vol. 126, Cambridge University Press, Cambridge, 1991. MR 1145488
  • 9. G. H. Hardy and E. M. Wrighte, An introduction to the theory of numbers, Clarendon Press, Oxford Univ. Press, New York, 1979. MR 0568909 (81i:10002)
  • 10. D. R. Heath-Brown, The fourth power moment of the Riemann zeta function, Proc. London Math. Soc. (3) 38 (1979), 385-422. MR 0532980 (81f:10052)
  • 11. H. Heilbronn, On the average length of a class of finite continued fractions, Number Theory and Analysis (Papers in Honor of Edmund Landau), Plenum, New York, 1969, pp. 87–96. MR 0258760
  • 12. Christopher Hooley, On the number of divisors of a quadratic polynomial, Acta Math. 110 (1963), 97–114. MR 0153648,
  • 13. J. W. Porter, On a theorem of Heilbronn, Mathematika 22 (1975), no. 1, 20–28. MR 0498452,
  • 14. Gérald Tenenbaum, Introduction to analytic and probabilistic number theory, Cambridge Studies in Advanced Mathematics, vol. 46, Cambridge University Press, Cambridge, 1995. Translated from the second French edition (1995) by C. B. Thomas. MR 1342300

Similar Articles

Retrieve articles in St. Petersburg Mathematical Journal with MSC (2000): 11L05, 11L07

Retrieve articles in all journals with MSC (2000): 11L05, 11L07

Additional Information

A. V. Ustinov
Affiliation: Khabarovsk Division, Institute of Applied Mathematics, Far Eastern Branch, Russian Academy of Sciences, 54 Dzerzhinskiĭ Street, 680000 Khabarovsk, Russia

Keywords: Euclid algorithm, Gauss--Kuzmin statistics, Kloosterman sums
Received by editor(s): December 12, 2007
Published electronically: July 21, 2009
Additional Notes: Supported by RFBR (grant no. 07-01-00306), by the Far Eastern Department of the Russian Academy of Sciences (project no. 06-III-C-01-017), and by the Foundation of Assistance to the Russian Science.
Article copyright: © Copyright 2009 American Mathematical Society

American Mathematical Society