Autor Tema: calcular gcd de forma recursiva.

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

13 Junio, 2010, 12:38 am
Leído 1212 veces

marshi

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 10
  • Karma: +0/-0
  • Sexo: Femenino
Hola. Debo realizar el siguiente ejercicio y no sé como se hace  :-[

"Muestre que cuando hay más de dos números la siguiente definición recursiva es correcta:
\(  gcd (a,b,c, \dots , m, n) = gcd(gcd(a,b,c, \dots , m), n) \)
Acá \( gcd(a,b, \dots) \) corresponde al máximo común divisor de todos sus argumentos."

Ojalá alguien pueda ayudarme...

13 Junio, 2010, 03:46 am
Respuesta #1

pepito

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,625
  • Karma: +0/-0
  • Sexo: Masculino
Sean \(  gcd (a,b,c, \dots , m, n) = d_1  \) y \(  gcd(gcd(a,b,c, \dots , m), n) = d_2 \)

Tenemos que \( d_1\mid a, \quad d_1\mid b, \quad d_1\mid c, \quad\ldots , \quad d_1\mid m, \quad d_1\mid n \)

Como \( d_1\mid a, \quad d_1\mid b, \quad d_1\mid c, \quad\ldots , \quad d_1\mid m \), entonces \( d_1\mid gcd(a,b,c, \ldots , m) \)

Como además \( d_1\mid n \), entonces \( d_1\mid d_2 \)

Por otro lado, tenemos que \( d_2\mid gcd(a,b,c, \ldots , m) \), con lo cual, \( d_2\mid a, \quad d_1\mid b, \quad d_1\mid c, \quad\ldots , \quad d_1\mid m \)

Como a parte, \( d_2\mid n \), entonces \( d_2\mid d_1 \)

Como \( d_1, d_2\in\mathbb{N} \), resulta que \( d_1=d_2 \).
"...parecido pero nada que ver"