Modulo III

 Aritmética entera y modular:

Divisibilidad:

      La divisibilidad en las matemáticas se refiere a la propiedad de los números enteros (números sin decimales) de dividirse por otro número entero y que su resultado sea a su vez un número entero. Por ejemplo, los números 3, 6, 9 y 12 tienen divisibilidad por 3, porque cuando divides cada uno de esos números enteros por 3 resultan números enteros: 1, 2, 3 y 4. La operación aritmética para dividir se llama división, que se compone de un divisor y un dividendo. El divisor es el número del total que queremos dividir y el dividendo es el número de partes que queremos saber que caben en el número total (divisor). Algunas de las propiedades que se deben tomar en cuenta para facilitar el ejercicio de la divisibilidad son:

• Los números divisibles solo se componen de números enteros distintos a cero.
• Todos los números son divisibles por 1 y por sí propio.

Algoritmo de Euclides: 

     El algoritmo de Euclides es un método para calcular el máximo común divisor (MCD). Fue escrito por Euclides en su obra magna Elementos. Dicho algoritmo funciona no sólo para los números naturales, sino para cualquier conjunto en el que exista una "división con residuo". A este tipo de divisiones en la que existe residuo se les nombra divisiones euclidianas y a los conjuntos donde se puede definir dicha división se les llama dominios euclídeos. Con lo anterior podemos decir que el algoritmo de Euclides extendido es una ligera modificación del Algoritmo de Euclides que permite además expresar al máximo común divisor como una combinación lineal. Este algoritmo tiene aplicaciones en diversas áreas como álgebra, teoría de números y ciencias de la computación, entre otras. Por ejemplo, el conjunto de los números enteros y el de los polinomios con coeficientes racionales son dominios euclídeos porque podemos definir una división con residuo. El algoritmo de Euclides se puede representar con la siguiente proposición:

• Sean \(a \), \(b \) enteros no nulos. Entonces \(MCD(a,b) = MCD(b,r) \) donde \(r \) es el único \(0 < r < b \) tal que existe un entero \(q \) con \(a= bq + r \). Esto es, que \(r \) es el resto de la división de \(a \) por \(b \).

     Esta proposición nos indica que es igual de válido calcular el \(MCD(a,b) \) que el \(MCD(b,r) \), con la ventaja de que \(r \) es un entero de menor tamaño que el original a. Esto es aprovechado por el algoritmo de Euclides para el cálculo del máximo común divisor de dos números enteros. Para calcular el \(mcd \) de dos enteros \(a \) y \(b \) (ambos \(>0 \), suponemos \(a > b \)) se definen \(q_i \) y \(r_i \) recursivamente mediante las ecuaciones:

\[a = bq_1 + r_1 \ \   (0<r_1<b) \] \[b = r_1q_2 + r_2 \ \  (0<r_2<r_1) \] \[r_1 =r _2q_3 + r_3 \ \  (0<r_3<r_2) \] \[.... \] \[r_{k-3} = r_{k-2}q_{k-1} + r_{k-1}  \ \ (0<r_{k-1}<r_{k-2}) \] \[r_{k-2} = r_{k-1}q_k  \ \ (r_k=0) \]. Y de la proposición anterior, se sigue que:

• \[MCD(a,b) = MCD(b,r_1) = MCD(r_1,r_2) = ... = MCD(r_{k-2},r_{k-1}) = r_{k-1} \]

     Además se puede demostrar que el número de pasos necesarios para calcular el mcd de dos números es menor que 5 veces el número de dígitos del menor de ellos.

Congruencias:

      

      Congruencia es un término usado en la teoría de números, para designar que dos números enteros  tienen el mismo resto al dividirlos por un número natural , llamado módulo; esto se expresa utilizando la notación:

${\displaystyle a\equiv b{\pmod {m}}}$

que se expresa diciendo que: ${\displaystyle a\,}$ es congruente con ${\displaystyle b\,}$ módulo ${\displaystyle m\,}$. De donde se define que dos números ${\displaystyle a\,\textstyle {\text{y}}\displaystyle \,b}$ son congruentes en módulo ${\displaystyle m\,\neq \,0}$ «» (sí y solo si) :

• ${\displaystyle m\,}$ divide exactamente a la diferencia de ${\displaystyle a\,}$ y ${\displaystyle b\,}$

${\displaystyle m\mid a-b}$

o lo que es lo mismo, ${\displaystyle a\,\textstyle {\text{y}}\displaystyle \,b}$ dejan el mismo resto en la división por ${\displaystyle m\,}$. Además, también se puede afirmar que:

• ${\displaystyle a\,}$ se puede escribir como la suma de ${\displaystyle b\,}$ y un múltiplo de ${\displaystyle m\,}$, pues si: ${\displaystyle m\mid a-b}$ » (entonces), ${\displaystyle mk=a-b}$, para algún ${\displaystyle k\in \mathbb {Z} \quad (entonces)\ a=b+km}$

El término congruencia se utiliza además con dos sentidos ligeramente diferentes: por un lado con el sentido de identidad matemática, como ejemplo de este uso tenemos el pequeño teorema de Fermat que asegura que para cada primo ${\displaystyle p\,}$ y cada entero ${\displaystyle a\,}$ no divisible por ${\displaystyle p\,}$ tenemos la congruencia:

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}.}$¹​

Por otro lado se utiliza en el sentido de ecuación, donde aparecen una o más incógnitas, y nos preguntamos si una congruencia tiene solución y en caso afirmativo cuáles son todas sus soluciones, por ejemplo la congruencia ${\displaystyle x^{2}-5\equiv 0{\pmod {11}}}$, tiene solución, y todas sus soluciones vienen dadas por ${\displaystyle x\equiv 4{\pmod {11}}}$ y ${\displaystyle x\equiv 7{\pmod {11}}}$, es decir ${\displaystyle x\,}$ puede ser cualquier entero de las sucesiones ${\displaystyle 11k+4\,}$ y ${\displaystyle 11k+7\,}$. Contrariamente la congruencia ${\displaystyle x^{2}-2\equiv 0{\pmod {11}}}$, no tiene solución.

     La notación y la relación terminología fueron introducidas por Carl Friedrich Gauss en su libro Disquisitiones Arithmetica en 1801. Su utilización se ha extendido a muchos otros entornos en los que podemos hablar de divisibilidad, por ejemplo a polinomios con coeficientes en un cuerpo, a ideales de anillos de números algebraicos, etc.

Resolución de Sistemas de congruencias de números enteros:

      Una congruencia de la forma:

ax ≡ b (mod m)

donde m es un entero positivo, a y b son números enteros y x es una variable entera, se llama congruencia lineal o ecuación de congruencia lineal (lineal por aparecer la variable x como potencia de grado uno, únicamente). Resolver esta ecuación consiste (como en el caso de la aritmética entera) en encontrar todos los enteros x que satisfagan la ecuación diofántica equivalente ax+my=b. En el caso de Z_m, la ecuación tendrá solución si y solo si mcd(a,m)|b , y en este caso tendrá exactamente d=mcd(a,m) soluciones distintas en Z_m de la forma:

x= x0 + (m.t)/d , t=0,1,2,...,d-1

en donde x₀ es una solución particular de la ecuación diofántica ax + my = b. En el apartado dedicado al algoritmo de Euclides se indica como puede utilizarse este algoritmo para calcular una solución particular de una ecuación diofántica.

Sistemas de numeración:

      Un sistema de numeración es aquel que nos representan cantidades numéricas mediante un conjunto de símbolos. La utilidad de los sistemas de numeración en el tema que nos ocupa es determinante.  La razón es que todos los ordenadores utilizan el sistema de numeración binaria para representar la información (no sólo los números).    Dentro de una red cada equipo tiene un identificador único denominado dirección IP y que, para conocerlo en profundidad, necesitaremos conocer su representación decimal y su representación binaria.

Los sistemas de numeración actuales son posicionales, es decir, un símbolo puede tener un significado diferente en función de su posición.  Las características de los sistemas posicionales son las siguientes:

• Se emplea un número finito de símbolos, dígitos o cifras, lo que determina la base del sistema.  Por ejemplo el sistema decimal utiliza los dígitos: 0,1,2,3,4,5,6,7,8,9 para representar los números y como estos símbolos son diez se dice que la base es 10.
• Cada cantidad viene expresada por una secuencia finita de símbolos del sistema.
• La cantidad total expresada se obtiene sumando el valor de cada uno de los símbolos.
• El valor de cada símbolo depende de sí mismo y de la psoción que ocupa dentro de la secuencia de símbolos.  Normalmente tendrá más valor cuanto más a la izquierda se sitúe.  
• Así los dígitos 983 en base 10  que representaremos así 983(10 representan al número 9*10²+8*10¹+3*10⁰ =983.  
• 10110(2 representa el número 1*2⁴+ 0*2³+ 1*2² +1*2¹ +0 *2⁰ = 22(10

Como se puede observar , cuanto mayor sea la base del sistema, mayor será el número de símbolos del alfabeto y menor será el número de cifras necesarias para representar una cantidad.  El mayor número que se puede representar, en una base b, com m dígitos es b^m -1.

      Los sistemas de numeración más usados en informática y, por tanto, en las redes de ordenadores son los siguientes:

• Binario.  La base del sistema es 2. Se utilizan los dígitos 0 y 1.  Se utilizan en todas las máquinas electrónicas digitales ya que éstas solo pueden representar dos estados.  En particular lo utilizan los ordenadores.  Con n dígitos binarios se pueden  representar los enteros comprendidos ne el rango [0, 2ⁿ-1].
• Decimal.  La base del sistema es 10.  Se utilizan los dígitos 0,1,2,3,4,5,6,7,8,9
• Hexadecimal. La base del sistema es 16.  Se utilizan los dígios 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
• Octal. La base del sistema es 8.  Los dígitos son 0,1,2,3,4,5,6,7.

Criterios de divisibilidad:

      Los criterios de divisibilidad son reglas que sirven para saber si un número es divisible por otro sin necesidad de realizar la división.

Estas son las reglas más comunes:

DIVISIBILIDAD POR 2: Un número es divisible por dos si termina en cero o en cifra par.

• 24 es divisible por 2 porque es par.
• 31 no es divisible por 2 porque no es par.

DIVISIBILIDAD POR 3: Un número es divisible por tres, si la suma de sus cifras es múltiplo de tres.

• 42 es divisible por 3 porque 4 + 2 = 6 es múltiplo de tres.
• 43 no es divisible por 3 porque 4 + 3 = 7 que no es múltiplo de tres.

DIVISIBILIDAD POR 5: Un número es divisible por cinco cuando acaba en cero o en cinco.

• 35 es divisible por 5 porque acaba en cinco.
• 540 es múltiplo de 5 porque acaba en cero.

DIVISIBILIDAD POR 9: Un número es divisible por nueve cuando la suma de sus cifras es múltiplo de nueve.

• 45 es divisible por 9 porque la suma de sus cifras es múltiplo de 9 (4 + 5 = 9)
• 738 es múltiplo de 9 porque 7 + 3 + 8 = 18, que es múltiplo de 9.

DIVISIBILIDAD POR 10: Un número es divisible por 10 si termina en cero. De manera similar, si termina en 00 es divisible por 100; si termina en 000 es divisible por 1000.

• El número 70 es divisible por 10 porque termina en cero