Autor Tema: Hallar todos los \(n\in\Bbb{N}\) tales que \(\varphi(n)=8\)

0 Usuarios y 1 Visitante están viendo este tema.

03 Marzo, 2021, 06:18 pm
Leído 728 veces

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,351
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola!

Hallar todos los \(n\in\Bbb{N}\) tales que \(\varphi(n)=8\), donde \( \varphi(n) \) es la función de Euler



Desde luego que no se conoce una expresión cerrada para la función inversa de Euler, por eso hay que "pensar un poco más".

Conozco las siguientes propiedades:

1) Si \( n \) es primo entonces \( \varphi(n)=n-1 \)

2) Si \( n \) es natural y \( p \) primo entonces \( \varphi(p^n)=p^n(1-1/p) \)

3) Si \( n,m \) son naturales y \( \gcd(n,m)=1 \) entonces \( \varphi(nm)=\varphi(n)\varphi(m) \)

4) \( \varphi(n)=\displaystyle n\cdot\prod_{p_i\mid n}\left(1-\frac{1}{p_i}\right),\quad \) con \( p_i \) los primos divisores de \( n \)

He encontrado dos posibles vías de solución, pero quisiera que me expliquen un poco cómo es que se llega a cada método (cómo funciona y por qué):

1º Método. Sabiendo que \( \sqrt{n}\leq\varphi(n)\leq n-1 \)

En este caso, elevando al cuadrado obtenemos \( n\leq64 \) y a partir de aquí se va probando hasta dar con las soluciones.

Pregunta: ¿Cómo se demuestra que para todo \( n\in\Bbb{N} \), \( \sqrt{n}\leq\varphi(n)\leq n-1 \) usando herramientas básicas?

2º Método. De forma analítica habiendo consultado el siguiente video: https://youtu.be/eAiVdJHnd8c

En particular creo que el ejemplo que más se ajusta es el que muestra a partir del minuto 7 (el de \( \varphi(x)=12 \)).

Si \( p \) es un primo que aparece en la factorización de \( n \) luego \( p-1\mid8,4,2,1 \), es decir \( p=9,5,3,2 \) descartamos \( 9 \) pues no es primo.

Luego \( 5,3\not\mid8 \) luego la multiplicidad de \( 5,3 \) es como mucho \( 1 \).

Tomemos \( n=5m \) con \( \gcd(5,m)=1 \): \( \varphi(n)=4\varphi(m)=8 \) luego \( \varphi(m)=2 \) de donde fácilmente se deduce que \( m=3,4,6 \) por lo tanto \( n=15,20,30 \) son soluciones de la ecuación original.

Pero ahora yo tomaría \( n=3o \) con \( \gcd(3,o)=1 \) tal como hace en el video pues \( 3\not\mid8 \), sin embargo al reemplazar me queda \( 8=2\varphi(o) \) de donde \( o=5,8,10,12 \), luego \( n=15,24,30,36 \) y algunas de estas NO son soluciones de la ecuación \( \varphi(n)=8 \). ¿Qué falla aquí?

Entonces intento hacer como hace en el video de tomar \( n=2^a3^b \) (que eran los otros 2 primos que faltaban), plantear que \( \varphi(n)=2^{a-1}(2-1)3^{b-1}(3-1) \) (¿por qué?), y esto a su vez es igual a \( 8=2^3 \), comparando término a término nos queda que \( a=3 \) y \( b-1=0 \), luego \( n=2^33^1=24 \). Por lo tanto TODAS las soluciones serían \( \boxed{n=15,20,30,\;24} \), SIN EMBARGO está faltando la solución \( n=16 \).

1) ¿Por qué si tomo \( n=3o \) tal como hace en el video, está mal?

2) ¿Por qué debo expresar a \( n \) de la forma \( 2^a3^b \) si \( 3\not\mid8 \) pero \( 2\mid8 \)?

3) ¿Por qué si lo expreso de dicha forma, me falta una solución?

Espero se entiendan mis consultas, sino preguntar por favor.

Gracias!!
Saludos

03 Marzo, 2021, 06:46 pm
Respuesta #1

feriva

  • $$\Large \color{#a53f54}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 9,651
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola!

Hallar todos los \(n\in\Bbb{N}\) tales que \(\varphi(n)=8\), donde \( \varphi(n) \) es la función de Euler



Desde luego que no se conoce una expresión cerrada para la función inversa de Euler, por eso hay que "pensar un poco más".

Conozco las siguientes propiedades:

1) Si \( n \) es primo entonces \( \varphi(n)=n-1 \)

2) Si \( n \) es natural y \( p \) primo entonces \( \varphi(p^n)=p^n(1-1/p) \)

3) Si \( n,m \) son naturales y \( \gcd(n,m)=1 \) entonces \( \varphi(nm)=\varphi(n)\varphi(m) \)

4) \( \varphi(n)=\displaystyle n\cdot\prod_{p_i\mid n}\left(1-\frac{1}{p_i}\right),\quad \) con \( p_i \) los primos divisores de \( n \)

He encontrado dos posibles vías de solución, pero quisiera que me expliquen un poco cómo es que se llega a cada método (cómo funciona y por qué):

1º Método. Sabiendo que \( \sqrt{n}\leq\varphi(n)\leq n-1 \)

En este caso, elevando al cuadrado obtenemos \( n\leq64 \) y a partir de aquí se va probando hasta dar con las soluciones.

Pregunta: ¿Cómo se demuestra que para todo \( n\in\Bbb{N} \), \( \sqrt{n}\leq\varphi(n)\leq n-1 \) usando herramientas básicas?

2º Método. De forma analítica habiendo consultado el siguiente video: https://youtu.be/eAiVdJHnd8c

En particular creo que el ejemplo que más se ajusta es el que muestra a partir del minuto 7 (el de \( \varphi(x)=12 \)).

Si \( p \) es un primo que aparece en la factorización de \( n \) luego \( p-1\mid8,4,2,1 \), es decir \( p=9,5,3,2 \) descartamos \( 9 \) pues no es primo.

Luego \( 5,3\not\mid8 \) luego la multiplicidad de \( 5,3 \) es como mucho \( 1 \).

Tomemos \( n=5m \) con \( \gcd(5,m)=1 \): \( \varphi(n)=4\varphi(m)=8 \) luego \( \varphi(m)=2 \) de donde fácilmente se deduce que \( m=3,4,6 \) por lo tanto \( n=15,20,30 \) son soluciones de la ecuación original.

Pero ahora yo tomaría \( n=3o \) con \( \gcd(3,o)=1 \) tal como hace en el video pues \( 3\not\mid8 \), sin embargo al reemplazar me queda \( 8=2\varphi(o) \) de donde \( o=5,8,10,12 \), luego \( n=15,24,30,36 \) y algunas de estas NO son soluciones de la ecuación \( \varphi(n)=8 \). ¿Qué falla aquí?

Entonces intento hacer como hace en el video de tomar \( n=2^a3^b \) (que eran los otros 2 primos que faltaban), plantear que \( \varphi(n)=2^{a-1}(2-1)3^{b-1}(3-1) \) (¿por qué?), y esto a su vez es igual a \( 8=2^3 \), comparando término a término nos queda que \( a=3 \) y \( b-1=0 \), luego \( n=2^33^1=24 \). Por lo tanto TODAS las soluciones serían \( \boxed{n=15,20,30,\;24} \), SIN EMBARGO está faltando la solución \( n=16 \).

1) ¿Por qué si tomo \( n=3o \) tal como hace en el video, está mal?

2) ¿Por qué debo expresar a \( n \) de la forma \( 2^a3^b \) si \( 3\not\mid8 \) pero \( 2\mid8 \)?

3) ¿Por qué si lo expreso de dicha forma, me falta una solución?

Espero se entiendan mis consultas, sino preguntar por favor.

Gracias!!
Saludos

Hola, manooooh.

Las consultas las dejo para quienes más saben. En cuanto a la cuestión... mucho arroz veo yo para tan poco pollo, a lo mejor estoy perdiéndome algo.

Spoiler

Tenemos

\( \varphi(n)=(p_{1}-1)(p_{2}-1)\cdot...(p_{n}-1)
  \) (para los factores primos de “n”).

De acuerdo en esto, supongo, pues sólo hay que efectuar las fracciones y verlo (perdón, esto es sólo si son libres de cuadrados; no vale del todo la idea)

Los primos menores que 8 son 2,3,5,7; restándoles 1, quedarían los siguientes factores: 1,2,4,6; donde el 6 queda descartado y tienes éstos, 1,2,4, correspondientes a los primos 2,3,5.

No sé... ahora mismo lo veo así de fácil, pero lo dejo en spoiler por si está mal.

(considerando eso con las posibilidades de los no libres de cuadrados, tampoco es difícil)

[cerrar]

Saludos.

03 Marzo, 2021, 07:27 pm
Respuesta #2

geómetracat

  • Moderador Global
  • Mensajes: 2,344
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Ten en cuenta que si \[ n=p_1^{r_1}\dots p_k^{r_k} \] es la descomposición en factores primos de \[ n \], entonces \[ \varphi(n)=p_1^{r_1-1}\dots p_k^{r_k-1}(p_1-1)\dots (p_k-1) \].
Esto no es más que tu fórmula 4) reescrita.

A partir de aquí se ve rápidamente que los únicos primos posibles en la descomposición de \[ n \] son \[ 2,3,5 \] y puedes hacer un análisis de los casos, que viene a ser lo del método 2.
Lo mejor es proceder como haces en el método 2) ir descartando casos. Pero te falta el caso en que \[ n \] es potencia de dos, que te da la solución que te falta.

Pregunta: ¿Cómo se demuestra que para todo \( n\in\Bbb{N} \), \( \sqrt{n}\leq\varphi(n)\leq n-1 \) usando herramientas básicas?
No es verdad que \[ \sqrt{n}\leq \varphi(n) \] para todo \[ n \]. Por ejemplo, \[ \varphi(2)=1<\sqrt{2} \]. Sí es cierto si \[ n \] es impar o si es múltiplo de \[ 4 \].

Para demostrarlo, usando la propiedad 3), basta ver que \[ \varphi(p^k)\geq \sqrt{p^k} \] (excepto en el caso \[ p=2,k=1 \]). En efecto, \[ \varphi(p^k)=p^{k-1}(p-1) \], mientras que \[ \sqrt{p^k}=p^{k/2} \]. Si \[ k>1 \], tenemos que \[ k-1{\color{red}\geq}k/2 \], luego en este caso se cumple la desigualdad que buscamos. Para el caso \[ k=1 \], observa que \[ \varphi(p)=p-1 \], pero si \[ p>2 \], \[ p-1>\sqrt{p} \], luego en este caso también se cumple.

En el caso que falta, que es cuando \[ n=2m \] con \[ m \] impar, \[ \varphi(n)=\varphi(m)\geq \sqrt{m} \], luego lo que puedes afirmar en el caso general, para todo \[ n \], es que \[ \varphi(n)\geq \sqrt{n/2} \].

Citar
1) ¿Por qué si tomo \( n=3o \) tal como hace en el video, está mal?
No está mal. Lo que pasa es que \[ 12 \] no es coprimo con \[ 3 \], se te ha colado.

Citar
2) ¿Por qué debo expresar a \( n \) de la forma \( 2^a3^b \) si \( 3\not\mid8 \) pero \( 2\mid8 \)?
Esto está respondido más arriba, mira la fórmula. Pero como digo después no basta con considerar esta forma, hay que considerar potencias de dos también.


Citar
3) ¿Por qué si lo expreso de dicha forma, me falta una solución?
Porque te falta plantear el caso \[ n=2^a \]. En este caso, tienes \[ \varphi(n)=2^{a-1} \]. Esto te da la solución \[ n=16 \] que te faltaba.

Corregido.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

03 Marzo, 2021, 07:42 pm
Respuesta #3

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,351
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola a ambos, sus aportaciones son muy valiosas

geómetracat: increíble todo lo que has deducido.

Ten en cuenta que si \[ n=p_1^{r_1}\dots p_k^{r_k} \] es la descomposición en factores primos de \[ n \], entonces \[ \varphi(n)=p_1^{r_1-1}\dots p_k^{r_k-1}(p_1-1)\dots (p_k-1) \].
Esto no es más que tu fórmula 4) reescrita.

Entiendo.

Citar
A partir de aquí se ve rápidamente que los únicos primos posibles en la descomposición de \[ n \] son \[ 2,3,5 \] y puedes hacer un análisis de los casos, que viene a ser lo del método 2.
Lo mejor es proceder como haces en el método 2) ir descartando casos. Pero te falta el caso en que \[ n \] es potencia de dos, que te da la solución que te falta.

Ayúdame a distinguir todos los casos posibles:

1) \( n \) es potencia de \( 2 \): \( n=2^a\to\varphi(n)=2^{a-1}=2^3 \) luego \( a-1=3\to a=4 \) luego \( n=2^4=16 \).

2) \( n \) NO es potencia de \( 2 \):

2.a) ???

2.b) ???

2.c) ???

Citar
No es verdad que \[ \sqrt{n}\leq \varphi(n) \] para todo \[ n \]. Por ejemplo, \[ \varphi(2)=1<\sqrt{2} \]. Sí es cierto si \[ n \] es impar o si es múltiplo de \[ 4 \].

Para demostrarlo, usando la propiedad 3), basta ver que \[ \varphi(p^k)\geq \sqrt{p^k} \] (excepto en el caso \[ p=2,k=1 \]). En efecto, \[ \varphi(p^k)=p^{k-1}(p-1) \], mientras que \[ \sqrt{p^k}=p^{k/2} \]. Si \[ k>1 \], tenemos que \[ k-1>k/2 \], luego en este caso se cumple la desigualdad que buscamos. Para el caso \[ k=1 \], observa que \[ \varphi(p)=p-1 \], pero si \[ p>2 \], \[ p-1>\sqrt{p} \], luego en este caso también se cumple.

En el caso que falta, que es cuando \[ n=2m \] con \[ m \] impar, \[ \varphi(n)=\varphi(m)\geq \sqrt{m} \], luego lo que puedes afirmar en el caso general, para todo \[ n \], es que \[ \varphi(n)\geq \sqrt{n/2} \].

Claro, en ese caso elevando al cuadrado, \( 64\geq n/2 \) luego hay que probar todos los \( n\leq128 \), ¿cierto?

Debo repasar un poco tu prueba pero gracias.

Citar
No está mal. Lo que pasa es que \[ 12 \] no es coprimo con \[ 3 \], se te ha colado.

Pero es que el \( 12 \) es el ejemplo del video, aquí es \( 8 \). Y en este caso sí se cumple \( \gcd(3,8)=1 \). ¿Y ahora? ???



En general creo que es un ejercicio bastante complicado para una asignatura como matemática discreta donde se priorizan los conceptos más que los cálculos. Y este ejercicio es de puro cálculo, acotaciones como has mostrado. Quisiera saber si te se ocurre una forma menos laboriosa para estos casos, por supuesto que las soluciones presentadas son válidas.

Saludos

03 Marzo, 2021, 08:06 pm
Respuesta #4

feriva

  • $$\Large \color{#a53f54}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 9,651
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino

En general creo que es un ejercicio bastante complicado para una asignatura como matemática discreta donde se priorizan los conceptos más que los cálculos. Y este ejercicio es de puro cálculo, acotaciones como has mostrado. Quisiera saber si te se ocurre una forma menos laboriosa para estos casos, por supuesto que las soluciones presentadas son válidas.

Saludos

Es fácil, manooooh, yo lo he sacado sin ver el vídeo ni enterarme de lo que decías bien (de ahí que dejara a otros las explicaciones, que después, si no, me regañan).

La función phi con números libres de cuadrados es simplemente el producto de estos elementos

\( p_{i}(1-\dfrac{1}{p_{i}})
  \) donde mutliplicando en cruz y cancelando queda \( p_{i}-1
  \).

Y de momento olvídate de los no libres de cuadrados (es más lío, yo lo entiendo pero porque primero lo he pensado sin ver nada, si no, no lo entendería).

Tienes, restando 1 a los primos, los factores posibles 1,2,4.

Entonces, con éstos, tienes los productos \( 1\cdot2\cdot4
  \) y \( 2\cdot4
  \); sustituyes por los primos correspondientes y son los números \( 2\cdot3\cdot5=30
  \) y \( 3\cdot5=15
  \).

Ahora, en esta operación, si no son libres de cuadrados, no desaparecen todos los \( p_{i}
  \), no se cancelan todos; fíjate qué fácil es entenderlo así.

Con 1, que corresponde al 2, si le pones tres doses delante que no se cancelan, tienes el número 16 (porque ese 1 se corresponde con (2-1) es un factor 2 en el número).

Con 2, que corresponde al 3, funciona multiplicarlo por dos doses 3·2·2... y así de sencillo con lo que sigue.



¡Es fácil :) !

Perdona, que ese último no era así; es así:

Tenemos (3-1)·2·2=8; pero tiene que estar el dos como factor en la phi; entonces es

(3-1)·2·2·(2-1)=8

Que se corresponde con 3·2·2·2=24


Saludos.

03 Marzo, 2021, 09:00 pm
Respuesta #5

geómetracat

  • Moderador Global
  • Mensajes: 2,344
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Ayúdame a distinguir todos los casos posibles:

Vamos a hacerlo sistemáticamente. Sabemos que \[ n \] es de la forma \[ 2^a3^b5^c \]. Pero de la fórmula, como \[ 8=2^3 \], tiene que ser \[ 0\leq b,c \leq 1 \] (si alguno fuera mayor que uno tendríamos que \[ 3 \] o \[ 5 \] divide a \[ \varphi(n) \]).

Ahora es cuestión de ir mirando casos. Empezamos con los que son múltiplos de \[ 5 \].
Si \[ n=5 \], tenemos \[ \varphi(5)=4\neq 8 \], luego \[ n=5 \] no es solución.
Si \[ n=3\cdot 5=15 \], entonces \[ \varphi(n)=8 \], luego es solución.
Si \[ n=2^a\cdot 5 \] (con \[ a>0 \]), se tiene \[ \varphi(n)=2^{a-1}\cdot 4 \], luego \[ a=2 \] y \[ n=20 \] es solución.
Si \[ n=2^a\cdot 3 \cdot 5 \], tenemos que \[ \varphi(n)=2^{a-1}\cdot 2 \cdot 4=8\cdot \], de donde \[ a=1 \] y \[ n=30 \] es solución. Con esto acabamos con los múltiplos de \[ 5 \].

Ahora múltiplos de \[ 3 \] que no son múltiplos de \[ 5 \].
Como \[ \varphi(3)=2 \], no es solución. Hay que mirar los de la forma \[ n=2^a\cdot 3 \], donde \[ \varphi(n)=2^{a-1}\cdot 2 \], de donde \[ a=3 \] y \[ n=24 \] es solución.

Finalmente, ya solo quedan las potencias de dos. Pero \[ \varphi(2^a)=2^{a-1} \], luego \[ a=4 \] y \[ n=16 \] es solución.

Juntándolo todo, las soluciones son exactamente: \[ 15,16,20,24,30 \].

Claro, en ese caso elevando al cuadrado, \( 64\geq n/2 \) luego hay que probar todos los \( n\leq128 \), ¿cierto?
Sí, pero es una solución muy poco eficiente.

Citar
Pero es que el \( 12 \) es el ejemplo del video, aquí es \( 8 \). Y en este caso sí se cumple \( \gcd(3,8)=1 \). ¿Y ahora? ???
No he visto el vídeo. Pero tú has escrito:

Pero ahora yo tomaría \( n=3o \) con \( \gcd(3,o)=1 \) tal como hace en el video pues \( 3\not\mid8 \), sin embargo al reemplazar me queda \( 8=2\varphi(o) \) de donde \( o=5,8,10,12 \), luego \( n=15,24,30,36 \) y algunas de estas NO son soluciones de la ecuación \( \varphi(n)=8 \). ¿Qué falla aquí?
Por un lado dices que \[ n=3o \] con \[ \gcd(3,o)=1 \], y por el otro lado sacas \[ o=5,8,10,12 \]. Si estás considerando únicamente \[ o \] coprimo con \[ 3 \], no puedes tomar \[ o=12 \]. Por eso no es solución.

Corregido.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

03 Marzo, 2021, 09:38 pm
Respuesta #6

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,351
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Muchas gracias por las respuestas. Paso a resaltar las dudas:

Para demostrarlo, usando la propiedad 3), basta ver que \[ \varphi(p^k)\geq \sqrt{p^k} \] (excepto en el caso \[ p=2,k=1 \]). En efecto, \[ \varphi(p^k)=p^{k-1}(p-1) \], mientras que \[ \sqrt{p^k}=p^{k/2} \]. Si \[ k>1 \], tenemos que \[ k-1>k/2 \], luego en este caso se cumple la desigualdad que buscamos. Para el caso \[ k=1 \], observa que \[ \varphi(p)=p-1 \], pero si \[ p>2 \], \[ p-1>\sqrt{p} \], luego en este caso también se cumple.

Queremos ver que \[ \varphi(p^k)\geq \sqrt{p^k} \] para todo \( p>2,\;k>1 \).

\( \varphi(p^k)=p^{k-1}(p-1) \). Ahora bien, si \( k>1 \), ¿cómo se llega a \( k-1>k/2 \)? Lo que intenté fue: \( k\geq2\to k-1\geq1 \).

Supuesto esto, tenemos \( p^{k-1}>p^{k/2}=\sqrt{p^k} \), pero falta el factor \( (p-1) \).

Gracias y saludos

03 Marzo, 2021, 09:48 pm
Respuesta #7

geómetracat

  • Moderador Global
  • Mensajes: 2,344
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
\( \varphi(p^k)=p^{k-1}(p-1) \). Ahora bien, si \( k>1 \), ¿cómo se llega a \( k-1>k/2 \)? Lo que intenté fue: \( k\geq2\to k-1\geq1 \).
Tiene que ser todo con \[ \geq \] en vez de \[ > \], es una errata.
\[ k-1 \geq k/2 \] es equivalente a \[ 2k-2\geq k \], que es equivalente a \[ k\geq 2 \].

Citar
Supuesto esto, tenemos \( p^{k-1}>p^{k/2}=\sqrt{p^k} \), pero falta el factor \( (p-1) \).
Como \[ p-1\geq 1 \], tenemos que \[ \varphi(p^k)=p^{k-1}(p-1)\geq p^{k-1}\geq p^{k/2} \].
La ecuación más bonita de las matemáticas: \( d^2=0 \)

03 Marzo, 2021, 11:41 pm
Respuesta #8

feriva

  • $$\Large \color{#a53f54}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 9,651
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino


2º Método. De forma analítica habiendo consultado el siguiente video: https://youtu.be/eAiVdJHnd8c


He visto el vídeo, manooooh, y me parece una complicación (aparte de que entienda poco en inglés).

1º Para \( \varphi(n)=10
  \).

Antes de nada una observación general.

Si, por ejemplo, \( n=p_{1}^{3}p_{2}^{2}=(p_{1}^{2}p_{2})p_{1}p_{2}
  \), y la phi es \( (p_{1}^{2}p_{2})(p_{1}-1)(p_{2}-1)
  \), su valor va a ser siempre mayor que \( (p_{1}-1)(p_{2}-1)
  \) (con cualquier ejemplo; como mucho puede ser igual). Por lo que basta analizar el tamaño de los primos posibles con \( (p_{1}-1)(p_{2}-1)
  \) (o con el “trozo” de phi del ejemplo que sea).

Es decir, el primo 13 ya no entra porque \( 13-1>10
  \)

A partir de eso tenemos los primos

\( 2,3,5,7,11
  \)

Quitándoles 1 tenemos los factores para las phis:

\( 1,2,4,6,10
  \)

Como 4 y 6 no dividen a 10, nos quedan sólo \( 1,2,10
  \).

Entonces, con los libres de cuadrados, las soluciones posible con esos factores son \( 10
  \) y \( 1*10
  \), o sea, lo que equivale a \( (11-1)
  \) y \( (2-1)(11-1)
  \); las phis de los números 11 y 22.

Y no hay más, en este caso es inmediato verlo; para que hubiera más tendríamos que tener el 5 aquí en los factores \( 1,2,10
  \); obvio.

...

Si \( \varphi(n)=12
  \); llegamos hasta 13: 13-1=12. El 17 ya no entra. Y hago lo mismo de antes:

\( 2,3,5,7,11,13
  \)

\( 1,2,4,6,10,12
  \)

Esta vez sólo quitamos el 10, los otros son divisores de 12:

\( 1,2,4,6,12
  \)

Pero ya sabemos que 12 es el más grande, el de la phi de 13, y no se puede multiplicar por ninguno más; por otra parte el 6 es grande también y sólo se puede multiplicar por 2; de aquí tenemos la phi de 21.

De ahí, al igual que pasaba antes, nos salen, al multiplicar por (2-1) también sus dobles; y tenemos las phis de éstos entonces: n=13,21,26,42.

Luego ya sólo tenemos que jugar con los que quedan \( 1,2,4
  \).

Pero como no hay ningún tres entre los factores... no hay más, esos cuatro son todos.

(Los he hecho como el otro, el del 8).

¿No es más fácil verlo así que con tanta potencia y tanto lío? Porque, de acuerdo en que son números fáciles, pero si son más difíciles, la combinatoria va a ser pesada siempre, haciéndolo de cualquier manera.

Saludos.

04 Marzo, 2021, 02:44 pm
Respuesta #9

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,351
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola a ambos

Muchas gracias por sus respuestas. feriva tendré que revisar en detalle lo que haces, porque lo que me parece más mecánico es lo que plantea geómetracat

Sabemos que \[ n \] es de la forma \[ 2^a3^b5^c \]. Pero de la fórmula, como \[ 8=2^3 \], tiene que ser \[ 0\leq b,c \leq 1 \] (si alguno fuera mayor que uno tendríamos que \[ 3 \] o \[ 5 \] divide a \[ \varphi(n) \]).

¿Por qué si \( 8=2^3 \) necesariamente ha de ser \( b,c\in\{0,1\} \)? ¿No puede darse igual si no supiéramos que \( \varphi(n)=8=2^3 \)?



Por otro lado, quiero intentarlo con otro ejemplo:

\( \varphi(n)=10 \). En este caso \( p-1\mid10,5,2,1 \) luego \( p=2,3,6,11 \) y \( 6 \) no es primo. Así que \( n=2^a3^b11^c \).

Como \( 10=2\cdot5 \) luego \( 0\leq b,c\leq1 \) (¿por qué hay que darse cuenta que \( 10=2\cdot5 \)?, es la misma pregunta anterior). Vamos por casos:

Múltiplos de 11:
- \( \varphi(11)=10 \) es solución. Creo que te faltó analizar este caso con \( n=5 \) en tu desarrollo por más que no cumpla, ¿es posible?:
Ahora es cuestión de ir mirando casos. Empezamos con los que son múltiplos de \[ 5 \].
Si \[ n=3\cdot 5=15 \], entonces \[ \varphi(n)=8 \], luego es solución.
Si \[ n=2^a\cdot 5 \] (con \[ a>0 \]), se tiene \[ \varphi(n)=2^{a-1}\cdot 4 \], luego \[ a=2 \] y \[ n=20 \] es solución.
Si \[ n=2^a\cdot 3 \cdot 5 \], tenemos que \[ \varphi(n)=2^{a-1}\cdot 2 \cdot 4=8\cdot \], de donde \[ a=1 \] y \[ n=30 \] es solución. Con esto acabamos con los múltiplos de \[ 5 \].

- \( n=3\cdot11=33 \) luego \( \varphi(n)=20 \) no es solución.
- \( n=2^a\cdot11,a>0 \) luego \( \varphi(n)=2^{a-1}10=10 \) luego \( a=1 \) y \( n=22 \) es solución.
- \( n=2^a\cdot3\cdot11,a>0 \) luego \( \varphi(n)=2^{a-1}2\cdot10=10 \) luego \( a=0 \) no hay solución.

¿Qué sucede con los casos \( n=2\cdot11,\;2\cdot3\cdot11 \), por qué no los analizamos?

Múltiplos de 3 y no de 11:
- \( \varphi(3)=2 \) no es solución.
- \( n=2^a3,a>0 \) luego \( \varphi(n)=2^{a-1}2=10 \) no hay solución.

Múltiplos de 2:
- \( n=2 \) no es solución. Este también creo
- \( n=2^a,a>0 \) luego \( \varphi(n)=2^{a-1} \) tampoco hay solución.

¿Por qué en algunos casos se les pone la condición \( a>0 \) y en otros no?

Por lo tanto las únicas soluciones son \( n=11,22 \). ¿Está todo bien?

Saludos