On generalizing Artin's conjecture on primitive roots to composite moduli

Various cyclic structures have been employed in cryptography and in pseudrandom number generation. One of the most basic arenas for this study is the multiplicative group of integers modulo n. In this paper we study the liklihood of a fixed integer relatively prime to n to generate a maximal cyclic subgroup of the multiplicative group modulo n. We discover and elucidate a surprising oscillation. In an earlier paper of the first author, it is shown that the set of such integers n has lower asymptotic density 0. We show in this paper, assuming the Generalized Riemann Hypothesis (GRH), that the upper asymptotic density is positive. This result stands in stark contrast to the situation with prime moduli, where it has been shown by Hooley that the GRH implies Artin's conjecture, namely that for a fixed integer, a positive density of the primes have this integer generating the multiplicative group modulo the prime.