Números Enteros

Congruencia – Función de Euler – Teorema de Fermat

Cálculo del Resto

Ecuaciones Lineales de Congruencia

Números Enteros

Se dice que a es un número entero si

1. a = 0
2. a  IN números naturales
3. – a con a  IN números naturales

El conjunto de números enteros Z = Z-  { 0 }  Z+ siendo

Z- el conjunto de los números enteros negativos.
Z+ el conjunto de los números enteros positivos.

Representación en la recta real

... -5 -4 -3 -2 -1 0 1 2 3 4 5 6 ...

a y – a son números opuestos

División Entera

La división en el conjunto de números enteros no es una operación cerrada pues si

queremos dividir dos números enteros no siempre dá por resultado un número entero.

Por ello se define la división entera

D dividendo
D d
D = c.d + r con 0  r < I d I d divisor
r c c cociente
r resto

Recibe el nombre de “Algoritmo de la División”

Ejemplo:

9 4
9 = 2.4 + 1 con 0  1 < 4
1 2
Divisibilidad
Definición: Sean a, b  Z con a  0. Decimos que a divide a b en Z si  c  Z / b = c.a
Se indica a I b
Se lee: a divide a b b es múltiplo de a
a es divisor de b b es divisible por a

Propiedades
1.  a  Z, a  0: a I a
2.  a, b, c  Z, a  0  b  0: a I b  b I c  a I c
3.  a, b, c  Z, a  0: a I b  a I c  a I b + c
4.  a, b  Z, a  0: a I b  k  Z  a I k.b

Números primos: Sea p  Z, p es un número primo si admite exactamente 4 divisores

a saber 1, -1, p, -p.
Números compuestos: Si a  -1, a  0, a  1 y no es primo se dice compuesto

Observación: Los números -1, 0, y 1 no son primos ni compuestos, son casos particulares
Número par: Es a = 2k, k  Z Número impar: Es a = 2k + 1, k  Z
Teorema fundamental de la aritmética
Todo número entero distinto de -1, 0 y 1, es o bien primo o se puede escribir como
producto de factores primos de manera única salvo el orden.

Ejemplo: 72 2
73 2
74 2 72 = 23 . 32
9 3
3 3
1

132 2
66 2
132 = 22 . 3 . 11
33 3
11 11
1
Máximo Común Divisor
Sean a, b  Z no simultáneamente nulos existe un único número entero positivo d
tal que:
1. d I a  d I b
2. si c  Z+ es tal que c I a  c I b  c I d
Ese número d se llama máximo común divisor entre a y b.

Se indica d = m.c.d. { a, b } o bien d = ( a, b )

Ejemplo:
72 = 23 . 32 y 132 = 22 . 3 . 11
m.c.d. { 72, 132 } = 22 . 3 = 12 O bien ( 72, 132 ) = 12

El máximo común divisor se obtiene como el producto de los factores comunes

elevados al menor exponente.

Coprimos o primos entre sí

Si a y b son dos números enteros y m. c. d. { a, b } = 1 entonces se dicen coprimos o
primos entre si.
Algoritmo de Euclides para calcular el máximo común divisor
Sean a y b números enteros con b > 0 aplicando reiteradamente el algoritmo de la división
se tienen las siguientes ecuaciones recursivas.

a = b . q 1 + r1 0  r1 < b
a b b r1 r1 r2
b = r1 . q 2 + r 2 0  r2 < r1
r1 q1 r2 q2 r3 q3
r1 = r2 . q3 + r3 0  r3 < r2

como cada resto ri < ri + 1  i el proceso es finito, entonces se procede sucesivamente

hasta llegar a un resto igual a cero. De esta manera el máximo común divisor entre
los dos números enteros dados es el último resto no nulo.

Combinación lineal entera – Teorema de Bezaut

Dados a y b  Z y d = ( a, b ) entonces existen m y n números enteros tal que
d=m.a+n.b
Identidad de Bezaut
Dados a y b  Z y ( a, b ) = 1   m y n números enteros tal que 1 = m . a + n . B

Esto permite demostrar que dos números enteros son coprimos, solamente demostrando
que 1 es combinación lineal entera de ambos.

Ejemplo:
Buscar el máximo común divisor entre 120 y 75, además escribirlo como combinación
lineal entera

120 = 1 . 75 + 45
120 75 75 45 45 30 30 15
75 = 1 . 45 + 30
45 1 30 1 15 1 0 2
45 = 1 . 30 + 15
30 = 2 . 15

m. c. d. { 120, 75 } = 15

15 = 45 – 30
15 = 45 – ( 75 – 45 ) = 2 . 45 – 75
15 = 2 ( 120 – 75 ) – 75 = 2 . 120 – 3. 75
15 = 2 . 120 + ( - 3 ) . 75
Mínimo Común Múltiplo
Sean a, b  Z no simultáneamente nulos existe un único número entero positivo m
tal que:
1. aImbIm
2. si k  Z+ es tal que a I k  b I k  m I k
Ese número m se llama mínimo común múltiplo entre a y b

Se indica m = m.c.m. { a, b } o bien m = [ a, b ]

Ejemplo:
36 = 22 . 32 60 = 22 . 3 . 5
m.c.m. { 36, 60 } = [ 36, 60 ] = 22 . 32 . 5 = 180

El mínimo común múltiplo se obtiene como el producto de los factores comunes y no

comunes elevados al mayor exponente.
 Congruencia Módulo n – Función de Euler

 La relación “congruencia módulo n”, que es una relación de equivalencia, clasifica a

los números enteros según su resto en la división por n.

 El conjunto cociente constituye un sistema completo de restos módulo n

 La totalidad de restos r tales que 1  r  n, coprimos con n, forma un sistema

reducido de restos módulo n

La función de Euler, que se indica  (n) es el cardinal del conjunto de estos restos

Formalmente,  (n) = | { x  N / x  n  ( x, n ) = 1} |

Ejemplo:
 (15) = | { 1, 2, 4, 7, 8, 11, 13, 14 } | = 8
Propiedades
1. Si p es un número primo,  (p) = p – 1,
Ejemplo: si p = 3, primo   (3) = 2

2. Si n  IN y p es un número primo se tiene que: φ (pn) = pn ( 1 – 1/p )

Que puede escribirse: φ (pn) = pn -1 ( p – 1 )
Ejemplo: si p = 7 y n = 3   (73) = 73 -1 ( 7 – 1 ) = 49 . 6 = 294

3. Si n y m  IN y ( m, n ) = 1   (n . m) =  (n) .  (m)
Ejemplo: si n = 5 y m = 4 ( 5, 4 ) = 1
 (5 . 4) =  (5) .  (4) = 4 . 2 = 8

 1
4. ( n )n 1  p divisores primos de n
pI n  p

Ejemplo: si p = 48 los divisores primos de 48 son 2 y 3

æ 1öæ 1ö
÷ 1 2
φ( 48 )= 48 ç
ç1- ç
÷
ç
÷1- ÷
= 48. . =16
÷
÷
ç
è 2øç
è 3ø 2 3
Propiedades
Además de las que figuran el la guía
1. a  b (n)  c  Z  a + c  b + c (n)
2. a  b (n)  c  Z  a . c  b . c (n)
3. a  b (n)  s  Z+  as  bs (n)

Teorema de Fermat
Si p es primo  ap  a (p)

Pequeño Teorema de Fermat

Sean a, p  Z y p es primo, si ( a, p ) = 1  ap -1  1 (p)

Teorema de Euler – Fermat

Si ( a, n ) = 1  aφ(n)  1 (n)
Cálculo del Resto
Ejemplo: Calcular el resto de dividir 417 2

a) r ( 5417, 3 ) p = 3 primo ( 5, 3 ) = 1 417 = 2 . 208 + 1 17 208

Teniendo en cuenta que ap-1  1 (p) 1

52  1 (3)  52.208  1 (3)  52.208 . 5  5 (3)  52.208 + 1  5 (3)  5417  5 (3)  2 (3)
Resto = 2
7385 16

98 461
b) r ( 477385, 17 ) p = 17 primo ( 47, 17 ) = 1 7385 = 16 . 461 + 9
25
Teniendo en cuenta que ap-1  1 (p)
9

4716  1 (17)  4716.461  1 (17)  4716.461 . 479  479 (17)  4716.461 + 9  479 (17)

47  47 (17)  13 (17) 476  47 . 13 (17)  16 (17)

472  47 . 13 (17)  16 (17) 477  47 . 16 (17)  4 (17)
473  47 . 16 (17)  4 (17) 478  47 . 4 (17)  1 (17)
474  47 . 4 (17)  1 (17) 479  47 . 1 (17)  13 (17)
475  47 . 1 (17)  13 (17) Resto = 13
Ecuaciones Lineales de Congruencia
Una expresión de la forma ax  b (n) se denomina ecuación lineal de congruencia

Condición nacesaria y suficiente para que una ecuación de congruencia

tenga solución
Para que la ecuación ax  b (n) admita una solución es que ( a, n ) | b

x a   .b
 n 1
La solución es

En general: Si x es una solución entonces x + kn también es solución.

Como son infinitas las soluciones se consideran 0  x < n que reciben el nombre de
soluciones principales
Ejemplo:
a) 5x  14 (18) ( 5, 18 ) = 1 1 | 14 hay solución
43750 18
 1  1 1 2
1818 1   1  18. . 6
 2  3 2 3 77 2430

55
x = 56 – 1 . 14  x = 3125 . 14 = 43750
10
x = 10 solución principal  x = 10 + 18k, k  Z

b) 18x  0 (15) ( 18, 15 ) = 3 3 | 0 hay solución

dividiendo por 3 todos los números queda
6x  0 (5)
Como 5 es un número primo  (5) = 5 – 1 = 4
x = 64 – 1 . 0 = 0
Son soluciones principales x=0
x=5
x = 10
 x = 0 + 5k, k  Z
c) 7x  1 (11) ( 7, 11 ) = 1 1 | 1 tiene solución

Como 11 es un número primo  (11) = 11 – 1 = 10

x = 710 – 1 . 1 = 79

7  7 (11)
72  7 . 7 (11)  5 (11)
73  7 . 5 (11)  2 (11)
74  7 . 2 (11)  3 (11)
75  7 . 3 (11)  10 (11)
76  7 . 10 (11)  4 (11)
77  7 . 4 (11)  6 (11)
78  7 . 6 (11)  9 (11)
79  7 . 9 (11)  8 (11)

La solución principal es x = 8
 x = 8 + 11k, k  Z