ON THE CONGRUENCE xx= x (mod n)

摘要

Solutions to the congruence xx = x (mod p), where p is a prime and 1 ? x ? p 1, have been investigated by several authors. Although Kurlberg, Luca and Shparlinski have recently shown that a solution exists with x 6= 1 for almost all primes, there do exist primes for which the only solution is x = 1, and they conjectured that the set of such primes is infinite. In this article, we investigate the nature of the solutions to this congruence when the prime modulus is replaced with a composite number. Among the results presented, we show that, unlike the situation when the modulus is a prime, there is always a solution with x 6= 1. In addition, we prove several results concerning the structure of these solutions, with special attention given to the algebraic structure. In particular, we show that there exist infinitely many composite numbers n for which the set of all solutions to xx x (mod n), with 1 ? x ? n 1, is a subgroup of the group of units modulo n.