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 n1=0
(mod ö(n)) then n is a Carmichael number.
Proof: Let a be prime to n ,so a^ö(n)=1 (mod n),
since n1=0 (mod ö(n)) there exist a nonnegative integer
m such that n1= m*ö(n)) therefore a^(n1)=(a^ö(n))^m then a^(n1)=1 (mod
n), so n is a Carmichael number.
Lemma.1: If n is a composite number and n1=0 (mod
ö(n)) then n is an odd squarefree number.
Proof: Suppose that n is a composite number and
n1=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)=
(p11)*(p21)*...*(pk1)*p1^(m11)*p2^(m21)*...*pk^(mk1)
hence for j=1,...,k we have pj^(mj1) divides n1,
so if for some i (1 <=i <=k) mi1 > 0 we get pi
divides n1 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 n1=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 n1, (p*q1)/((p1)(q1)) is a natural number,
but, (p*q1)/((p1)(q1))=1+1/(p1)+1/(q1) (II)
so, 1< (p*q1)/((p1)(q1))<= 1+1/2+1/4 therefore
(p*q1)/((p1)(q1)) can't be an integer which is a contradiction.
Lemma.3: If n is a composite number and n1=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
n1, (p*q*r1)/((p1)(q1)(r1)) is an integer,
we use of the nice relation (III):
(p*q*r1)/((p1)(q1)(r1))=1+ 1/(p1)+ 1/(q1)+
1/(r1)+ 1/((p1)(q1)) (III) + 1/((q1)(r1))+ 1/((p1)(r1))
Let assume, A=(p*q*r1)/((p1)(q1)(r1))
we have the following cases:
case.1 : p>3
since p>=5,q>=7 and r>=11 by using (III) ,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*71)/(2*4*6)=13/6
case.2.1.2 : p=3, q=5 & r=11 then
A=(3*5*111)/(2*4*10)=41/20
case.2.1.3 : p=3, q=5 & r=13 then
A=(3*5*131)/(2*4*12)=97/48
case.2.1.4 : p=3, q=5 & r>13 since r>=17 by using
(III) ,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 (III) ,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 n1 divides n and the proof is complete.
So we have the following theorem :
Theorem. If n is a composite number and n1=0 (mod
ö(n)) then n is an odd squarefree number with at least four prime
divisors.
I think by using of the generalization of (III) 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 n1=0 (mod ö(n)) then n is an odd squarefree 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
n1=0 (mod ö(n)) A=(p*q*r*z1)/((p1)(q1)(r1)(z1)) is an integer
number. we have relation (IIII) (and it's
generalization):
(p*q*r*z1)/((p1)(q1)(r1)(z1))=
1+1/(p1)+1/(q1)+1/(r1)+1/(z1)+ 1/((p1)(q1))+1/((p1)(r1))
+1/((p1)(z1))+1/((q1)(r1))+1/((q1)(z1))+1/((r1)(z1))
+1/((q1)(r1)(z1))+1/((p1)(r1)(z1)
+1/((z1)(q1)(z1))+1/((p1)(q1)(r1)) (IIII)
If we define f(a,b,c,d)=(a*b*c*d1)/((a1)(b1)(c1)(d1)) (a,b,c&d are
greater than 2) then by using (IIII) 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*z1)/(31)(51)(131)*(z1),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 n1=0 (mod ö(n)).
Daniel wrote:
Of course n = 1 (mod phi(n)) if n is prime:
phi(n) = n1, 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^(k1) = (p1) * p^(k1)
n = phi(n) + p^(k1) = p^(k1) (mod phi(n))
For p >= 3, k > 1 we have:1 < p^(k1) < p^k  p^(k1)
1 < n % (phi(n)) < phi(n) [% as "modulo" in C++,
giving the smallest nonnegative 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) = (p1)*(q1) = 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(k1)) is a factor of phi(n), so p 
phi(n) n = 1 (mod phi(n)) means that phi(n)  (n1).
If p  phi(n) and phi(n)  (n1), then p  (n1).
This is impossible because p  n
2) Assume that n is squarefree.
Let n = p1 * ... * pn, n > 1.
Hence phi(n) = (p11) * ... * (pn1).
Every factor is even and we have at least two
factors, so 4  phi(n). n = 1 (mod phi(n)) means that phi(n)  (n1). if 4
 phi(n) and phi(n)  (n1), then 4  (n1). 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 n1=0 (mod φ(n))
exist.
Let n’s
prime factorization be n = p_{1}^a_{1}.p_{2}^a_{2}.p_{3}^a_{3}...p_{m}^a_{m},
Then
phi(n) = (p_{1}1).p_{1}^(a_{1}1).(p_{2}1).p_{2}^(a_{2}1).(p_{3}1).p_{3}^(a_{3}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_{1}.p_{2}.p_{3}...p_{m}
and phi(n) = (p_{1}1).(p_{2}1).(p_{3}1)...(p_{m}1)
Since
at least one p_{j} is odd, phi(n) is even so n1 is even.
Therefore n must be odd, and all p_{j} are odd.
Take p_{1}<p_{2}<p_{3}<....<p_{m}
and define r = n/p_{m}
then if
p_{m}>r, (p_{m}1).r = nr > np_{m} and (p_{m}1).(r+1)
= nr + p_{m}  1 > n1 so (p_{m}1) does not divide (n1)
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 n1, 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.kobepharmau.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)<n1 so for the condition required we need
n1 = k.phi(n), k>1 k =
(n1)/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 3prime
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 (n1), n == 1 mod 64, and probably a much higher
power of two.
Testing
k = (n1)/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 kvalue 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
3637 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.
***