Problems & Puzzles: Puzzles

Puzzle 524. x = 1 (mod phi(x)) Farideh Firoozbakt sent the following puzzle: We know that: 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.

***

Noe wrote:

This is a difficult unsolved problem. See section B37 of Richard Guy's
book "Unsolved Problems in Number Theory" for the status of this problem up
to 2004. D. H. Lehmer conjectured that there is no composite solution.

***

Antoine wrote:

In “ Recreations in the theory of numbers “ A.H.Beiler writes on p.92-93 :

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 distinct primes.
No solution is known. It is suspected that a solution for a composite number
x is impossible.

B. k * phi( x ) = x + 1 has solutions.

***

Emmanuel wrote:

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 link:
http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.rmjm/1250127235
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 primefactors.

***

Colin wrote:

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 phi(n)=1.

I also see on http://www.pateysoft.fr/Conjecture-de-Lehmer-sur-la.html 
(*) 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 (*).
 

***