Problems & Puzzles:
x = 1 (mod phi(x))
Farideh Firoozbakt sent the following
if p is
prime then p is a solution for the equation,
x = 1 (mod phi(x)) (*).
Q1. Can you find a composite solution
for (*) ?
(Note: We can easily show that if n is a
composite solution of (*) then n is odd and square-free).
Contributions came from T. D. Noe, Antoine
Verroken, Emmanuel Vantieghem & J-C Colin.
This is a difficult unsolved problem. See section B37 of Richard
book "Unsolved Problems in Number Theory" for the status of this
to 2004. D. H. Lehmer conjectured that there is no composite
In ď Recreations in the theory of numbers ď A.H.Beiler writes on
A k * phi( x ) = x Ė 1
1. k = 1 any prime , x , is a solution
2. when x is composite phi(x), must differ from x by more than unity
3. k > 1 , x composite ; x must be the product of at least 7
No solution is known. It is suspected that a solution for a
x is impossible.
B. k * phi( x ) = x + 1 has solutions.
The puzzle seems somewhat ambitious since the puzzle is the
famous unsolved problem of Lehmer. See R.K.Guy, Unsolved Problems in
Elementary Number Theory, Problem B37. You also can have direct
access to the present state of knowledge by using the following
There, among others, you can learn that any candidate for a solution
to the congrence x = 1 (mod phi(x)) should have at least 14
I seached up to 10^7 an x / x mod phi(x)=1 (*) and I found
nothing, I think, because of Derrick Lehmer conjecture on the
Euler's totient function which says n is prime if and only if n mod
I also see on
(*) hence n or x in puzzle 524, if not prime, may be only a
CarmichaŽl number. So I tested all CarmichaŽl numbers up to 16
digits included and no one verifies (*).
So my answer to puzzle 524 is : it's impossible to find a number not
prim which verifies (*).