Autor Tema: Problema Euler

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

10 Marzo, 2008, 01:28 pm
Leído 3341 veces

SoN

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 15
  • Karma: +0/-0
  • Sexo: Masculino
Hola a tod@s.

Tengo un problema con un ejercicio y espero que me puedan ayudar.
Dice así:

Definimos la función  \( \varphi \) de Euler en el conjunto de los números naturales posivitos como:

\( \varphi(n)= \left\{#{i\in{}Z:1 \leq i \leq n, mcd(i,n)=1}\right\} \)

1a) Demostrar que la función \( \varphi \) de Euler cumple:

\( \sum_{d|n}{\varphi(d)=n} \)

Indicación del problema--> Podéis empezar demostrando que:

\( \left\{{\frac{1}{n},\frac{2}{n},...,\frac{n-1}{n},\frac{n}{n}}\right\}=\left\{{\bigcup\limit_{d|n}{\frac{a}{d} \in{} Q: 0 < \frac{a}{d} \leq 1, mcd(a,d)=1}}\right\} \)


2a) Utilizar la descripción anterior para dar una expresión recursiva de \( \varphi(n) \)


Se ha dicho que es necesario seguir las indicaciones y no sé por dónde pillarlo. :banghead:
Gracias.

10 Marzo, 2008, 02:38 pm
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 1) Fíjate que a cada número de la forma:

 \( \displaystyle\frac{k}{n} \)

 le corresponde de manera única un par de enteros positivos \( (a,d) \) con \( d \) divisor de \( n \) y \( a\leq d \) y \( d \) primos entre si. Basta tomar una fracción equivalente reducida:

 \( \displaystyle\frac{k}{n}=\displaystyle\frac{a}{d} \) con \( d|n \) y \( m.c.d(a,d)=1 \)

 Recíprocamente dado una par de enteros positivos \( (a,d) \) con \( a\leq d \), \( d \) divisor de \( n \) y primos entre si, define una fracción con denominador \( n \):

\( \displaystyle\frac{a}{d}=\displaystyle\frac{a(n/d)}{n} \)

 La conclusión de es que estos dos conjuntos tienen el mismo número de elementos:

\( C_1= \{\displaystyle\frac{1}{n},\ldots,\displaystyle\frac{k}{n}\} \)

y

\( C_2=\{(a,d)|d\mbox{ divisor de }n,\quad a\leq d,\quad m.c.d(a,d)=1\} \)

 Fíjate que el cardinal de \( C_1 \) es \( n \) y el cardinal de \( C_2 \) es la suma de todos los \( \varphi(d) \) con \( d \) divisor de \( n \).

 2) La suma anterior puede escribirse como:

\(  \displaystyle\sum_{d|n,d<n}\varphi(d)+\varphi(n)=n \)

 Termina...

Saludos.

10 Marzo, 2008, 04:02 pm
Respuesta #2

SoN

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 15
  • Karma: +0/-0
  • Sexo: Masculino
Por tu aclaración, veo que en el 1 me estaba complicando bastante yo solo.
Muchas gracias, el_manco.
Respecto al 2, soy incapaz de ver más allá de este ordenador (en lo que al problema se refiere). Soy bastante negado en esto... Agradecería alguna indicación.

También, me gustaría hacer otra pregunta respecto a este mismo problema con el que estoy liado.

Dice asi:

Demostrar que si a y b son enteros positivos coprimeros, entonces \( \varphi(ab)=\varphi(a)\varphi(b) \)
Indicación al problema -->
Si dado un número natural m escribimos s(m) el número de factores primos de m contando multiplicidades, se puede aplicar inducción sobre el conjunto de parejas (s(a),s(b)) con la relación de orden habitual \( (x,y)\leq{(x',y')} \) si y solo sí \( x\leq{x'}, y\leq{y'} \).


Entiendo que \( \forall{n}, 1\leq{n}\leq{ab} \), n será primo con ab si no es múltiplo ni de a ni de b.
Para n, \( 1\leq{n}\leq{ab-1} \) hay a-1 múltiplos de b y b-1 multiplos de a, donde no hay comunes ya que el minimo comun multiplo de (a,b)=ab
Entonces...
\( \varphi(ab)=(a-1)(b-1)=\varphi(a)\varphi(b) \)

Suponiendo que esto que digo sea correcto... que tengo mi dudas... no se continuar. Y el teorema de inducción me viene bastante grande...

Gracias de nuevo.

10 Marzo, 2008, 06:46 pm
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 Lo del dos ya lo puse:

\(  \displaystyle\sum_{d|n,d<n}\varphi(d)+\varphi(n)=n \)

 de donde:

\(  \varphi(n)=n-\displaystyle\sum_{d|n,d<n}\varphi(d) \)

 y esto es una relación recursiva que te permite poner \( \varphi(n) \) en función de los valores \( \varphi(d) \) con \( d \) menor que \( n \).

Saludos.

10 Marzo, 2008, 11:08 pm
Respuesta #4

SoN

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 15
  • Karma: +0/-0
  • Sexo: Masculino
Ok Ok.
Gracias por la ayuda!

Saludos.

11 Marzo, 2008, 11:09 am
Respuesta #5

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 En cuanto a probar que \( \varphi(ab)=\varphi(a)\varphi(b) \) si \( m.c.d(a,b)=1 \), tu has probado de manera correcta que es cierto para \( a \) y \( b \) primos.

 Los pasos para la prueba general pueden ser estos:

 1) Prueba que: \( \varphi(pb)=(p-1)\varhpi(b)=\varphi(p)\varphi(b) \) si \( p \) es primo y \( m.c.d(b,p)=1 \).

 Para ello ten en cuenta que los número no coprimos con \( pb \) y no mayores que éste se construyen como:

 - números no coprimos con \( b \) más múltiplos \( kb \) con \( 0\leq k\leq p-1 \) (si los "cuentas" son \( (b-\varphi(b)p \)).
 - números de la forma \( p\cdot k \) con \( k \) coprimo con \( b \) (para no repetir los anteriores) y menor que \( b \) (si los "cuentas" son \( \varhpi(v) \))

 2) Prueba que \( \varhpi(pb)=p\varphi(b) \)  si \( p \) es primo y \( m.c.d (p,b)=p \).

 Para ello ten en cuenta que los número no coprimos con \( pb \) y no mayores que éste se construyen ahora simplemente como:

 - números no coprimos con \( b \) más múltiplos \( kb \) con \( 0\leq k\leq p-1 \) (si los "cuentas" son \( (b-\varphi(b)p \)).

 3) Deduce que: \( \varphi(p^n)=p^{n-1}(p-1) \) para \( p \) primo.

 4) Prueba en general tu resultado por inducción sobre el número de divisores primos de \( a \).
 
 - Si \( a \) tiene un divisor primo, \( a=p^n \). Combinando 1, 2 y 3:

\(  \varphi(p^nb)=p^{n-1}\varphi(pb)=p^{n-1}p\varphi(b)=\varphi(a)\varphi(b) \)

 - Supón que el resultado es cierto cuando \( a \) tiene menos de \( n \) divisores primos. Si \( a  \) tiene \( n \) divisores primos y \( a=p^ka'  \), con \( m.c.d(a',k)=1 \), por 1 y 2:

\(  \varphi(ab)=\varphi(p^ka'b)=\varphi(p^k)\varphi(a'b) \)

 Por hipótesis de inducción:

\(  \varphi(a'b)=\varphi(a')\varphi(b) \)

 y

\(  \varphi(p^k)\varphi(a')=\varphi(p^ka')=\varphi(a). \)

Saludos.

12 Marzo, 2008, 09:02 am
Respuesta #6

SoN

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 15
  • Karma: +0/-0
  • Sexo: Masculino
Gracias nuevamente.

Si tuviera que dar una fórmula explícita para calcular el valor de la función \( \varphi \), cual seria?

Saludos.

12 Marzo, 2008, 09:09 am
Respuesta #7

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 Combinando los resultados probados en este conjunto de mensajes sería algo así. Dado un número n con descomposición en factores primos:

\( n=p_1^{k_1}\cdot \ldots\cdot p_m^{k_m} \),

se tiene:

\(  \varphi(n)=\displaystyle\prod_{i=1}^mp_i^{k_i-1}(p_i-1) \)

donde estás utilizando que:

\( \varphi(n)=\varphi(p_1^{k_1})\cdot \ldots \cdot \varphi(p_m^{k_m})  \)

y

\( \varphi(p^k)=p^{k-1}(p-1) \)

Saludos.

27 Octubre, 2008, 01:54 am
Respuesta #8

coleauch

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 15
  • Karma: +0/-0
  • Sexo: Masculino
Alguien sabe como desmostrar que si \( (a,b)\neq{}1 \)  \( \Longrightarrow{} \)  \( \varphi(ab)>\varphi(a)\varphi(b) \)

27 Octubre, 2008, 08:38 am
Respuesta #9

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 En este hilo está probado que:

\(  m.c.d(a,b)=1\quad \Rightarrow{}\quad \varphi(ab)=\varphi(a)\varphi(b) \)

 Pero entoncese supongamos que:

\(  a=p_1^{k_1}\ldots p_n^{k_n} \)
\(  b=p_1^{l_1}\ldots p_n^{l_n} \)

 con \( p_i \) primos, \( k_i,l_i \) enteros no negativos.

 Por la propiedad anterior:

\(  \varphi(a)=\varphi(p_1^{k_1})\ldots \varphi(p_n^{k_n}) \)
\(  \varphi(b)=\varphi(p_1^{l_1})\ldots \varphi(p_n^{l_n}) \)
\(  \varphi(ab)=\varphi(p_1^{l_1+k_1})\ldots \varphi(p_n^{l_n+k_n}) \)

 Ahora basta tener en cuenta que si \( l,k\geq 1 \):

\(  \varphi(p^{l+k})=p^{l+k-1}(p-1)=p^{l+k-2}p(p-1) \)

 y

\(  \varphi(p^{l})\varphi(p^k)=p^{k-1}(p-1)p^{l-1}(p-1)=p^{l+k-2}(p-1)(p-1) \)

Saludos.