Numbers n whose Euler Phi value Divides n + 1/Mistake/Third Edition

Source Work

2004: Richard K. Guy: Unsolved Problems in Number Theory (3rd ed.):

$\mathbf B$: Divisibility

$\mathbf {B 37}$: Does $\map \phi n$ properly divide $n - 1$?

Mistake

Lehmer gives $8$ solutions to $\map \phi n \mid n + 1$, namely $n = 2$, $n = 2^{2^k} - 1$ for $1 \le k \le 5$, $n = n_1 = 3 \cdot 5 \cdot 17 \cdot 353 \cdot 929$ and $n = n_1 \cdot 83623937$. [Note that $353 = 11 \cdot 2^5 + 1, 929 = 29 \cdot 2^5 + 1, 83623937 = 11 \cdot 29 \cdot 2^{18} + 1$ and $\paren {353 - 2^8} \paren {929 - 2^8} = 2^{16} - 2^8 + 1$.] This exhausts the solutions with less than seven factors. Victor Meally notes that $n = n_1 \cdot 83623937 \cdot 699296672132097$ would be a solution were the largest factor a prime, put Peter Borwein notes that this is divisible by $73$.

Correction

While Guy attributes that final observation to Victor Meally, it does in fact appear in Lehmer's original $1932$ article as a footnote:

In the same way if $6992962672132097$ is a prime

$3 \cdot 5 \cdot 17 \cdot 353 \cdot 929 \cdot 83623937 \cdot 6992962672132097 = 48901526933832864378258473353215$

is a solution of $(2)$.

Also note that $699296672132097$ is a misprint.

The correct number is $6992962672132097$.

Also see

• Numbers $n$ whose Euler Phi value Divides $n + 1$

Sources

• 1932: D.H. Lehmer: On Euler's Totient Function (Bull. Amer. Math. Soc. Vol. 38: pp. 745 – 751)

• 2004: Richard K. Guy: Unsolved Problems in Number Theory (3rd ed.): $\mathbf B$: Divisibility: $\mathbf {B 37}$: Does $\map \phi n$ properly divide $n - 1$?