Mdi teoria de numeros jhon mauro gomez

Taller 3: Teor´ de N´meros, MD I. ıa u
Profesora: Martha Elena del Socorro Mill´n Gonz´lez Ph.D. a a Matem´ticas Discretas I (750083M) Grupo 01 a Carolina Crespo C. (0940170) - 3743 Luis Manuel Ni˜ o T. (0938420) - 3743 n Jhon Mauro G´mez B. (0939548) - 3743 o 20 de Mayo de 2010

1.

Residuos
Planteamiento a, b, c ∈ R+ a|b → b=a·k c = aj + r c = bh + s Desarrollo 1. s = c − bh 2. s = (aj +r) − (ak)h 3. s = a (j − kh) +r
t

4. s = at + r

Respuesta Como s tiene la forma s = at + r, entonces el resto de la divisi´n entre s y a es r. o

2.

Residuos
Planteamiento x ∈ Z+ ∧ x < 100 x = 3k1 + r1 x = 5k2 + r2 x = 7k3 + r3 Desarrollo x − r1 = 3k1 x − r2 = 5k2 x − r3 = 7k3 x ≡ r2 (mod 5) x ≡ r3 (mod 7) 3. x − a = bk x ≡ r1 (mod 3) Propiedad 1. x ≡ a(mod b) 2. b | x − a

IDesarrollo x − r1 = 3k1 x − r2 = 5k2 x − r3 = 7k3

x ≡ r1 (mod 3) x ≡ r2 (mod 5) x ≡ r3 (mod 7)

Respuesta Si es posible, pues se pueden plantear las congruencias y resolverlas por el Teorema del Residuo Chino, ya que 3, 5, 7 son primos Relativos.

3.

Diferencia de Cubos Consecutivos
Prueba x3 − (x + 1)3 nunca es divisible por 3 Demostraci´n o x3 − x3 + 3x2 + 3x + 1 3x2 + 3x + 1 3 (x2 + x)+1
h

3h + r, r = 0 Respuesta Por tanto, se ha demostrado que x3 − (x + 1)3 nunca es divisible por 3, pues la expresi´n equio valente 3(x2 + x) + 1 tiene la forma 3h + r, donde h = x2 + x y r = 1, y al tener el residuo, no puede ser divisible por 3.

4.

Congruencia

Planteamiento El menor x ∈ Z+ que cumpla la congruencia 11x ≡ 6(mod 17). Desarrollo Algoritmo de Euclides • mcd(17, 11) •17 = 1 · 11 + 6 • mcd(11, 6) • 11 = 1 · 6 + 5 • mcd(6, 5) • 6=1·5+1 • mcd(5, 1) • 5=5·1+0 Desarrollo Combinacion Lineal • 1 =6−1·5 • 1 = 6 − 1 · (11 − 1 · 6) • 1 = 6 − 1 · 11 + 1 · 6 • 1 = 2 · 6 − 1 · 11 • 1 = 2 · (17 − 1 · 11) − 1 · 11 • 1 = 2 · 17 − 2 · 11 − 1 · 11 • 1 = 2 · 17 − 3 · 11

II

Busqueda del x positivo • 11(−3) ≡ 1(mod 17) • 11(−18) ≡ 6(mod 17) • x = −3 · 6 + 17k • x = −18 +17k • x = −18 + 17(2) → Pues con 2 se obtiene el menor entero positivo • x = −18 + 34 • x = 16 Respuesta Por tanto, el menor x ∈ Z+ que cumpla la congruencia 11x ≡ 6(mod 17), es x = 16.

5.

Combinaci´n Lineal o

Planteamiento Exprese en mcd(95, 25) como combinaci´n lineal de 25 y 95. o Desarrollo Algoritmo de Euclides • • • • • • mcd(95, 25) 95 = 3 · 25 + 20 mcd(25, 20) 25 = 1 · 20 + 5mcd(20, 5) 20 = 4 · 5 + 0 Combinaci´n Lineal o • 5 = 25 − 1 · 20 • 5 = 25 − 1 · (95 − 3 · 25) • 5 = 25 − 1 · 95 + 3 · 25 • 5 = 4 · 25 − 1 · 95

Respuesta Por tanto, mcd(95, 25) = 5 es equivalente a la combinaci´n lineal: 4 · 25 − 1 · 95 = 5 . o

III

6.

Problema Piratas

Planteamiento x : N´mero de monedas de Oro u x ≡ 3(mod 11) Desarrollo Teorema del Resto Chino Mn • m = 11 · 8 · 3 = 264 •M1 = 264 ÷ 11 = 24 • M2 = 264 ÷ 8 = 33 • M3 = 264 ÷ 3 = 88 24Y1 ≡ 1(mod 11) • Euclides • mcd(24, 11) • 24 = 2 · 11 + 2 • mcd(11, 2) • 11 = 5 · 2 + 1 o • Combinaci´n Lineal • 1 = 11 − 5 · 2 • 1 = 1 · 11 − 5 · (24 − 2 · 11) • 1 = 1 · 11 − 5 · 24 + 10 · 11 • 1 = 11 · 11 − 5 · 24 • Y1 = −5 • Y3 = 1 x • x = 3 · 24 · −5 + 4 · 33 · 1 + 5 · 88 · 1 • x = −360 + 132 + 440 = 212 • x = 212 Respuesta Portanto, el n´mero de monedas con las que qued´ el Cocinero (Como m´ u o ınimo), son: a. 212. • Combinaci´n Lineal o • Combinaci´n Lineal o • 1 = 33 − 4 · 8 • 1 = 1 · 33 − 4 · 8 • Y2 = 1 • 1 = 88 − 28 · 3 • 1 = 1 · 88 − 29 · 3 33Y2 ≡ 1(mod 8) • Euclides • mcd(33, 8) • 33 = 4 · 8 + 1 • mcd(8, 1) • 8=8·1+0 • 33Y2 ≡ 1(mod 8) • 88Y3 ≡ 1(mod 3) 88Y3 ≡ 1(mod 3) • Euclides • mcd(88, 3) • 88 = 29 · 3 + 1 •mcd(3, 1) • 8 =8·1+0 Yn • 24Y1 ≡ 1(mod 11) x ≡ 4(mod 8) x ≡ 2(mod 3)

IV

7.

Problema Edad

Planteamiento x : Edad x = 5k + 4 → x ≡ 4(mod 5) Desarrollo Teorema del Resto Chino Mn • m = 5 · 3 · 7· = 105 • M1 = 105 ÷ 5 = 21 • M2 = 105 ÷ 3 = 35 • M3 = 105 ÷ 7 = 15 21Y1 ≡ 1(mod 5) • Euclides • mcd(21, 5) • 21 = ·5 + 1 • mcd(5, 1) • 5=5·1+0 • Combinaci´n Lineal o • 1 = 21 − 4 · 5 • 1 = 1 · 21 −...