No solution has been found but characterization of the potential solution has been produced by several puzzlers: Faride Firoozbakht, Jon Wharf, Daniel Gronau.

***

Faride wrote:

I proved the following facts:

Proposition : If n is a composite number and n-1=0 (mod ö(n)) then n is a Carmichael number.

Proof: Let a be prime to n ,so a^ö(n)=1 (mod n), since n-1=0 (mod ö(n)) there exist a non-negative integer m such that n-1= m*ö(n)) therefore a^(n-1)=(a^ö(n))^m then a^(n-1)=1 (mod n), so n is a Carmichael number.

Lemma.1: If n is a composite number and n-1=0 (mod ö(n)) then n is an odd square-free number.

Proof: Suppose that n is a composite number and n-1=0 (mod ö(n)) , since ö(n) for n > 2 is an even number n must be odd. Let n= p1^m1*p2^m2*...*pk^mk then,

ö(n)= (p1-1)*(p2-1)*...*(pk-1)*p1^(m1-1)*p2^(m2-1)*...*pk^(mk-1) hence for j=1,...,k we have pj^(mj-1) divides n-1, so if for some i (1 <=i <=k) mi-1 > 0 we get pi divides n-1 but we know pi divides n then pi divides 1 which is impossible. Therefore mj for j=1,...,k is equal to one and the proof is complete.

Lemma.2: If n is a composite number and n-1=0 (mod ö(n)) then n has at least three distinct prime divisors .

Proof: Assume n has only two distinct prime divisors by the lemma.1 n= p*q were p & q are distinct odd primes. Since ö(n) divides n-1, (p*q-1)/((p-1)(q-1)) is a natural number, but, (p*q-1)/((p-1)(q-1))=1+1/(p-1)+1/(q-1) (I-I) so, 1< (p*q-1)/((p-1)(q-1))<= 1+1/2+1/4 therefore (p*q-1)/((p-1)(q-1)) can't be an integer which is a contradiction.

Lemma.3: If n is a composite number and n-1=0 (mod ö(n)) then n has has at least four distinct prime divisors .

Proof : We know n is odd, we must show n hasn't only three distinct prime divisors, if p, q&r(p<q<r) are the only distinct prime divisors of n ,by the lemma.1 n= p*q*r , since ö(n) divides n-1, (p*q*r-1)/((p-1)(q-1)(r-1)) is an integer, we use of the nice relation (I-II):

(p*q*r-1)/((p-1)(q-1)(r-1))=1+ 1/(p-1)+ 1/(q-1)+ 1/(r-1)+ 1/((p-1)(q-1)) (I-II) + 1/((q-1)(r-1))+ 1/((p-1)(r-1))

Let assume, A=(p*q*r-1)/((p-1)(q-1)(r-1)) we have the following cases:

case.1 : p>3

since p>=5,q>=7 and r>=11 by using (I-II) ,we get  1<A<=1+1/4+1/6+1/10+1/24+1/60 +1/40 ,so 1 < A < 8/5.

case.2.1.1 : p=3, q=5 & r=7 then A=(3*5*7-1)/(2*4*6)=13/6

case.2.1.2 : p=3, q=5 & r=11 then A=(3*5*11-1)/(2*4*10)=41/20

case.2.1.3 : p=3, q=5 & r=13 then A=(3*5*13-1)/(2*4*12)=97/48

case.2.1.4 : p=3, q=5 & r>13 since r>=17 by using (I-II) ,we get 1<A<=1+ 1/2+ 1/4+ 1/16+ 1/8+ 1/64 +1/32 ,so 1 < A < 127/64.

case.2.2 : p=3, q>=7 since r>=11 by using (I-II) ,we get 1<A<=1+ 1/2+ 1/6+ 1/10+ 1/12+ 1/60+ 1/20 ,so 1 < A < 23/12. we see in all cases A can't be integer ,which is contradiction. with n-1 divides n and the proof is complete.

So we have the following theorem :

Theorem. If n is a composite number and n-1=0 (mod ö(n)) then n is an odd square-free number with at least four prime divisors.

I think by using of the generalization of (I-II) we can prove that every such number has more than four prime divisors, we must verify many cases. I think if there exist such number it must be large .

Later she added:

 Theorem.2: If n is a composite number and n-1=0 (mod ö(n)) then n is an odd square-free number with at least five prime divisors.

Proof: By using the previous theorem we must show n isn't of the form p*q*r*z where p,q,r&z are distinct primes,suppose that n=p*q*r*z since n-1=0 (mod ö(n)) A=(p*q*r*z-1)/((p-1)(q-1)(r-1)(z-1)) is an integer number. we have relation (I-III) (and it's generalization):

(p*q*r*z-1)/((p-1)(q-1)(r-1)(z-1))= 1+1/(p-1)+1/(q-1)+1/(r-1)+1/(z-1)+ 1/((p-1)(q-1))+1/((p-1)(r-1)) +1/((p-1)(z-1))+1/((q-1)(r-1))+1/((q-1)(z-1))+1/((r-1)(z-1)) +1/((q-1)(r-1)(z-1))+1/((p-1)(r-1)(z-1) +1/((z-1)(q-1)(z-1))+1/((p-1)(q-1)(r-1)) (I-III)

If we define f(a,b,c,d)=(a*b*c*d-1)/((a-1)(b-1)(c-1)(d-1)) (a,b,c&d are greater than 2) then by using (I-III) we deduce that "f is a decreasing function relative to each variable" we use this fact (that we call this,(**)) to show that A can't be an integer which is a contradiction. we have only following cases:

Case1 : p > 3

since p >= 5,q >= 7,r >= 11,z >= 13 by using (**)we get 1 < A <= 139/80 .

case 2.1.1 p=3,q=5,r < 17 since 7 <= r<=13 and z >= 11 by using (**) we get Limit((3*5*13*z-1)/(3-1)(5-1)(13-1)*(z-1),z->infinity) < A <= 577/240 so 65/32 < A <= 577/240

case 2.1.2.1 p=3,q=5,r=17, z < 3*5*17 since z <= 251 by using (**) we get 16001/8000 <= A <= 1211/576

case 2.1.2.2 p=3,q=5,r=17, z > 3*5*17 since z >= 263 by using (**) we get 1< A <= 8383/4192.

case 2.1.3.1 p=3,q=5,r=19, z<=89 by using (**) we get 6341/3168 <= A <= 3277/1584

case 2.1.3.2 p=3,q=5,r=19, z > 89 since z >= 97 by using (**) we get 1 < A <= 6911/3456

case 2.2.1.1 p=3,q=7,r=11, z <= 23 since 13 <= z <= 23 by using (**) we get 332/165 <= A <= 1963/960 case 2.2.1.2 p=3,q=7,r=11, z > 23 since z <= 29 by using (**) we get 1 <= A <= 3349/1680

case2.2.2.1 p=3,q=7,r=13, z=17 in this case A=145/72

case2.2.2.2 p=3,q=7,r=13, z=19 in this case A=2593/1296

case2.2.2.3 p=3,q=7,r=13, z>19 since z >= 23 by using (**) we get 1 < A <= 3139/1584

case2.2.3 p=3,q=7,r>13, z>19 since r >= 17 and z >= 23 by using (**) we get 1 <= A <= 3391/1728

So in all cases A can't be an integer number and the proof is complete.

**********************************

Spoof such number: If we suppose (incorrectly) that 255 is prime and n=3*5*17*255 then n-1=0 (mod ö(n)).

Daniel wrote:

Of course n = 1 (mod phi(n)) if n is prime: phi(n) = n-1, n = phi(n) + 1 = 1 (mod phi(n)) ==> For any prime number n we have n = 1 (mod phi(n))

Lets eliminate the easiest cases for composites:

For n > 2 we know that phi(n) is even. Hence if n is even too (and n > 2) then n = 1 (mod phi(n)) is impossible. ==> For an EVEN composite number n we have NEVER n = 1 (mod phi(n))

Let n = p^k with p prime and k > 1. phi(n) = p^k - p^(k-1) = (p-1) * p^(k-1)

n = phi(n) + p^(k-1) = p^(k-1) (mod phi(n))

For p >= 3, k > 1 we have:1 < p^(k-1) < p^k - p^(k-1)

1 < n % (phi(n)) < phi(n) [% as "modulo" in C++, giving the smallest non-negative residue] ==> For n = p^k, k>1 and p prime we have NEVER n = 1 (mod phi(n))

Let n = p * q, p and q are distinct odd primes.

phi(n) = (p-1)*(q-1) = pq + 1 - (p+q)

n = phi(n) - 1 + p + q = p + q - 1 (mod phi(n))

We have: 1 < p + q - 1 < pq + 1 - (p+q)

(To prove the second relation p + q - 1 < pq + 1 - (p+q) 2p + 2q < pq + 2 2p/q + 2 < p + 2/q Because 2p/q < p (for q > 2) and 2 < 2/q (for q > 1) the last relation holds Of course we get the same for p.)

So we have:

1 < n % (phi(n)) < phi(n) ==> For n = p * q, p and q are distinct odd primes, we have NEVER n = 1 (mod phi(n))

Not much, but a starting point...

Later he added:

I found stronger conditions:

THEOREM: If n = 1 (mod phi(n)) holds for composite n, then: 1) n has to be squarefree (there is no x > 1 with x² | n ) 2) n = 1 (mod 4) 3) n has at least three prime factors

PROOF:

1) Assume that p^k | n for a prime number p and k > 1. Hence (p^k - p(k-1)) is a factor of phi(n), so p | phi(n) n = 1 (mod phi(n)) means that phi(n) | (n-1). If p | phi(n) and phi(n) | (n-1), then p | (n-1). This is impossible because p | n

2) Assume that n is squarefree.

Let n = p1 * ... * pn, n > 1. Hence phi(n) = (p1-1) * ... * (pn-1).

Every factor is even and we have at least two factors, so 4 | phi(n). n = 1 (mod phi(n)) means that phi(n) | (n-1). if 4 | phi(n) and phi(n) | (n-1), then 4 | (n-1). This is equivalent to n = 1 (mod 4)

3) This was proved in my last mail: For n = p * q and both factors prime we have: phi(n) = pq + 1 - p - q n = phi(n) - 1 + p + q. All we have to show is that phi(n) + 1 < n < 2*phi(n), which implies that n = 1 (mod phi(n)) is impossible.

The first relation holds:phi(n) + 1 < phi(n) - 1 + p + q 1 < p + q - 1, which is true for p >= 3, q >= 2 The second relation holds too: phi(n) - 1 + p + q < 2*phi(n) p + q - 1 < phi(n) p + q - 1 < p*q + 1 - p - q 2(p + q) < pq + 2 p + q < pq/2 + 1 | divide by p 1 + q/p < q/2 + 1/p

Because 1 < 1/p and q/p < q/2 (for p > 2) the relation holds.

Jon wrote:

I believe that no composite numbers satisfying n-1=0 (mod φ(n)) exist.

Let n’s prime factorization be n = p₁^a₁.p₂^a₂.p₃^a₃...p_m^a_m,

Then phi(n) = (p₁-1).p₁^(a₁-1).(p₂-1).p₂^(a₂-1).(p₃-1).p₃^(a₃-1).....(p_m-1).p_m^(a_m-1).

If some a_j>1 then p_j divides both n and phi(n) and therefore also divides n mod phi(n).

So all a_j are =1, n is squarefree.

So n=p₁.p₂.p₃...p_m and phi(n) = (p₁-1).(p₂-1).(p₃-1)...(p_m-1)

Since at least one p_j is odd, phi(n) is even so n-1 is even. Therefore n must be odd, and all p_j are odd.

Take p₁<p₂<p₃<....<p_m and define r = n/p_m  then if p_m>r, (p_m-1).r = n-r > n-p_m and (p_m-1).(r+1) = n-r + p_m - 1 > n-1 so (p_m-1) does not divide (n-1)  therefore p_m<r , i.e.. the largest prime factor of n must be less than sqrt(n)

Also it directly follows that n must have at least three prime factors.

Also, because each p_j-1 divides n-1, n must be a Carmichael number. In consequence I have taken to calling any solutions to this puzzle “SuperCarmichaels”.

I tested the Carmichaels up to 10^12 with no success (using the list at http://www.kobepharma-u.ac.jp/~math/note/note02.txt ). I then made further progress through the Carmichael numbers at ftp://ftp.dpmms.cam.ac.uk/pub/Carmichael/ , testing all Carmichaels up to 10^16. No SuperCarmichaels were found, so n>10^16.

Since n is composite (m>1) then phi(n)<n-1 so for the condition required we need n-1 = k.phi(n), k>1 k = (n-1)/phi(n) is increased with more prime factors and with smaller prime factors. for n = 3 . 5 = 15, k=14/8 = 7/4 < 2

We can restrict the combinations of primes (just as for Carmichaels); we cannot have p_j divides any other p_i-1. Using this restriction I also tested whether we can produce k=> 2 with just three primes. Omitting either 3 or 5 immediately disqualifies a 3-prime solution. With both 3 and 5 the next eligible prime is 17 which fails to achieve k=2.

So we need at least 4 prime factors to get to k=2 and given the requirements for n > 10^16 and p_m < sqrt(n) we will need another two large prime factors to achieve this, so n has at least 6 prime factors Also because each (p_j-1) brings at least one factor of 2 to (n-1),  n == 1 mod 64, and probably a much higher power of two.

Testing k = (n-1)/phi(n), only 9 Carmichaels < 10^16 (out of 246683) have k>2:

n	k
1886616373665 158353658932305 269040992399565 655510549443465 881715504450705 1817671359979245 3193231538989185 3852971941960065 6128613921672705	2.1143 2.0321 2.0307 2.0039 2.0813 2.0361 2.1149 2.0016 2.0889	highest k closest to k=2

Only 143 have k>1.75  (The impressive 62745 = 3*5*47*89 has k=1.937 which is the highest k-value until 1886616373665 )

 I also tested some of the large Carmichael numbers generated by Löh and Niebuhr (A New Algorithm for Constructing Large Carmichael Numbers), but the k values were around 1.7. Their 81488 digit Carmichael with 10058 factors gave a k of 1.779.

Thanks to the sources noted on Carmichael numbers and (as ever) for Joe Crump’s Excel addin.

***

As a matter of fact, I have learned during this week (thanks to my friend Enoch Haga, who pointed out to me the pages 36-37 from the Ribenboim's well known book) that this question goes back to Lehmer, who first studied (1932) this nothing simple question.

Lehmer demonstrated then that, if it exists at all, n should be odd, square free and w(n)=> 6 [w(n)= quantity of distinct factors of n].

More recently (1980) Cohen and Hagis showed that n>10^20 and  w(n)=>14. Wall showed that if 30 does not divides n then w(n)=>26, while Lieuwens (1970) showed that if 3 divides n then w(n)>213 and n>5.5x10^570.

***