Aritmetica modula

ARITMÉTICA MODULAR
Relación de Equivalencia 1. Reflexiva: x x, x R 2. Simétrica: x y x, y R Í y, x R 3. Transitiva: x y z x, y R y, z R Í x, z

R

TEOREMA FUNDAMENTAL DEL ÁLGEBRA Toda relaciónde equivalencia induce una partición en su conjunto. PARTICIÓN DE A P  A1, A2, . . . An 1. A i A j   2. A  A 1 Þ A 2 Þ A 3 Þ. . . A n EJEMPLO 1 R n  x, y

Z:x

y es un múltiplo de n

1.Reflexiva: x x, x R x x  0 que es múltiplo de n Ê x, x 2. Simétrica: x y x, y R Í y, x x, y R Ê x y es un múltiplo de n Ê y x es un múltiplo de n Ê y, x R

R R

3. Transitiva: x y z x, y R y, z R Íx, z R x, y R y, z R Ê x y es múltiplo de n y z es múltiplo de n Í x y  y z es múltiplo de n Í x z es múltiplo de n Í x, z R PARTICIÓN A x  y : x, y R A 0  y : 0 y es un múltiplo de n A 0  . . . ,2n, n, 0, n, 2n, 3n, . . . A1  y:1 y es un múltiplo de n

A 1  . . . , 2n  1, n  1, 1, n  1, 2n  1, 3n  1, . . . ... An
1



EJEMPLO 2 Z:x Z 5  x, y

y es un múltiplo de 5 1

A0A1 A2 A3 A4 A5

     

..., ..., ..., ..., ..., ...,

10, 5, 0, 5, 10, . . . 9, 4, 1, 6, 11, . . . 8, 3, 2, 7, 12, . . . 7, 2, 3, 8, 13, . . . 6, 1, 4, 9, 14, . . . 5, 0, 5, 10, 15, . . . A 0

P  A0, A1, A2, A3, A4  A1, A2, A3, A4, A5  A 4 , A 12 , A 3 , A 9 , A 5 TEOREMA: A i  A j Ê i, j R

ARITMÉTICA EN UNA PARTICIÓN P  A0, A1, A2, A3, A4 A i  A j  A ij A1  A2  A3 A6 A2  A8  A3 A 6  A 12  A 18  A 3

A4  A3  A2 A7 A2 A2 A6  A1 A6  A 4  A1 A 26  A 24  A 1

A 5 A 3  A 15  A 0 A0 A3  A0 A 15 A 8  A 120  A 0

Notación por representante: x

AiÊ x  Ai

SUMA: x  y  x  y RESTA: x y  x y MULTIPLICACIÓN: x y  x

y

EJEMPLO 3 (Z 5 ) x  4  3 x  3 4

2

 7  3 x  4 mod 5 x mod 5 3 x mod 5 7 x mod 5 3 3 4

x  [número que aldividir por 5 tenga como residuo 4]  [número que al dividir por 5 tenga como residuo -3] EJEMPLO 4 2 x  4  1 2 x  1 4 2 x  3 2 x  2 2 x  4  2 2 x  2 4 2 x  3 x  4 x 
2 2

Z5

 1...