Carmichael conjecture

[JM Montolio A]

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.

[science_man_88]

Originally Posted by JM Montolio A

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.

[JM Montolio A]

Yes. ¿ we can proof it from the rules ?

[Tooryalai]

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.