Mathematica 9 is now available

Wolfram Library Archive

All Collections Articles Books Conference Proceedings
Courseware Demos MathSource Technical Notes
Title Downloads

Computational Evidence for Lehmer's Totient Conjecture

John Renze
Organization: Wolfram Research, Inc.
Department: Information Resources
Revision date


In 1932, D. H. Lehmer considered the equation k ϕ[N] == N - 1. for positive integers N and k. If N is prime, then the equation has a solution with k = 1. He conjectured that these are the only solutions.

Conjecture: Let a be a positive integer. Then ϕ[N] divides N - 1 if and only if N is prime.

The conjecture remains open to this day. The current best result, due to Cohen and Hagis, is that N must have at least 14 prime factors and be greater than 10^22. The code in this notebook carries out a search for a counter-example to Lehmer's conjecture and extends these limits.

*Mathematics > Number Theory

Lehmer Totient
Downloads Download Wolfram CDF Player

LehmerArticle.nb (12.1 KB) - Mathematica Notebook [for Mathematica 5.0]