Memphis 16-MCD250 Manuel d'utilisateur

Cap´ıtulo 3Teor´ıa de n´umeros3.1. Principio de inducci´onUna caracter´ıstica fundamental de los n´umeros naturales es que cualquie-ra de ellos puede

56 CAP´ITULO 3. TEOR´IA DE N´UMEROSDemostraci´on. Es claro que 1 = ma + nb = ka + lc, con lo que 1 = 1 ∗ 1 =(ma + nb) ∗(k a + lc) = (mka + nkb + lmc)

3.4. N´UMEROS PRIMOS. FACTORIZACI´ON 57Demostraci´on. Veamos que 1) ⇒ 2). Sea p un primo que divide a ab y sead = mcd(a, p). Como d | p, se tiene que

58 CAP´ITULO 3. TEOR´IA DE N´UMEROSDemostraci´on. Supongamos que p1, . . . , prfuesen todos los primos y conside-remos m = p1···pr+ 1. El teorema ante

3.5. ECUACIONES DIOF´ANTICAS 59b = ±pβ11pβ22···pβrrcon αi, βi≥ 0. Con esta descomposici´on se tiene que:Teorema 7. Dados a, b enteros con la descompos

60 CAP´ITULO 3. TEOR´IA DE N´UMEROSDemostraci´on. Sean (x, y) y (x0, y0) dos soluciones de ax + by = n. Es claroque:ad(x − x0) =bd(y0− y)con lo quebdd

3.5. ECUACIONES DIOF´ANTICAS 61a = 145 y b = 3, con lo que x = 74, y = 71a = 87 y b = 5, con lo que x = 46, y = 41a = 29 y b = 15, con lo que x = 22,

62 CAP´ITULO 3. TEOR´IA DE N´UMEROSTeorema 11. La soluciones de la ecuaci´on x2+ y2= z2verificando quex, y, z son naturales, mcd(x, y, z) = 1 y x es pa

3.6. CONGRUENCIAS 63Ejemplo 33. 7 ≡34 y 18 ≡26.Teorema 12. Cada entero a es congruente m´odulo m con uno de los enteros{0, 1, . . . , m −1}.Demostraci

64 CAP´ITULO 3. TEOR´IA DE N´UMEROSDemostraci´on4) Si a −b = mt y c −d = mt0, entoncesa + c = b + d + mt + mt0ac = (b + mt)(d + mt0) = bd + mtd + mt0b

3.6. CONGRUENCIAS 65Demostraci´onEn primer lugar hay que tener en cuenta que encontrar una soluci´on enterax0de ax ≡mb implica encontrar (x0, y0) ente

48 CAP´ITULO 3. TEOR´IA DE N´UMEROSii) Para todo natural n, se verifica que 1 + 2 + ··· + 2n= 2n+1− 1.i ii) Para todo natural n, se tiene queµ1 +13¶n≥³

66 CAP´ITULO 3. TEOR´IA DE N´UMEROSDemostraci´on. Para cada i = 1, 2, . . . , k, sea ti=mmiy sea yila ´unicasoluci´on m´odulo mique admite la ecuaci´o

3.6. CONGRUENCIAS 67Opci´on 1: b1= 3, b2= 4, b3= 1.En este caso,x0= 3 · 15 ·7 + 4 · 24 · 4 + 1 · 40 · 1 = 739.Las restantes soluciones son x = 739 + λ

68 CAP´ITULO 3. TEOR´IA DE N´UMEROSy utilicemos la aplicaci´on:f : C → A × Bdefinida por f(c) = (a, b), donde c ≡ma y c ≡nb. Puesto que f es biyec-tiva

3.6. CONGRUENCIAS 69Teorema 17. Si p es un n´umero primo que no divide al entero a, entoncesap−1≡p1Demostraci´on. Basta aplicar el Teorema de Euler ya

70 CAP´ITULO 3. TEOR´IA DE N´UMEROS3.7. Introducci´on a la Criptograf´ıaCriptograf´ıa: Kryptos: escondido + graphein = escritura.El objetivo de la cri

3.7. INTRODUCCI´ON A LA CRIPTOGRAF´IA 71durante la segunda mitad del siglo XX. Despu´es de la guerra, los criptoa-nalistas continuaron desarrollando y

72 CAP´ITULO 3. TEOR´IA DE N´UMEROScuenta que aqu´ı dif´ıcil es sin´onimo de computacionalmente no factiblecon los mejores algoritmos y el mejor hardw

3.7. INTRODUCCI´ON A LA CRIPTOGRAF´IA 73Supongamos que escoge e = 7. A hace p´ublicos los n´umeros n y e enalgo similar a una gu´ıa de tel´efonos. (n,

74 CAP´ITULO 3. TEOR´IA DE N´UMEROSDemostraci´on. Si mcd(a, n) = 1, entonces el Teorema de Euler garantiza queaφ(n)≡n1 y, en consecuencia:aed= aφ(n)k+

3.8. SISTEMAS DE NUMERACI´ON 75Roberto desencripta N haciendo:Nd≡n43853517119923≡n(4385351750000)24385351719923≡n(133807774)2· 281712138 ≡n300145477 ·

3.1. PRINCIPIO DE INDUCCI´ON 49En ocasiones conviene demostrar que una propiedad es cierta para todoslos enteros mayores que un entero n0. Los princip

76 CAP´ITULO 3. TEOR´IA DE N´UMEROSEjemplo 40. Escribamos 45 en base 2, 3 y 4.45 = 32 + 8 + 4 + 1 = 25+ 23+ 22+ 2045 = 27 + 18 = 33+ 2 ×3245 = 2 × 42+

3.8. SISTEMAS DE NUMERACI´ON 77Completamos el primer bloque a 001. Nos quedan as´ı bloques de tres que secorresponden con n´umeros de 0 a 7 y ser´an l

50 CAP´ITULO 3. TEOR´IA DE N´UMEROSEjemplo 22. Probemos que todos los coru˜neses tienen la misma edad. Esevidente que un conjunto unitario verifica la

3.2. DIVISIBILIDAD EN Z 51v) Sean a > 0 y b > 0 dos enteros. Si a | b, entonces a ≤ b.Dado que b = aq y q ha de ser mayor que cero, es claro que

52 CAP´ITULO 3. TEOR´IA DE N´UMEROSDemostraci´on. Probemos, en primer lugar la existencia y luego la unicidad.ExistenciaConsideremos el conjunto:M = {

3.3. ALGORITMO DE EUCLIDES 53Ejemplo 24. Si a es cualquier n´umero entero, entonces a, a + 1 o a + 2 esun m´ultiplo de 3. Al dividir a entre 3, obtene

54 CAP´ITULO 3. TEOR´IA DE N´UMEROSLa aplicaci´on reiterada del lema anterior conduce al c´alculo del m´aximocom´un divisor y se cono ce con el nombre

3.3. ALGORITMO DE EUCLIDES 55Por otro lado, si dividimos a entre d, obtenemos a = dq+r, con 0 ≤ r < d.Puesto que r < d = min(S), es claro que r