Problems & Puzzles: Puzzles

Puzzle 248.  Find one composite solution.

Ross Honsberger notices(*) that for the congruence:

n-1=0 (mod φ(n))

"... no composite solution is known... yet we are unable to declare there is none"

φ(n) is the Euler's totient function.

Question. Maybe you'll like to find one composite solution or to demonstrate that it can not happens that way.
_________
(*)p. 35, Mathematical Gems II, 1976.

Solution: 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 .

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...

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 = p1^a1.p2^a2.p3^a3...pm^am,

Then phi(n) = (p1-1).p1^(a1-1).(p2-1).p2^(a2-1).(p3-1).p3^(a3-1).....(pm-1).pm^(am-1).

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

So all aj are =1, n is squarefree.

So n=p1.p2.p3...pm and phi(n) = (p1-1).(p2-1).(p3-1)...(pm-1)

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

Take p1<p2<p3<....<pm and define r = n/pm  then if pm>r, (pm-1).r = n-r > n-pm and (pm-1).(r+1) = n-r + pm - 1 > n-1 so (pm-1) does not divide (n-1)  therefore pm<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 pj-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 pj divides any other pi-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 pm < sqrt(n) we will need another two large prime factors to achieve this, so n has at least 6 prime factors Also because each (pj-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.

*** Records   |  Conjectures  |  Problems  |  Puzzles  Home | Melancholia | Problems & Puzzles | References | News | Personal Page | Puzzlers | Search | Bulletin Board | Chat | Random Link Copyright © 1999-2012 primepuzzles.net. All rights reserved.