mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2018-03-04, 20:10   #1
JM Montolio A
 
Feb 2018

25·3 Posts
Post Carmichael conjecture

Carmichael conjecture: for any even k,
the number of solutions of totient(s)=k, never is one.
 
A first look on solutions.
k, Odd, Even.
1 1 2*1
2 3 4*1 2*3
4 5 8*1 4*3 2*5
6 7 9 2*7 2*9
8 15 16*1 8*3 4*5 2*15
10 11 2*11
 
I find some rules.
Rule 1. Any even solution becomes of a previous odd solution.
Sources for the odd solutions.
Rule 2. If (k+1) is prime.
Rule 3. If k=(p-1)*(p^e), with p is prime.
Rule 4. The odd solution of form pq.
If k=a*b. All even.
And a with some odd solution p. And b with some odd solution q.
And p,q are coprimes. Then p*q is a odd solution for k.
Example. k= 24 =2*12 =4*6. Odd solutions 3*13, 5*7, 5*9.
 
Rule 5. k without solutions. k=2p, p prime, and (2p+1) composite.
Rule 6. k with a even solution n=4*(odd), implies a odd solution.
Example. k=20, s=4*11, implies s=3*11.
 
Definitions
s prime, #sol(k,PR) (0/1)
s odd composite, #sol(k,CO)
s = 2*Odd, #sol(k,2I)
s = (4,8,...)*Odd, #sol(k,PI)
Then we have:
Rule 7. #sol(k,2I)= #sol(k,PR)+#sol(k,CO)
Rule 8. #sol(k,PI)= #sol(k/2,2I)+#sol(k/2,PI)

k---------PR CO 2I PI
-----------------------------
k 2 #sol: 1 0 1 1
k 4 #sol: 1 0 1 2
k 6 #sol: 1 1 2 0
k 8 #sol: 0 1 1 3
k 10 #sol: 1 0 1 0
k 12 #sol: 1 1 2 2
k 14 #sol: 0 0 0 0
 
The unsolved case: k, no odd solution, but with one alone even solution.

Last fiddled with by JM Montolio A on 2018-03-04 at 20:24
JM Montolio A is offline   Reply With Quote
Old 2018-03-04, 20:24   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by JM Montolio A View Post
Carmichael conjecture: for any even k,
the number of solutions of totient(s)=k, never is one.
 
A first look on solutions.
k Odd solutions Even solutions
---------- ------------- -------------------------------
1 1 2*1
2 3 4*1 2*3
4 5 8*1 4*3 2*5
6 7 9 2*7 2*9
8 15 16*1 8*3 4*5 2*15
10 11 2*11
--------------------------------------------------------
 
I find some rules.
Rule 1. Any even solution becomes of a previous odd solution.
Sources for the odd solutions.
Rule 2. If (k+1) is prime.
Rule 3. If k=(p-1)*(p^e), with p is prime.
Rule 4. The odd solution of form pq.
If k=a*b. All even.
And a with some odd solution p. And b with some odd solution q.
And p,q are coprimes. Then p*q is a odd solution for k.
Example. k= 24 =2*12 =4*6. Odd solutions 3*13, 5*7, 5*9.
 
Rule 5. k without solutions. k=2p, p prime, and (2p+1) composite.
Rule 6. k with a even solution n=4*(odd), implies a odd solution.
Example. k=20, s=4*11, implies s=3*11.
 
Definitions
s prime, #sol(k,PR) (0/1)
s odd composite, #sol(k,CO)
s = 2*Odd, #sol(k,2I)
s = (4,8,...)*Odd, #sol(k,PI)
Then we have:
Rule 7. #sol(k,2I)= #sol(k,PR)+#sol(k,CO)
Rule 8. #sol(k,PI)= #sol(k/2,2I)+#sol(k/2,PI)

PR CO 2I PI
-----------------------------
k 2 #sol: 1 0 1 1
k 4 #sol: 1 0 1 2
k 6 #sol: 1 1 2 0
k 8 #sol: 0 1 1 3
k 10 #sol: 1 0 1 0
k 12 #sol: 1 1 2 2
k 14 #sol: 0 0 0 0
-----------------------------
 
The unsolved case: k, no odd solution, but with one alone even solution.
For any odd n, it sufffices to double it as you noticed. It then follows, that the conjecture holds if there's at least one odd n solution for every even k.
science_man_88 is offline   Reply With Quote
Old 2018-03-04, 20:32   #3
JM Montolio A
 
Feb 2018

11000002 Posts
Smile Yes. ¿ we can proof it from the rules ?

Yes. ¿ we can proof it from the rules ?
JM Montolio A is offline   Reply With Quote
Old 2020-04-20, 09:16   #4
Tooryalai
 
May 2019

2 Posts
Default Proof

Carmichael's Totient Function Conjecture



Carmichael's totient function conjecture concerns the multiplicity of values of Euler's totient function φ(n), which counts the number of integers less than and coprime to n. It states that, for every n there is at least one other integer m ≠ n such that φ(m) = φ(n).



1.​Proving the conjecture is equivalent to proving that the conjecture holds for all integers congruent to 4 (mod 8).



I.​m = 4 (mod 8) = 8 * x + 4 = 4 * (2 * x + 1) = 4 * k; k = Odd



II.​m / 2 = ( 4 * k ) / 2 = 2 * k



III.​If you divide m by 2, then you also divide φ(m) by 2



IV.​φ(m) = (φ(m) / 2) * 2



i.​Note that φ(k) = φ(2 * k) = (φ(m) / 2)



ii.​Note that φ(3) = 2



iii. φ(m) = (φ(m) / 2) * 2 = φ(k) * φ(3)



iv.​If gcd(k, 3) = 1, then φ(k * 3) = φ(k) * φ(3)



v.​If you only want m to be a value for φ(m), then k must be a multiple of 3,

else n = k * 3 and φ(m) = φ(n)



vi.​Note that (φ(m) / 2) / 2 must be a nontotient, else (2 scenarios):



a.​for some positive odd integer p & some positive even integer2 * p,

φ(p) = φ(2 * p) = (φ(m) / 2) / 2; then φ(4 * p) = (φ(m) / 2); and

finally, φ(8 * p) = φ(m)



b.​or for some positive even integer q (q divisible by at least 4) φ(q) =

(φ(m) / 2) / 2; then φ(2 * q) = (φ(m) / 2); and finally, φ(4 * q) =

φ(m)



vii.​If (φ(m) / 2) / 2 is a nontotient, then φ(m) / 2 must also be a nontotient

as a result of the following:



a.​Farideh Firoozbakht (Dec 30, 2005) generalized that if N is a

nontotient and 2N+1 is composite, then 2N is also a nontotient.



b.​Note that the only values allowed for φ(k) = φ(2 * k) = (φ(m) / 2) are

k and 2 * k; if (φ(m) / 2) were to exist according to “a” above, then

k would have to be prime thereby contradicting “IV:v”



viii.​Therefore, (φ(m) / 2) = 2 * j, j = Odd



a.​However, the only values satisfying φ(k) = φ(2 * k) = (φ(m) / 2) = 2 *

j (for k a multiple of 3) are perfect powers of 3 as can be seen

below:



i.​For s = 3^r * t and t not divisible by 3, φ(3 * s) = 3^r * 2 *

φ(t)



ix.​k =3^h, and φ(3^h) = (3-1) * 3^(h-1) = 2 * 3^(h-1)= (φ(m) / 2)



x.​φ(m) = 2 * 2 * 3^(h-1)= 4 * 3^(h-1)



xi.​Set h = 2 and φ(m) = 4 * 3^(2-1)= 4 * 3 = 12 = φ(21)



xii.​For all h > 2, φ(m) = 4 * 3^(h-1)= φ(i) = φ(21 * 3^(h-2))



a.​i is divisible by 7 and so φ(m) = φ(i), m ≠ i



2.​Hence, the conjecture is true.
Tooryalai is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Carmichael numbers devarajkandadai Number Theory Discussion Group 14 2017-11-15 15:00
Carmichael Numbers Stan Miscellaneous Math 19 2014-01-02 21:43
Carmichael numbers (M) something devarajkandadai Miscellaneous Math 2 2013-09-08 16:54
Carmichael Numbers devarajkandadai Miscellaneous Math 0 2006-08-04 03:06
Carmichael Numbers II devarajkandadai Math 1 2004-09-16 06:06

All times are UTC. The time now is 14:25.

Sat Aug 15 14:25:02 UTC 2020 up 2 days, 11 hrs, 1 user, load averages: 1.67, 1.79, 1.81

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.