Uniform Distribution of Fractional Parts Related to Pseudoprimes

Banks, William D. ; Garaev, Moubariz Z. ; Luca, Florian ; Shparlinski, Igor E.

Canadian journal of mathematics, Tome 61 (2009) no. 3, pp. 481-502

Résumé

We estimate exponential sums with the Fermat-like quotients $${{f}_{g}}(n)=\frac{{{g}^{n-1}}-1}{n}\text{and }{{h}_{g}}(n)=\frac{{{g}^{n-1}}-1}{P(n)},$$ where $g$ and $n$ are positive integers, $n$ is composite, and $P\left( n \right)$ is the largest prime factor of $n$ . Clearly, both ${{f}_{g}}(n)$ and ${{h}_{g}}(n)$ are integers if $n$ is a Fermat pseudoprime to base $g$ , and if $n$ is a Carmichael number, this is true for all $g$ coprime to $n$ . Nevertheless, our bounds imply that the fractional parts $\left\{ {{f}_{g}}(n) \right\}$ and $\left\{ {{h}_{g}}(n) \right\}$ are uniformly distributed, on average over $g$ for ${{f}_{g}}(n)$ , and individually for ${{h}_{g}}(n)$ . We also obtain similar results with the functions ${{\tilde{f}}_{g}}(n)=g\,{{f}_{g}}(n)$ and ${{\tilde{h}}_{g}}(n)=g{{h}_{g}}(n)$ .

Détail

DOI : 10.4153/CJM-2009-025-2

Mots-clés : 11L07, 11N37, 11N60

Bibliographie

[1] [1] Alford, W. R., Granville, A., and Pomerance, C., There are infinitely many Carmichael numbers. Ann. of Math. 139(1994), no. 3, 703–722. Google Scholar

[2] [2] Banks, W. D., Garaev, M. Z., Luca, F., and Shparlinski, I. E., Uniform distribution of the fractional part of the average prime divisor. Forum Math. 17(2005), no. 6, 885–901. Google Scholar

[3] [3] Bassily, N. L., Kátai, I., and Wijsmuller, M., On the prime power divisors of the iterates of the Euler-ϕ function. Publ. Math. Debrece. 55(1999), no. 1-2, 17–32. Google Scholar

[4] [4] Bateman, P. T., Erdös, P., Pomerance, C., and Straus, E. G., The arithmetic mean of the divisors of an integer. In: Analytic number theory, Lecture Notes in Math. 899, Springer, Berlin-New York, 1981, pp. 197–220. Google Scholar

[5] [5] Bourgain, J., New bounds on exponential sums related to Diffie-Hellman distributions. C. R. Math. Acad. Sci. Pari. 338(2004), no. 11, 825–830. Google Scholar

[6] [6] Bourgain, J., Glibichuk, A. A., and Konyagin, S. V., Estimates for the number of sums and products and for exponential sums in fields of prime order. J. London Math. Soc. 73(2006), no. 2, 380–398. Google Scholar

[7] [7] Boyarinov, R. N., Ngongo, I. S., and Chubarikov, V. N., On new metric theorems in the method of A. G. Postnikov. In: IV International conference: modern problems of number theory and its pplications, Current problems III, Mosk. Gos. Univ. im. Lomonosova Mekh.- Mat. Fak., Moscow, 2002, pp. 5–31. Google Scholar

[8] [8] El- Mahassni, E. D., Shparlinski, I. E., and A.Winterhof, Distribution of nonlinear congruential pseudorandom numbers modulo almost squarefree integers. Monatsh. Math. 148(2006), no. 4, 297–307. Google Scholar

[9] [9] Erdös, P., Granville, A., Pomerance, C., and Spiro, C., On the normal behavior of the iterates of some arithmetic functions. In: Analytic number theory, Progr. Math. 85, Birkhäuser, Boston, MA, 1990, pp. 165–204. Google Scholar

[10] [10] Erdʺos, P. and Murty, R., On the order of a (mod p). CR MProc. Lecture Notes 19, American Mathematical Society, Providence, RI, 1999, 87–97. Google Scholar

[11] [11] Erdʺos, P. and Pomerance, C., On the number of false witnesses for a composite number. Math. Comp.46(1986), no. 173, 259–279. Google Scholar

[12] [12] Ford, K., The distribution of integers with a divisorin a given interval. Ann. of Math. 168(2008), no. 2, 367–433. Google Scholar

[13] [13] Garaev, M. Z., The large sieve inequality for the exponential sequence ƛ [O(n15/14+o(1))] modulo primes. Canad. J. Math., 61(2009), 336–350. Google Scholar

[14] [14] Garaev, M. Z., Luca, F., and Shparlinski, I. E., Exponential sums and congruences with factorials. J. Reine Angew. Math. 584(2005), 29–44. Google Scholar

[15] [15] Garaev, M. Z. and Shparlinski, I. E., The large sieve inequality with exponential functions and the distribution of Mersenne numbers modulo primes. Int. Math. Res. Not. 2005(2005), no. 39, 2391–2408. Google Scholar

[16] [16] Granville, A. and Pomerance, C., Two contradictory conjectures concerning Carmichael numbers. Math. Comp. 71(2002), no. 238, 883–908. Google Scholar

[17] [17] Heath-Brown, D. R., An estimate for Heilbronn's exponential sum. In: Analytic number theory 2, Progr. Math. 139, Birkhäuser, Boston, MA, 1996, pp. 451–463. Google Scholar

[18] [18] Heath-Brown, D. R. and Konyagin, S. V., New bounds for Gauss sums derived from kth powers, and for Heilbronn's exponential sum. Q. J. Math. 51(2000), no. 2, 221–235. Google Scholar

[19] [19] Indlekofer, K.-H. and Timofeev, N. M., Divisors of shifted primes. Publ. Math. Debrece. 60(2002), no. 3-4, 307–345. Google Scholar

[20] [20] Karatsuba, A. A., Fractional parts of functions of a special form. Izv. Math. 59(1995), no. 4, 721–740. Google Scholar

[21] [21] Karatsuba, A. A., Analogues of Kloosterman sums. Izv. Math. 59(1995), no. 5, 971–981. Google Scholar

[22] [22] Karatsuba, A. A., Double Kloosterman sums. Math. Note. 66(1999), no. 5-6, 565–569. Google Scholar

[23] [23] Konyagin, S. V., Estimates of trigonometric sums over subgroups and Gauss sums. In: IV International Conference, Modern problems of number theory and its applications, Mosk. Gos. Univ. im. Lomonosova Mekh.- Mat. Fak., Moscow, 2002, pp. 86–114. Google Scholar

[24] [24] Konyagin, S. V. and Shparlinski, I. E., Character sums with exponential functions and their applications. Cambridge Tracts in Mathematics 136, Cambridge University Press, Cambridge, 1999. Google Scholar

[25] [25] Korobov, N. M., Estimates of trigonometric sums and their applications. Uspehi Mat. Nau. 13(1958), no. 4, 185–192. Google Scholar

[26] [26] Korobov, N. M., Double trigonometric sums and their applications to the estimation of rational sums. Mat. Zametk. 6(1969), 25–34. Google Scholar

[27] [27] Landau, E., Über die Zahlentheoretische Function ϕ(n) und ihre Beziehung zum Goldbachschen Satz. Nachr. Königlichen Ges.Wiss. Göttingen, Math.-Phys. Klasse, Göttingen, 1900, 177–186. Google Scholar

[28] [28] Lidl, R. and Niederreiter, H., Finite fields. In: Encyclopedia of mathematics and its applications 20, second edition, Cambridge University Press, Cambridge, 1997. Google Scholar

[29] [29] Luca, F., On f (n) modulo ω(n) and (n) when f is a polynomial. J. Aust. Math. Soc. 77(2004), no. 2, 149–164. Google Scholar

[30] [30] Luca, F. and Pomerance, C., On some problems of Makowski-Schinzel and Erdʺos concerning the arithmetical functions ϕ and σ. Colloq. Math. 92(2002), no. 1, 111–130. Google Scholar

[31] [31] Luca, F. and Sankaranarayanan, A., The distribution of integers n divisible by lω(n). Publ. Inst. Math. 76(90)(2004), 89–99. Google Scholar

[32] [32] Montgomery, H. L., Primes in arithmetic progressions. Michigan Math. J. 17(1970), 33–39. Google Scholar

[33] [33] Montgomery, H. L., Ten lectures on the interface between analytic number theory and harmonic analysis. C MBS Regional Conference Series in Mathematics 84, American Mathematical Society, Providence, RI, 1994. Google Scholar

[34] [34] Montgomery, H. L. and Vaughan, R. C., The large sieve. Mathematika 20(1973), 119–134. Google Scholar

[35] [35] Postnikov, A. G., Ergodic aspects of the theory of congruences and of the theory of Diophantine approximations. Trudy Mat. Inst. Steklo. 82(1966), 3–112. Google Scholar

[36] [36] Prachar, K., Primzahlverteilung. Springer-Verlag, Berlin, 1957. Google Scholar

[37] [37] Spiro, C., How often is the number of divisors of n a divisor of n? J. Number Theor. 21(1985), no. 1, 81–100. Google Scholar

[38] [38] Spiro, C., Divisibility of the k-fold iterated divisor function of n into n. Acta Arith. 68(1994), no. 4, 307–339. Google Scholar

[39] [39] Tenenbaum, G., Introduction to analytic and probabilistic number theory. Studies in Advanced Mathematics 46, Cambridge University Press, 1995. Google Scholar

[40] [40] Vinogradov, A. I., On the remainder in Merten's formula. Dokl. Akad. Nauk SSS. 148(1963), 262–263. Google Scholar

[41] [41] Vinogradov, I. M., Elements of number theory. Dover Publications, New York, 1954. Google Scholar