Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 30 vistas

    Tema 4 - Teoria de Numeros y Aritmetica Modular - FVC

    Cargado por

    José Moruno Arena
    Este documento resume los principales temas de la teoría de números y la aritmética modular, incluyendo la divisibilidad, los números primos, el máximo común divisor, el mínimo común múltiplo y la congruencia modular. Explica algoritmos como la división por tentativa, la criba de Eratóstenes y la división euclídea para determinar la primalidad de los números y calcular el máximo común divisor. También describe aplicaciones de la aritmética modular en criptografía y generación de números pseudoaleatorios.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd

    Tema 4 - Teoria de Numeros y Aritmetica Modular - FVC

    Cargado por

    José Moruno Arena
    30 vistas19 páginas
    Este documento resume los principales temas de la teoría de números y la aritmética modular, incluyendo la divisibilidad, los números primos, el máximo común divisor, el mínimo común múltiplo y la congruencia modular. Explica algoritmos como la división por tentativa, la criba de Eratóstenes y la división euclídea para determinar la primalidad de los números y calcular el máximo común divisor. También describe aplicaciones de la aritmética modular en criptografía y generación de números pseudoaleatorios.

    Título original

    Tema 4_Teoria de numeros y aritmetica modular_FVC

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento resume los principales temas de la teoría de números y la aritmética modular, incluyendo la divisibilidad, los números primos, el máximo común divisor, el mínimo común múltiplo y la congruencia modular. Explica algoritmos como la división por tentativa, la criba de Eratóstenes y la división euclídea para determinar la primalidad de los números y calcular el máximo común divisor. También describe aplicaciones de la aritmética modular en criptografía y generación de números pseudoaleatorios.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    30 vistas19 páginas

    Tema 4 - Teoria de Numeros y Aritmetica Modular - FVC

    Cargado por

    José Moruno Arena
    Este documento resume los principales temas de la teoría de números y la aritmética modular, incluyendo la divisibilidad, los números primos, el máximo común divisor, el mínimo común múltiplo y la congruencia modular. Explica algoritmos como la división por tentativa, la criba de Eratóstenes y la división euclídea para determinar la primalidad de los números y calcular el máximo común divisor. También describe aplicaciones de la aritmética modular en criptografía y generación de números pseudoaleatorios.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    Está en la página 1de 19

    Álgebra y Matemática Discreta

    Prof. Federico Vicente Cristóbal

    Tema 4: Teoría de números y aritmética modular

    Universidad Internacional de La Rioja


    Índice

    ► Divisibilidad y aritmética modular

    ► Números primos

    ► Máximo común divisor y mínimo común múltiplo

    2
    Esquema

    3
    Teoría de números y Aritmética modular

    Teoría de números: Rama de las matemáticas que estudia las


    propiedades de los números enteros y su divisibilidad

    Por ejemplo: la teoría de los números primos, basada en la Propiedad


    de la divisibilidad, permite transmitir información encriptada

    Aritmética modular: Estudia las operaciones y propiedades de


    congruencia entre enteros respecto a un módulo

    Sistema aritmético para clases de equivalencia de números enteros


    (clases de congruencia)

    Por ejemplo: Aritmética del reloj permite que los números coincidan
    tras alcanzar cierto valor común llamado modulo

    4
    Divisibilidad y aritmética modular

    5
    Números primos

    Número primo: número natural mayor que 1 que tiene únicamente


    dos divisores positivos distintos: él mismo y el 1

    Contrariamente, los números compuestos son los números naturales que


    tienen algún divisor natural aparte de sí mismos y del 1, y, por lo tanto,
    pueden factorizarse

    El número 1, por convenio, no se considera ni primo ni compuesto

    6
    Números primos: La división por tentativa

    La división por tentativa garantiza encontrar un factor de n, puesto que


    comprueba todos los factores primos posibles de n

    Si el algoritmo no encuentra ningún factor, es una prueba de que n es primo

    Si un resto en la división es cero, entonces el número no es número primo

    La división por tentativa es mejor que la Criba de Erastóstenes si solo quiere


    determinar la primalidad de un número

    En términos de rendimiento, la división por tentativa es más lenta que la


    Criba de Eratóstenes cuando encuentra un rango de números primos

    7
    Números primos: Criba de Eratóstenes

    Video donde se muestra como se van


    descartando los números no primos: https://es.wikipedia.org/wiki/Criba_de_Erat%C3%B3stenes
    #/media/Archivo:Sieve_of_Eratosthenes_animation.gif

    Fuente: https://www.smartick.es/blog/matematicas/numeros/numeros-primos-criba-eratostenes/

    8
    Números primos: Teorema fundamental de la
    Aritmética

    Las funciones aritméticas aditivas y multiplicativas están completamente


    determinadas por sus valores en las potencias de los números primos

    El teorema establece la importancia de los números primos

    Son los «ladrillos básicos» con los que se «construyen» los enteros
    positivos, en el sentido de que todo entero positivo puede construirse como
    producto de números primos de una única manera

    9
    Números primos: Teorema de los números primos

    Demuestra que los primos son menos comunes cuanto más grandes son

    La cantidad π(x) de primos menores o iguales que un número x, es


    aproximadamente x/log(x) cuando x es grande (el cociente entre ambas
    cantidades tiende a “1” cuando x tiende a infinito).

    Existe una profunda conexión entre ambos conceptos: la función


    logaritmo permite describir la distribución de los números primos

    π(1) = 0 (no hay primos ≤ 1)


    π(2) = 1 (único primo ≤ 2 es 2)
    π(3) = 2 (primos ≤ 3 son 2 y 3)
    π(4) = 2 (id.)
    π(5) = 3 (primos ≤ 5 son 2, 3 y 5)
    ...
    π(10) = 4 (primos ≤ 10 son 2, 3, 5 y 7)
    ...
    10
    División euclídea: El algoritno de la división

    El proceso de la división de un número asegura la aparición de dos


    valores únicos, el cociente y el resto, que caracterizan a dicho
    número

    11
    División euclídea: Máximo común divisor y mínimo
    común múltiplo
    MÁXIMO COMÚN DIVISOR (mcd)

    12
    División euclídea: Máximo común divisor y mínimo
    común múltiplo
    El algoritmo de Euclides es un método antiguo para calcular el mcd(a,b)
    de una manera más eficiente que factorizar a y b en sus factores primos.

    Al dividir a entre b (números enteros), se obtiene un cociente q y un resto r.


    El algoritmo de Euclides dice que es posible demostrar que el mcd(a,b) es
    el mismo que mcd(b,r).

    Y podemos seguir usando divisiones sucesivas para así reducir el problema


    del calculo de mcd de dos enteros positivos a un problema idéntico sobre
    números enteros más pequeños, hasta que uno de ellos se haga cero.
    Ejemplo: Comprobar que mcd(28,6) es el mismo que mcd(6,r)
    Como r=4 . Tenemos que comprobar que mcd(28,6) = mcd(6,4)

    13
    División euclídea: Máximo común divisor y mínimo
    común múltiplo
    Ejemplo: Calcular el mcd (287,91) Según el Algoritmo de Euclides
    mcd (287,91) = mcd (91,14), ya que 287 = 91 3 + 14
    mcd (91,14) = mcd (14,7), ya que 91 = 14 6 + 7
    mcd (14,7) = mcd (7,0), ya que 14 = 7 2 + 0
    Por lo tanto mcd (287,91) = mcd (91,14) = mcd (14,7) = mcd (7,0) = 7

    MÍNIMO COMÚN MULTIPLO (mcm)

    Ejemplo: Calcular el mcm(28,6)

    14
    División euclídea: Máximo común divisor y mínimo
    común múltiplo

    Ejemplo: Comprobar que se cumple el teorema anterior con 28 y 6


    Tenemos que comprobar que
    28 . 6 = mcd(168,6) . mcm(168,6)
    En los ejercicios anteriores, hemos visto que:
    mcd(168,6) = 2
    mcm(168,6) = 84
    Si sustituimos esos valores en la igualdad de arriba tenemos que
    28 . 6 = 2 . 84
    168 = 168
    Por lo tanto, hemos comprobado que se cumple dicho teorema con 28 y 6

    15
    División euclídea: Congruencia modular

    En Teoría de Números se utiliza la congruencia para indicar que dos


    números enteros, a y b, tienen el mismo resto al dividirlos por un
    número natural, m (módulo)

    Ejemplos: a) Calcula el valor de: 56 mod 6; de 5 mod 8 y de 92 mod 11


    b) Ver si 23 es congruente con 5 mod 9. Y si 16 y 4 son congruentes con mod 5
    a) 56 mod 6 = 2 ; 5 mod 8 = 5 ; 92 mod 11 = 4
    b) 23 – 5 = 18 que es divisible por 9. Por lo tanto 23 5 mod 9 y además
    se cumple que 23 mod 9 = 5 mod 9 = 5
    16 – 4 = 12 que no es divisible por 5. Por lo tanto 16 4 mod 5

    16
    Aplicaciones de la aritmética modular
    Las congruencias tienen muchas aplicaciones en matemática discreta y
    ciencias de la computación.
    Una de las aplicaciones más importantes de las congruencias está relacionada
    con la Criptografía, que es el estudio de los mensajes secretos, que veremos
    en el próximo tema 5.
    Otra aplicación de las congruencias es su uso en la generación de números
    pseudoaleatorios.

    17
    Aplicaciones de la aritmética modular

    18
    www.unir.net

    También podría gustarte