Geodesic
On the Distribution of Pseudopowers
Canadian journal of mathematics, Tome 62 (2010) no. 3, pp. 582-594

Voir la notice de l'article provenant de la source Cambridge University Press

An $x$ -pseudopower to base $g$ is a positive integer that is not a power of $g$ , yet is so modulo $p$ for all primes $p\,\le \,x$ . We improve an upper bound for the least such number, due to E. Bach, R. Lukes, J. Shallit, and H. C. Williams. The method is based on a combination of some bounds of exponential sums with new results about the average behaviour of the multiplicative order of $g$ modulo prime numbers.
DOI : 10.4153/CJM-2010-020-4
Mots-clés : 11A07, 11L07, 11N36 
Konyagin, Sergei V.; Pomerance, Carl; Shparlinski, Igor E. On the Distribution of Pseudopowers. Canadian journal of mathematics, Tome 62 (2010) no. 3, pp. 582-594. doi: 10.4153/CJM-2010-020-4
@article{10_4153_CJM_2010_020_4,
     author = {Konyagin, Sergei V. and Pomerance, Carl and Shparlinski, Igor E.},
     title = {On the {Distribution} of {Pseudopowers}},
     journal = {Canadian journal of mathematics},
     pages = {582--594},
     year = {2010},
     volume = {62},
     number = {3},
     doi = {10.4153/CJM-2010-020-4},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-2010-020-4/}
}
TY  - JOUR
AU  - Konyagin, Sergei V.
AU  - Pomerance, Carl
AU  - Shparlinski, Igor E.
TI  - On the Distribution of Pseudopowers
JO  - Canadian journal of mathematics
PY  - 2010
SP  - 582
EP  - 594
VL  - 62
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-2010-020-4/
DO  - 10.4153/CJM-2010-020-4
ID  - 10_4153_CJM_2010_020_4
ER  - 
%0 Journal Article
%A Konyagin, Sergei V.
%A Pomerance, Carl
%A Shparlinski, Igor E.
%T On the Distribution of Pseudopowers
%J Canadian journal of mathematics
%D 2010
%P 582-594
%V 62
%N 3
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-2010-020-4/
%R 10.4153/CJM-2010-020-4
%F 10_4153_CJM_2010_020_4

[1] [1] Bach, E., Lukes, R., Shallit, J., and Williams, H. C., Results and estimates on pseudopowers. Math. Comp. 65(1996), no. 216, 1737–1747. doi: 10.1090/S0025-5718-96-00762-4 Google Scholar

[2] [2] Baker, R. C. and Harman, G., The Brun-Titchmarsh theorem on average. In: Analytic Number Theory. Progr. Math 138. Birkhäuser Boston, Boston, MA, 1996, pp. 39–103. Google Scholar

[3] [3] Baker, R. C. and Harman, G., Shifted primes without large prime factors. Acta Arith. 83(1998), no. 4, 331–361. Google Scholar

[4] [4] Banks, W., Friedlander, J. B., Pomerance, C., and Shparlinski, I. E., Multiplicative structure of values of the Euler function. In: High Primes and Misdemeanours: Lectures in Honour of the 60th Birthday of Hugh Cowie Williams. Fields Inst. Commun. 41. American Mathematical Society, Providence, RI, 2004, pp. 29–48. Google Scholar

[5] [5] Erdʺos, P. and Murty, M. R., On the order of a (mod p). In: Number Theory/ CR M Proc. Lecture Notes 19. American Mathematical Society, Providence, RI, 1999, pp. 87–97. Google Scholar

[6] [6] Ford, K., The distribution of integers with a divisor in a given interval. Ann. of Math. 168(2008), no. 2, 367–433. doi: 10.4007/annals.2008.168.367 Google Scholar

[7] [7] Fouvry, É., Théorème de Brun–Titchmarsh: application au théorème de Fermat. Invent. Math. 79(1985), no. 2, 383–407. doi: 10.1007/BF01388980 Google Scholar

[8] [8] Goldfeld, M., On the number of primes p for which p + a has a large prime factor. Mathematika 16(1969), 23–27. Google Scholar

[9] [9] Harman, G., Prime-Detecting Sieves. London Mathematical Society Monographs Series 33. Princeton University Press, Princeton, NJ, 2007. Google Scholar

[10] [10] Heath-Brown, D. R. and Konyagin, S. V., New bounds for Gauss sums derived from k-th powers, and for Heilbronn's exponential sum. Q. J. Math. 512000), no. 2, 221–235. doi: 10.1093/qjmath/51.2.221 Google Scholar

[11] [11] Hooley, C., On the largest prime factor of p + a. Mathematika 20(1973), 135–143. Google Scholar

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

[13] [13] Iwaniec, H. and Kowalski, E., Analytic Number Theory. American Mathematical Society Colloquuium Publications 53, American Mathematical Society, Providence, RI, 2004. Google Scholar

[14] [14] 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

[15] [15] Kurlberg, P. and Pomerance, C., On the period of the linear congruential and power generators. Acta Arith. 119(2005), no. 2, 149–169. doi: 10.4064/aa119-2-2 Google Scholar

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

[17] [17] Pappalardi, F., On the order of finitely generated subgroups of Q¤ (mod p) and divisors of p − 1. J. Number Theory 57(1996), no. 2, 207–222. doi: 10.1006/jnth.1996.0044 Google Scholar

[18] [18] Pomerance, C., Popular values of Euler's function. Mathematika 27(1980), no. 1, 84–89. Google Scholar

[19] [19] Pomerance, C. and Shparlinski, I. E., Smooth orders and cryptographic applications. In: Algorithmic Number Theory. Lecture Notes in Comput. Sci. 2369. Springer, Berlin, 2002, pp. 338–348. Google Scholar

[20] [20] Schinzel, A., A refinement of a theorem of Gerst on power residues. Acta Arith. 17(1970), 161–168. Google Scholar

[21] [21] Tenenbaum, G., Introduction to Analytic and Probabilistic Number Theory. Cambridge Studies in Mathematics 46. Cambridge University Press, Cambridge, 1995. Google Scholar

Cité par Sources :