Lehmer's Totient Problem

Author

Eric W. Weisstein
January 15, 2004

This notebook downloaded from http://mathworld.wolfram.com/notebooks/NumberTheory/LehmersTotientProblem.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/LehmersTotientProblem.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Code

Divides[a_,b_]:=Mod[b,a]==0

Enumeration

Select[Range[10^6],!PrimeQ[#]&&Divides[EulerPhi[#],#-1]&]//Timing

Select[Range[10^7],!PrimeQ[#]&&Divides[EulerPhi[#],#-1]&]//Timing