Autor Tema: Máximo común divisor y Fibonacci

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

04 Abril, 2009, 02:04 am
Respuesta #10

topo23

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 937
  • Karma: +0/-0
Creo que Hector comete un error, al suponer que \( 17\nmid -510=2 \times 3 \times 5 \times 17 \).

Por el algoritmo de Euclides
\( \begin{eqnarray*}
28n+5 & = & 0(35n+2) + 28n+5 \\
35n+2 & = & 1(28n+5) + 7n-3 \\
28n+5 & = & 4(7n-3)+17
\end{eqnarray*}
 \)

Como 17 es primo entonces si \( 17 | 7n-3 \) entonces \( \textrm{mcd}(28n+5, 35n+2) = 17 \), caso contrario \( \textrm{mcd}=1 \).

Por ejemplo para n=15, el mcd es 17.
.

06 Abril, 2009, 11:05 am
Respuesta #11

Luis Fuentes

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

 En concreto para hallar cuando el m.c.d es \( 17 \) resuelve la ecuación diofántica:

\(  7n-3=17k \)

 o equivalentemente

\(  7n-17k=3 \)

 ¿Sabes hacerlo?.

Saludos.

06 Abril, 2009, 02:58 pm
Respuesta #12

Teón

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,369
  • Karma: +0/-0
  • Sexo: Masculino
  • C:.J:.T:.
Si resuelves la ecuación que da el_manco, encontrarás:
Spoiler
si n=17k-2, MCD(28n+5,35n+2)=17, en caso contrario MCD(28n+5,35n+2)=1,
donde \(  k\in{\mathbb{Z}} \)
[cerrar]
Eram quod es, eris quod sum.

06 Abril, 2009, 09:09 pm
Respuesta #13

z451

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


No llego. La ecuación diofántica de arriba tiene solución si el máximo coún divisor de 7 y 17 es múltiplo de 3. He visto un par de enlaces pero nada.
¿Podéis ayudarme siendo más explícitos?

Un saludo.

P.D.: Por cierto, esta tarde estuve visitando Göttingen, y a su vez las tumbas de Gauss y Hilbert. Muy impresionante.

06 Abril, 2009, 10:02 pm
Respuesta #14

topo23

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 937
  • Karma: +0/-0
Para n=-2,

28*(-2)+5=-51=-3*17
35*(-2)+2=-68=-4*17.

No veo nada raro, a que te referis cuando afirmas que para k=0 y n=-2 pasa algo raro?


Hay varios metodos para resolver este tipo de ecuaciones diofanticas, todo depende de cuanto sabes, en general lo que primero se hace es encontrar una solucion particular, y luego a partir de esa solucion se pueden generar otras, asi podemos buscar las que cumplan un criterio determinado (por ejemplo que n, k sean positivos).

Por ejemplo si n=A es una solucion de 7n - 17k = 3, entonces A + 17, A + 2*17, ... tambien es solucion.

* La mas simple es el metodo de prueba y error.

Por ejemplo para 7n - 17k = 3, podemos hacer \( \cancel{n = \frac{3 - 17k}{7}} \) \( n=\frac{3+17k}{7} \), y tenemos que encontrar un k tal que n sea entero.

k=0, no sirve.
k=-1, da n=-2

Luego van a ser soluciones son n = -2 + 17j

* Usando el algoritmo de Euclides como mcd(7,17)=1, existen r, s enteros tales que 7r + 17s = 1, multiplicando por 3 tenemos 7(3r) + 17(3s) = 3, que es una solucion particular.

* Con congruencias entonces la ecuaciones es \( 7n = 3 \mod(17) \). Si pasamos el 7 dividiendo entonces ya esta, para eso usamos el PTF, como mcd(7,17)=1, entonces vale que \( 7^{17-1}=7^{16}=7 \times 7^{15}=1\mod(17) \).

.

07 Abril, 2009, 12:08 am
Respuesta #15

z451

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 47
  • Karma: +0/-0
  • Sexo: Masculino
¿Por qué \( n = \frac{3 - 17k}{7} \) y no \( n = \frac{3 + 17k}{7} \)?

20 Abril, 2009, 01:29 am
Respuesta #16

z451

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

20 Abril, 2009, 02:51 am
Respuesta #17

topo23

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 937
  • Karma: +0/-0
¿Por qué \( n = \frac{3 - 17k}{7} \) y no \( n = \frac{3 + 17k}{7} \)?

Si el despeje esta mal deberia ser \( n = \frac{3 + 17k}{7} \) (aunque como no nos importa el signo de k, sino solo n, ambas llevan al mismo conjunto de soluciones de n, con los k de signo cambiado).

.

20 Abril, 2009, 02:58 pm
Respuesta #18

z451

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 47
  • Karma: +0/-0
  • Sexo: Masculino
Muchas gracias por la aclaración.