Aritmética modular

La aritmética modular se utiliza para simplificar los problemas teóricos-numéricos sustituyendo cada entero por el resto de dividirlo entre un entero positivo fijo n. Esto produce el efecto de sustituir el conjunto infinito Z por un conjunto Zn que sólo contiene n elementos. Encontraremos que se pueden sumar, restar y multiplicar los elementos de Zn(igual que en Z), aunque encontraremos dificultades en la división. Zn hereda muchas de las propiedades de Z pero mucho más fácil de trabajar con ellos. (ax = b).

Ejemplo 

17≡ 5 (mod 6), 241 ≡ 6 (mod 9), 22051946 ≡ 2(mod 4)

Teorema 

Sea n un entero positivo, los enteros a y b son congruentes modulo n si solo si existe un entero k tal que
a = b + km.

Teorema 

Sea n un entero positivo, si a ≡ b (mod n) y c ≡d (mod n) entonces a + c ≡ b + d (mod n) y a≡c ≡ b≡d
(mod n).

Para cualquier entero n ≥1 se verifican las siguientes propiedades:

• Reflexiva a ≡ a (mod n) para cualquier entero a;
• Simétrica a ≡ b (mod n) )→ b ≡ a (mod n).
• Transitiva a ≡ b (mod n) y b ≡ c (mod n) )→ a ≡c (modn).

Estas propiedades definen una relación de equivalencia o de congruencia módulo n en los Z. Queda así particionado Z en clases de equivalencia o congruencias disjuntas.
[a] = fb 2 Z : a ≡ b (mod n) g = f. . ., a - 2n, a - n, a, a + n, a + 2n, . . .g para a 2 Z.

Podemos decir que Zn forma un sistema numérico con
propiedades similares a los Z (suma, resta, multiplicación).
[a] + [b] = [a + b],(modn)
[a] - [b] = [a - b],(modn)
[a] * [b] = [a * b](modn)

 

Algoritmo de Euclides

import javax.swing.JOptionPane;
public class Mcd2{
    public static void main(String []args){
        int num1,num2,min,max,resto,mcd=0;
        num1=Integer.parseInt(JOptionPane.showInputDialog("ingrese numero 1"));
        num2=Integer.parseInt(JOptionPane.showInputDialog("ingrese numero 2"));
       
        min=Math.min(num1, num2);
        max=Math.max(num1, num2);
       
        while(min!=0)
        {
            resto=max%min;
            max=min;
            min=resto;
        }
        mcd=max;
        JOptionPane.showMessageDialog(null,"El MCD es: "+mcd+" de "+num1+" y "+num2);
    }
}