Maximo Común Divisor

Se define el máximo común divisor (MCD) de dos o más números enteros al mayor número entero que los divide sin dejar resto.

Un número entero d se llama máximo común divisor (MCD) de los números a y b cuando:

1. d es divisor común de los números a y b y
2. d es divisible por cualquier otro divisor común de los números a y b.

Los tres métodos más utilizados para el cálculo del máximo común divisor de dos números son:

Por descomposición en factores primos

El máximo común divisor de dos números puede calcularse determinando la descomposición en factores primos de los dos números y tomando los factores comunes elevados a la menor potencia, el producto de los cuales será el MCD.

En la práctica, este método solo es operativo para números pequeños tomando en general demasiado tiempo calcular la descomposición en factores primos de dos números cualquiera.

Usando el algoritmo de Euclides

Un método más eficiente es el algoritmo de Euclides, que utiliza el algoritmo de la división junto al hecho que el MCD de dos números también divide al resto obtenido de dividir el mayor entre el más pequeño.

El algoritmo de Euclides es un método antiguo y eficaz para calcular el máximo común divisor (MCD). Fue originalmente descrito por Euclides en su obra Elementos. El algoritmo de Euclides extendido es una ligera modificación que permite además expresar al máximo común divisor como una combinación lineal. Este algoritmo tiene aplicaciones en diversas áreas como álgebra, teoría de números y ciencias de la computación, entre otras. Con unas ligeras modificaciones suele ser utilizado debido a su gran eficiencia.

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using System.Windows.Forms;

namespace MCD_I_Forms

{

    public partial class Form1 : Form

    {

        public Form1()

        {

            InitializeComponent();

        }

        int numero1, numero2, a, b, resultado;

        private void button2_Click(object sender, EventArgs e)

        {

            Application.Exit();

        }

        private void button1_Click(object sender, EventArgs e)

        {

            //Algoritmo de Euclides

            //Seleccionamos el mayor y el menor para asignarlos

            //a las variables a y b respectivamente

            numero1 = int.Parse(textBox1.Text);

            numero2 = int.Parse(textBox2.Text);

            a = Math.Max(numero1, numero2);

            b = Math.Min(numero1, numero2);

            do //ciclo para las iteraciones

            {

                resultado = b;  // Guardamos el divisor en el resultado

                b = a % b;      //Guardamos el resto en el divisor

                a = resultado;  //El divisor para al dividendo

            }

            while

            (b != 0);

            textBox3.Text = resultado.ToString();

        }

    }

}

Usando el mínimo común múltiplo


El máximo común divisor también puede ser calculado usando el mínimo común múltiplo. Si a y b son distintos de cero, entonces el máximo común divisor de a y b se obtiene mediante la siguiente fórmula, que involucra el mínimo común múltiplo de a y b:




MCD de tres o más números


El máximo común divisor de tres o más números se puede definir usando recursivamente

https://es.wikipedia.org/wiki/M%C3%A1ximo_com%C3%BAn_divisor

https://es.wikipedia.org/wiki/Algoritmo_de_Euclides

http://www.vitutor.com/di/di/a_7.html