Talk:Numbers n whose Euler Phi value Divides n + 1/Historical Note

Hi RandomUndergrad, you seem to have access to 1994: Richard K. Guy: Unsolved Problems in Number Theory (2nd ed.), I only have the $3$rd edition.

I need your help.

In $3$ed it goes:

Lehmer gives $8$ solutions to $\map \phi n \divides 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$ ... 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$.

So there are problems with this page, and this attribution of this result to Meally as follows:

a) $699 \, 296 \, 672 \, 132 \, 097 = 3 \times 13 \times 2 \, 317 \, 519 \times 7 \, 737 \, 017$ and so does not have $73$ as a factor. So that $699 \, 296 \, 672 \, 132 \, 097$ above is wrong. So the report as given in $3$rd Edition is incorrect. Can we check what it says in the $2$nd edition?

b) The results on this page concerning $83 \, 623 \, 935$ and $83 \, 623 \, 935 \times 83 \, 623 \, 937$ were (according to Guy $3$ed) given by D.H. Lehmer, along with a bunch of others. Presumably these were given in $2$ed as well.

c) I note that $83 \, 623 \, 935 \times 83 \, 623 \, 937 = 6 \, 992 \, 962 \, 672 \, 132 \, 095$, which is so tantalisingly close to $699 \, 296 \, 672 \, 132 \, 097$ that I checked whether he meant to write $6 \, 992 \, 962 \, 672 \, 132 \, 097$ instead. This would of course have been the gist of Meally's result, using the same mechanism as getting $83 \, 623 \, 935 \times 83 \, 623 \, 937$ from $83 \, 623 \, 935$. And indeed, I have checked $6 \, 992 \, 962 \, 672 \, 132 \, 097$ and it is indeed $73 \times 95 \, 794 \, 009 \, 207 \, 289$.

Hence I have the following to do:

1. I need to write another erratum page to Wells (that is: it was not Meally who found this result but Lehmer, and that the result was incompletely stated)
2. I need to write an erratum page to Guy $3$ed to report on the fact that $699 \, 296 \, 672 \, 132 \, 097$ is a misprint for $6 \, 992 \, 962 \, 672 \, 132 \, 097$.

So, in short: can you quote me here what 1994: Richard K. Guy: Unsolved Problems in Number Theory (2nd ed.) says, that is, whether he got that big number right that he got wrong in $3$ed? Then I will be able to write the erratum page so as to encompass that as well.

If you are able to fill in the details of the contents of $2$ed that would be brilliant. --prime mover (talk) 15:29, 8 July 2020 (UTC)

This section in $2$ed is called :Does $\map \phi n$ properly divide $n - 1$? so the result for $n + 1$ was included only as a note, for which I quote as follows:

Victor Meally notes that $\map \phi n$ sometimes divides $n + 1$, e.g. for $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$.]

The $n_1$ defined above is equal to $83623935$.

There is no mention of the larger number, though his method does require $n_1 + 2$ to be prime, so I agree with (c).

There is also no mention of Lehmer's results for $n + 1$, though there is a citation "On Euler's Totient Function, Bull. Amer. Math. Soc., 38(1932) 745-751".

--RandomUndergrad (talk) 16:12, 8 July 2020 (UTC)

Thank you for that. It looks as though the mistake happened only in $3$ed then. I will review the Lehmer citation, it is also there in $3$ed, as is the section enclosed in [...] above which I missed out so as to be brief.

As for filling in the details of $2$ed, best to wait till I've finished the detail of $3$ed, copy it over, and amend as needed. --prime mover (talk) 16:16, 8 July 2020 (UTC)

This has now all been implemented as errata pages in 1994: Richard K. Guy: Unsolved Problems in Number Theory (2nd ed.) and 2004: Richard K. Guy: Unsolved Problems in Number Theory (3rd ed.).

We would do well to replace or expand this page, or even add a further page, dedicated to Lehmer's complete analysis of this result. It's fairly elementary, but there are a number of lemmata. --prime mover (talk) 07:38, 9 July 2020 (UTC)