Product Sets of Rationals, Multiplicative Translates of Subgroups in Residue Rings, and Fixed Points of the Discrete Logarithm

摘要

We give a lower bound on the size of the product set of two arbitrary subsets of the set of Farey fractions of a given order and apply it to study the distribution of elements of multiplicative groups in residue rings. For example, we prove a conjecture of J. Holden and P. Moree on the behavior of the number of solutions to the congruence gh ≡ h (mod p), 1 ≤ g,h ≤ p - 1, on average over primes p. This congruence appears in studying fixed points of the discrete logarithm.