On composite n for which φ(n)∣n − 1. II

Carl Pomerance

Vol. 69 (1977), No. 1, 177–186

DOI: 10.2140/pjm.1977.69.177

Abstract

The problem of whether there exists a composite n for which φ(n)∣n − 1 (φ is Euler’s function) was first posed by D. H. Lehmer in 1932 and still remains unsolved. In this paper we prove that the number of such n not exceeding x is O(x^1∕2(log x)^3∕4). We also prove that any such n with precisely K distinct prime factors is necessarily less than K^2K . There are appropriate generalizations of these results to integers n for which φ(n)∣n − a, a an arbitrary integer.

Mathematical Subject Classification

Primary: 10A20, 10A20

Milestones

Received: 28 October 1975

Published: 1 March 1977