Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-29T20:38:47.126Z Has data issue: false hasContentIssue false
  • English
  • Français

RANDOM MULTIPLICATIVE WALKS ON THE RESIDUES MODULO $n$

Part of: Ergodic theory Multiplicative number theory

Published online by Cambridge University Press:  12 May 2017

Nathan McNew
Nathan McNew*
Affiliation:
Department of Mathematics, Towson University, 8000 York Road, Towson, MD 21252, U.S.A. email [email protected]
Get access

Abstract

We introduce a new arithmetic function $a(n)$ defined to be the number of random multiplications by residues modulo $n$ before the running product is congruent to zero modulo $n$. We give several formulas for computing the values of this function and analyze its asymptotic behavior. We find that it is closely related to $P_{1}(n)$, the largest prime divisor of $n$. In particular, $a(n)$ and $P_{1}(n)$ have the same average order asymptotically. Furthermore, the difference between the functions $a(n)$ and $P_{1}(n)$ is $o(1)$ as $n$ tends to infinity on a set with density approximately $0.623$. On the other hand, however, we see that (except on a set of density zero) the difference between $a(n)$ and $P_{1}(n)$ tends to infinity on the integers outside this set. Finally, we consider the asymptotic behavior of the difference between these two functions and find that $\sum _{n\leqslant x}(a(n)-P_{1}(n))\sim (1-\unicode[STIX]{x1D70B}/4)\sum _{n\leqslant x}P_{2}(n)$, where $P_{2}(n)$ is the second largest divisor of $n$.

MSC classification

Primary: 11N37: Asymptotic results on arithmetic functions 37A45: Relations with number theory and harmonic analysis
Type
Research Article
Information
Mathematika , Volume 63 , Issue 2 , 2017 , pp. 602 - 621
Copyright
Copyright © University College London 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aldous, D., Random walks on finite groups and rapidly mixing Markov chains. In Seminar on Probability, XVII (Lecture Notes in Mathematics 986 ), Springer (Berlin, 1983), 243–297; MR 770418.Google Scholar
Alladi, K. and Erdős, P., On an additive arithmetic function. Pacific J. Math. 71(2) 1977, 275–294; MR 0447086.Google Scholar
Alladi, K. and Erdős, P., On the asymptotic behavior of large prime factors of integers. Pacific J. Math. 82(2) 1979, 295–315; MR 551689.CrossRefGoogle Scholar
De Koninck, J. M. and Ivić, A., The distribution of the average prime divisor of an integer. Arch. Math. (Basel) 43(1) 1984, 37–43; MR 758338.Google Scholar
Erdős, P. and Ivić, A., Estimates for sums involving the largest prime factor of an integer and certain related additive functions. Studia Sci. Math. Hungar. 15(1–3) 1980, 183–199; MR 681439.Google Scholar
Erdős, P., Ivić, A. and Pomerance, C., On sums involving reciprocals of the largest prime factor of an integer. Glas. Mat. Ser. III 21(41)(2) 1986, 283–300; MR 896810.Google Scholar
Erdős, P. and Pomerance, C., On the largest prime factors of n and n + 1. Aequationes Math. 17(2–3) 1978, 311–321; MR 0480303.Google Scholar
Gretete, D., Random walk on a finitely generated monoid. Int. J. Math. Combinatorics 4 2011, 54–58; (electronic).Google Scholar
Hildebrand, M., A survey of results on random walks on finite groups. Probab. Surv. 2 2005, 33–63; MR 2121795.Google Scholar
Ivić, A., On the kth prime factor of an integer. Zb. Rad. Prirod.-Mat. Fak. Ser. Mat. 20(1) 1990, 63–73; MR 1158406.Google Scholar
Jeske, D. R. and Blessinger, T., Tunable approximations for the mean and variance of the maximum of heterogeneous geometrically distributed random variables. Amer. Statist. 58(4) 2004, 322–327; MR 2109423.CrossRefGoogle Scholar
Kemeny, J., Largest prime factor. J. Pure Appl. Algebra 89(1–2) 1993, 181–186.CrossRefGoogle Scholar
Knuth, D. E. and Trabb Pardo, L., Analysis of a simple factorization algorithm. Theoret. Comput. Sci. 3(3) 1976/77, 321–348; MR 0498355.CrossRefGoogle Scholar
Mairesse, J., Random walks on groups and monoids with a Markovian harmonic measure. Electron. J. Probab. 10 2005, 1417–1441 (electronic); MR 2191634.Google Scholar
McNew, N., Multiplicative problems in combinatorial number theory. PhD Thesis, Dartmouth College, 2015.Google Scholar
Naslund, E., The average largest prime factor. Integers 13 2013; Paper No. A81, 5.Google Scholar
Wheeler, F. S., Two differential-difference equations arising in number theory. Trans. Amer. Math. Soc. 318(2) 1990, 491–523; MR 963247.Google Scholar