Aritmetica Modular

PROBLEMAS RESUELTOS DE ARITMÉTICA ENTERA Y MODULAR
ARITMÉTICA ENTERA 1) Usar el Algoritmo de Euclides para calcular d = mcd (a, b), y encontrar x e y tales que d = ax + by. a) a = 1312, b = 800 Solución: Encontrando d = a x + b y → d = 1312 x + 800 y Por el algoritmo de Euclides tenemos: 1312 = 800 + 512 800 = 512 + 288 512 = 288 + 224 288 = 224 + 64 224 = 64(3) + 32 64 = 32(2) + 0 = mcd (1312, 800) 32 → d = ⇒ 32 = 224 − 64 (3) 32 = [512 − 288] − 3 [288 − 224]

32 = 512 − 4 [288] + 3 [224] 32 = [1312 − 800] − 4 [800 − 512] + 3 [512 − 288] 32 = 1312 − 5[800] + 7 [512] − 3 [288] 32 = 1312 − 5 [1312 − 512] + 7 [512] − 3[800 − 512] 32 = −4[1312] + 15[512] − 3[1312 − 512] 32 = −7 [1312] + 18 [512] 32 = −7 [1312] + 18[1312 − 800] 32 = 11[1312] − 18 [800]

= 1312 (11) + 800 (−18) 32   
a x0 b y0

• x = 11, •

y = -18

Reemplazando x e y en d = ax + by d = ax + by 32 = 1312 (11) + 800 (-18) 32 = 14432 + (-14400) 32 = 32

b) a = 322, b = 406 Solución: Encontrando d = ax + by → d = 332x + 406y Por el algoritmo de Euclides tenemos: 406 = 322 + 84 322 = 84(3) + 70 84 = 70 + 14

Lic. GUILLERMO MAS AZAHUANCHE

88

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO70 = 14(5) + 0 = mcd (322 , 406) 14 → d = → 14 = 84 − 70  

14 = 406-322-[322-(3)84] 14 = 406-2(322)+(3)[406-322] 14 = 406(4)+322(-5)

14 322 (−5) + 406 (4) =    
a x0 b y0

• •

x = -5

y=4

Reemplazando x e y en d = ax + by d = ax + by 14 = 322 (-5) + 406 (4) 14 = -1610 - 1624 14 = 14

c) a = 721, b = 448. Solución: Encontrando d = ax + by → d = 721x + 448y Por elalgoritmo de Euclides tenemos: a = 721, b = 448 Solución d = mcd (721,448) = 7 • Aplicando el Algoritmo de Euclides 721 = 448 (1) + 273 448 = 273 (1) + 175 273 = 175 (1) + 98 175 = 98 (1) + 77 98 = 77 (1) + 21 77 = 21 (3) +14 21 = 14 (1) + 7 14 = •
7 (2) + 0 d

Proceso inverso del Algoritmo 7 = 21 + (-1) 14 7 = 21 + (-1) [77 + (-3) 21]

Lic. GUILLERMO MAS AZAHUANCHE

89

UNIVERSIDAD NACIONALDEL CALLAO ESCUELA DE POST GRADO 7 = (-1) 77 + (4) 21 7 = (-1) 77 + (4) [98 + (-1) 77] 7 = (4) 98 + (-5) 77 7 = (4) 95 + (-5) [ 175 + (-1) 98] 7 = (-5) 175 + (9) 98 7 = (-5) 175 + (9) [273 + (-1) 175] 7 = (9) 273 + (-14) 175 7 = (9) 273 + (-14) [448 + (-1) 273] 7 = (-14) 448 + (23) 273 7 = (-14) 448 + (23) [721 + (-1) 448] 7 = (23) 721 + (-37) 448 x = 23, • y = -37 d = ax +by

Reemplazando x e y7 = 721 (23) + 448 (-37) ⇒ 7 = 16583 + 16576 ⇒ 7 = 7 2. Se dispone de un suministro ilimitado de agua, un gran cubo con un desagüe y dos garrafas que contienen 7 y 9 litros respectivamente. ¿Cómo podría ponerse un litro de agua en el cubo? Solución 7x + 9y = 1 n x: Número de garrafas de 7 litros vertidas o retiradas del cubo y: Número de garrafas de 9 litros vertidas o retiradas del cubo d =mcd (7, 9) =1 • Aplicando Algoritmo de Euclides 9 = 7(1) + 2 7 = 2 (3) + 1 2= • 1 (2) + 0 d
n 1 = =1 d 1

(+) vertida (-) retirada

Proceso inverso del Algoritmo 1 = 7 + (-3) 2 1 = 7 + (-3) [9 + (-1) 7] 1 = (-3) 9 + (4) 7 x=4 y = -3

Lic. GUILLERMO MAS AZAHUANCHE

90

UNIVERSIDAD NACIONAL DEL CALLAO ESCUELA DE POST GRADO 7 (4) + 9 (-3) = 1 luego: 28 27 = 1 entonces 1 = 1

Luego sevierten 4 garrafas de 7 litros y se retiran 3 garrafas de 9 litros. 3. Calcular las soluciones enteras de las siguientes ecuaciones dionfáticas: a) 28x + 36y = 44 Solución d = mcd (28,36) = 4 36 = 28 (1) + 8 28 = 8 (3) + 4 8=
4 (2) + 0 d n 44 = = 11 4 d

4 = 28 + 8 (-3) 4 = 28 + (-3) [36 + (-1) 28] 4 = (-3) 36 + (4) 28 28 (4) + 36 (-3) = 4 • Multiplicando x 11 x e y, d 28 (44) + 36 (-33) = 44 xo= 44, yo = -33

b x = xo + t a
x = 44 + 36 t 4

a y = yo − t b
y = −33 − 28 t 4

x = 44 + 9t 44 + 9t > 0 t > -4.88

y = -33 - 7t -33 - 7t < 0 t >- 4.71 t

-4 -4,88

-3

-2

-1

0

1

2

3

……..

∞
Satisface para ∀ t ∈ ℤ Para: t = 1 x = 44 + 9t x = 44 + 9 y = -33 - 7t y = -33 -7
⇒

28x + 36y = 44 28(53) + 36 (-40) = 44

Lic. GUILLERMO MAS AZAHUANCHE

91...