El totient de Euler y los divisores cuentan la relación de función cuando $[( \frac { \varphi (n)}{2}+1) \cdot ( \frac { \tau (n)}{2}+1)] = n$

Question

Estoy estudiando la función totient de Euler $ \varphi (n)$ y la función de contar los divisores, $ \tau (n)$ también llamado $d(n)$ y recientemente abrió una pregunta (enlace aquí) sobre la siguiente condición:

(1) $\ \forall n \ge3 $ si $( \frac { \varphi (n)}{2}+1)\ \mid\ n\ $ entonces $( \frac { \varphi (n)}{2}+1) \in \Bbb P$

Quería hacer el mismo ejercicio, pero agregando una restricción extra con respecto a la función de conteo de divisores, $ \tau (n)$ y encontré lo siguiente en el intervalo $[3,29] \cup [31,10^9]$ excepto por un solo contra-ejemplo aislado en $n=30$ :

(2) $\ \forall n \in [3,29] \cup [31,10^9]$ ,

si $[( \frac { \varphi (n)}{2}+1)\ \mid\ n]\ \land\ [( \frac { \tau (n)}{2}+1)\ \mid\ n]\ $ entonces $[( \frac { \varphi (n)}{2}+1) \cdot ( \frac { \tau (n)}{2}+1)] = n$

Así que básicamente cuando la condición (1) ocurre y también la restricción $( \frac { \tau (n)}{2}+1) \mid n$ sucede, entonces ambos $( \frac { \varphi (n)}{2}+1)$ y $( \frac { \tau (n)}{2}+1)$ son factores de $n$ y si se multiplican son exactamente $n$ .

Por ejemplo..:

$n=21\ ,\ ( \frac { \varphi (21)}{2}+1)=7 = a\ ,\ ( \frac { \tau (21)}{2})+1=3 = b\ ,$ y $a \cdot b = 7 \cdot3 = 21$

$n=999993\ ,\ ( \frac { \varphi (999993)}{2}+1)=333331 = a\ ,\ ( \frac { \tau (999993)}{2})+1=3 = b\ ,$ y $a \cdot b = 333331 \cdot3 = 999993$

El único contraejemplo que he encontrado hasta ahora es:

$n=30\ ,\ ( \frac { \varphi (30)}{2}+1)=5 = a\ ,\ ( \frac { \tau (30)}{2})+1=5 = b\ ,$ y $a \cdot b = 5 \cdot 5 = 25 \not = 30$

He estado leyendo acerca de las propiedades de las funciones de conteo tanto del totiente como del divisor, pero no entiendo por qué siempre parece suceder (2), excepto por $n=30$ así que quería compartir con ustedes estas preguntas:

1. ¿Es trivial? Se puede obtener conociendo las propiedades de $ \varphi (n)$ y $ \tau (n)$ ?
2. ¿Hay otro contraejemplo para $n \gt10 ^9$ ?

Si alguien pudiera comprobar más allá sería muy apreciado. Cualquier pista o explicación sobre el porqué (2) sucede es muy bienvenida, ¡gracias!

ACTUALIZACIÓN 2015/05/25

Probado hasta $10^9$ no se encontraron contramuestras aparte de $n=30$ . Aquí está el código PARI/GP:

eulerdiv(limitval)={
   for (n = 1, limitval,
      mytot = (eulerphi(n)/2)+1;
      mydiv = (numdiv(n)/2)+1;

      if ((n%mytot==0) && (n%mydiv==0),
         if((mytot*mydiv)==n,,print("Counterexample: "," ",n," ",mytot," ",mydiv)
         )
      )
   ) 
 }

Answer 1

Esta respuesta prueba la afirmación asumiendo que

(1) $\ \forall n \ge3 $ si $( \frac { \varphi (n)}{2}+1)\ \mid\ n\ $ entonces $( \frac { \varphi (n)}{2}+1) \in \Bbb P$

es cierto, pero no parece estar probado en su otro puesto.

Con (2) y (3) denotan

(2) $[( \frac { \varphi (n)}{2}+1)\ \mid\ n]\ \land\ [( \frac { \tau (n)}{2}+1)\ \mid\ n]\ $

(3) $[( \frac { \varphi (n)}{2}+1) \cdot ( \frac { \tau (n)}{2}+1)] = n$

Queremos saber si (2) implica (3).

---

Tenemos $$ \frac { \varphi (n)}{2}+1 > \frac {n}{2e^{ \gamma } \log \log n + \frac {6}{ \log \log n}}+1$$

$$ \frac { \tau (n)}{2}+1 \leq \sqrt {n}+1$$

La primera encuadernación ha sido probada en Rosser y Schoenfeld (1962). La segunda encuadernación es elemental.

---

Para $n > 88$ tenemos

\begin {alinear} 2e^{ \gamma } \log \log n + \frac {6}{ \log \log n} &< \sqrt {n} \\ \frac {n}{2e^{ \gamma } \log \log n + \frac {6}{ \log \log n}} &> \frac {n}{ \sqrt {n}} \\ \frac {n}{2e^{ \gamma } \log \log n + \frac {6}{ \log \log n}}+1 &> \frac {n}{ \sqrt {n}}+1 \\ \frac { \varphi (n)}{2}+1 &> \frac { \tau (n)}{2}+1 \end {alinear}

Desde $ \frac { \varphi (n)}{2}+1$ es una primicia de (1), $ \frac { \varphi (n)}{2}+1$ y $ \frac { \tau (n)}{2}+1$ no tienen un factor común. Por lo tanto, si se clasifican (2) el producto de ellos no puede ser más grande que $n$ .

---

Lema 1. Para cualquier $n >88$ si (2) está clasificado, entonces $$ \left ( \frac { \tau (n)}{2}+1 \right ) \left ( \frac { \varphi (n)}{2}+1 \right ) \leq n$$

$$ \left ( \frac { \tau (n)}{2}+1 \right )< \left ( \frac { \varphi (n)}{2}+1 \right )$$

---

Ahora observamos que si $n>88$ entonces $ \left ( \frac { \varphi (n)}{2}+1 \right )$ debe ser la mayor división primaria $n$ de lo contrario $ \left ( \frac { \tau (n)}{2}+1 \right )$ es ciertamente más grande. Se puede hacer una afirmación más fuerte:

Lema 2. Si $n=p_1^{e_1}p_2^{e_2}p_3^{e_3} \cdots p_k^{e_k}$ y todos $e_i \geq 2$ , $k \geq 2$ nunca es una estadística (2). Elija cualquiera de los $p_k$ como $ \frac { \varphi (n)}{2}+1$ y vemos que $ \frac { \tau (n)}{2}+1 > \frac { \varphi (n)}{2}+1$ . Por lo tanto, por Lemma 1 no puede hacer estadísticas (2).

---

Por lo tanto, el mayor primo $r$ en la factorización primaria, tiene el exponente uno. Escribimos $$n=kr , \quad \gcd (k,r)=1, \quad \frac { \varphi (n)}{2}+1=r$$ Desde $ \gcd (k,r)=1$ y $ \varphi $ es una función multiplicadora, que tenemos: $$ \varphi (n)= \varphi (kr)= \varphi (k) \varphi (r)= \varphi (k)(r-1)$$

\begin {alineado*} \frac { \varphi (n)}{2}+1 &= \frac { \varphi (k)(r-1)}{2}+1=r \\ \frac { \varphi (k)(r-1)}{2} & =r-1 \\ \varphi (k) &=2 \\ k=3 & \vee k=4 \end {alineado*}

---

Por lo tanto, un número $n>88$ que satisface (2) tiene la forma $3q$ o $4q$ para algunos primos $q$ .

• $n=4q$ , $ \varphi (n)=2(q-1)$ , $ \frac { \varphi (n)}{2}+1=q$ y $ \frac { \tau (n)}{2}+1=4$ así que satisface (3).

• $n=3q$ tenemos $ \varphi (n)=2(q-1)$ y $ \frac { \varphi (n)}{2}+1=q$ ,
  $ \frac { \tau (n)}{2}+1=3$ . Por lo tanto, satisface (3).

Por lo tanto, todos los números $n$ que satisfacen (2) satisfacen (3).

Usando tu trabajo, es válido para todos $3 \leq n \leq 29$ y $31 \leq n$ .