Él y su padre trabajaron juntos en desarrollar la criba de Lehmer.
Dicho trabajo no fructiferó, sin embargo En 1.878 Édouard Lucas propuso dos pruebas para comprobar los números primos de Mersenne pero no realizó ninguna prueba completa tampoco.
Fue en 1932 que nació el primer hijo de la pareja, Laura.
Pasaron el año de 1938 a 1939 en Inglaterra gracias a una Beca Guggenheim, tanto en la Universidad de Cambridge como en la Universidad de Mánchester, en donde conoció a G. H. Hardy, John Edensor Littlewood, Harold Davenport, Kurt Mahler, Louis Mordell, y Paul Erdős.
Lehmer continuó en Lehigh durante el año lectivo de 1939-1940.
Lehmer seguiría desarrollándose activamente en la computación durante el resto de su carrera.
Lehmer aceptó una posición como Director del Instituto para Análisis Numérico(INA) de la Agencia Nacional de Estándares, trabajando con la Standards Western Automatic Computer (SWAC).
John Selfridge invitó en dos ocasiones a los Lehmer a pasar un semestre en la Universidad del Norte de Illinois, en una ocasión Selfridge arregló que Erdős y Lehmer dieran juntos un curso de Problemas de Investigación en la Teoría de Números, Lehmer enseñó las primeras ocho semanas y Erdős el resto del curso.