aritmética de los números enteros - · pdf file2.1. la relación de...

Aritmética de los números enterosJosé Luis Ruiz Muñoz

1 créditoP00/75004/00190

FUOC • P00/75004/00190 Aritmética de los números enteros

Índice

Introducción............................................................................................... 5

Objetivos ...................................................................................................... 6

1. El anillo de los números enteros ...................................................... 7

2. Divisibilidad .......................................................................................... 9

2.1. La relación de divisibilidad ................................................................ 9

2.2. El máximo común divisor ................................................................. 12

2.3. El algoritmo de Euclides .................................................................... 14

2.4. El algoritmo de Euclides extendido................................................... 18

2.5. El mínimo común múltiplo .............................................................. 20

3. Ecuaciones diofánticas ....................................................................... 22

4. Números primos y factorización de enteros ................................. 25

5. Congruencias de números enteros ................................................... 30

5.1. La relación de congruencia................................................................ 30

5.2. Clases de congruencias ...................................................................... 33

6. Anillos de enteros modulares............................................................ 35

6.1. Operaciones con clases ...................................................................... 35

6.2. Clases invertibles ............................................................................... 36

6.3. La función de Euler............................................................................ 38

6.4. Teoremas de Fermat y de Euler .......................................................... 42

6.5. Pruebas de divisibilidad ..................................................................... 44

Resumen....................................................................................................... 46

Actividades complementarias................................................................ 47

Ejercicios de autoevaluación .................................................................. 47

Solucionario................................................................................................ 49

Glosario ........................................................................................................ 55

Bibliografía................................................................................................. 56

FUOC • P00/75004/00190 5 Aritmética de los números enteros

Introducción

Este módulo está dedicado a la aritmética de los números enteros. Lo empeza-

mos recordando las nociones básicas de los enteros que utilizamos a lo largo

del módulo. A continuación, estudiamos los conceptos de divisor y múltiplo

y las propiedades de la relación de divisibilidad, entre las cuales destaca el teo-

rema de la división entera, del que se deducen muchas de las propiedades de

los enteros que después se estudian.

Introducimos el máximo común divisor, estudiamos con detalle sus propiedades

más interesantes y damos un método, el algoritmo de Euclides, para su cálculo.

Este algoritmo es un punto clave en muchas de las cuestiones que siguen. Acaba-

remos esta sección con el estudio del mínimo común múltiplo y su cálculo.

A continuación hacemos un interludio para estudiar las ecuaciones lineales

con dos variables y coeficientes enteros, porque están estrechamente relacio-

nadas con el algoritmo de Euclides (la resolución efectiva en los enteros de es-

tas ecuaciones utiliza una versión ampliada de este algoritmo).

Después dedicamos un momento al estudio de los números primos y demos-

tramos el teorema fundamental de la aritmética o teorema de la factorización

única de los enteros como producto de primos.

En el apartado dedicado a las congruencias, definimos este concepto y demos-

tramos sus propiedades. Como veremos, es un concepto muy útil y, al mismo

tiempo, tiene una notación clara y cómoda, muy parecida a la relación de

igualdad.

Continuamos con los anillos de enteros modulares y la forma de operar con

los mismos: suma y producto de clases, cálculo de la clase inversa de una clase

invertible y cálculo de la función de Euler.

Acabamos el módulo viendo algunas aplicaciones de las congruencias.


Objetivos

Los contenidos de este módulo introducen al estudiante en los conceptos bá-

sicos de la aritmética de los números enteros y la algorítmica involucrada. Una

vez trabajados los contenidos de este módulo didáctico, el estudiante debe es-

tar preparado para:

1. Entender los conceptos de divisibilidad, de máximo común divisor y míni-

mo común múltiplo y utilizar el algoritmo de Euclides.

2. Saber resolver las ecuaciones diofánticas lineales con dos variables.

3. Familiarizarse con la noción de congruencia y con las operaciones básicas

con congruencias.

4. Calcular en los anillos de enteros modulares: operaciones con clases.

5. Saber calcular la función de Euler y conocer sus utilidades.


1. El anillo de los números enteros

En este apartado presentamos el conjunto de números enteros y menciona-

mos los hechos y las propiedades básicas que utilizamos más adelante. Supon-

gamos un conocimiento, aunque sea intuitivo, de lo que es un número entero.

A continuación expresamos con precisión cuáles son las propiedades básicas

que satisfacen los números enteros, en las que basamos los estudios de divisi-

bilidad que haremos en apartados posteriores.

Representaremos con Z el conjunto de los números enteros:

El conjunto de los números naturales:

es un subconjunto de Z y es, por definición, el conjunto de los números ente-

ros positivos.

Los números enteros se pueden sumar y multiplicar. El resultado de la suma y

de la multiplicación de dos enteros es otro entero; es decir, la suma y el pro-

ducto son operaciones binarias internas en el conjunto Z.

La terna (Z, +, ·) es un anillo conmutativo con unidad.

Con esta frase queremos decir que la suma satisface las propiedades siguientes:

• Propiedad asociativa: si a, b, c ∈ Z, entonces a + (b + c) = (a + b) + c.

• Propiedad conmutativa: si a, b ∈ Z, entonces a + b = b + a.

• Existencia de elemento neutro: si a ∈ Z, entonces 0 + a = a + 0 = a.

• Existencia de elemento inverso: si a ∈ Z, entonces a+ (−a) = 0 .

Y que el producto satisface las propiedades siguientes:

• Propiedad asociativa: si a, b, c ∈ Z, entonces a(bc) = (ab )c.

• Propiedad conmutativa: si a, b ∈ Z, entonces ab = ba.

• Existencia de elemento neutro: si a ∈ Z, entonces 1 · a = a.

Z 0, 1, 2, …±±{ }=

N 0, 1, 2, …{ }=


Y que, además, hay una propiedad adicional que relaciona la suma y el pro-

ducto; nos referimos a la propiedad distributiva:

• Propiedad distributiva: si a, b, c ∈ Z, entonces a(b + c ) = ab + ac.

En general, en Z no hay inversos respecto del producto; sólo los enteros ±1 los

tienen. A pesar de ello, el producto satisface la propiedad siguiente:

• Ley de cancelación: si a, b, c ∈ Z satisfacen a · c = b · c y c ≠ 0, entonces

a = b.

Gracias a estas propiedades, es posible resolver en el anillo de los enteros las

ecuaciones del tipo a + x = b , con a y b enteros.

Las propiedades básicas referentes a la relación de orden en los enteros son las

siguientes:

1) Ley de tricotomía: si a ∈ Z, entonces exactamente una de las relaciones

siguientes es cierta: a< 0, a = 0 o a > 0.

2) Clausura de los enteros positivos: si a, b ∈ Z son enteros positivos, enton-

ces a + b y a · b son enteros positivos.

3) Principio de la buena ordenación: todo conjunto no vacío de enteros po-

sitivos tiene un primer elemento o elemento mínimo; es decir, un elemento

menor o igual que todos los demás miembros del conjunto. De forma equiva-

lente, cualquier subconjunto de N tiene un elemento mínimo. Diremos que el

conjunto N es un conjunto bien ordenado.

Observemos que el conjunto de enteros no es un conjunto bien ordenado. Por

ejemplo, el subconjunto de los enteros negativos no tiene un elemento mínimo.

En Z tenemos definida una relación de orden total : si a y b son en-

teros, entonces diremos que a<b si el entero b – a es un entero posi-

tivo; es decir:

a b b a 0 b a N∈–⇔>–⇔<


2. Divisibilidad

En este apartado estudiaremos la divisibilidad de números enteros, así como

sus propiedades más importantes y útiles para cálculos futuros.

2.1. La relación de divisibilidad

Ejemplo 1

Tenemos que 16 | 64, pero 16 50.

Ejemplo 2

El 0 no divide ningún entero: en efecto, si 0|b, entonces habría un único entero tal queb = 0 · x. Pero esto implicaría que b = 0, y entonces la ecuación 0 = 0 · x no tendría una únicasolución x. Por lo tanto, concluimos que 0 b, para todo entero b. Es decir, no se puede di-vidir por 0. Por lo tanto, en la definición anterior podemos excluir la posibilidad a = 0.

La proposición 1 refleja las propiedades elementales de la relación de divi-

sibilidad.

Demostración

1) Tenemos: a = 1 · a.

2) En efecto: 0 = a · 0.

Sean a, b ∈ Z números enteros. Diremos que a divide b si hay un único

entero x ∈ Z tal que ax = b. Es decir, si la ecuación ax = b tiene solución

entera única para x.

Proposición 1

1) 1 | a, para todo a ∈ Z.

2) a | 0, para todo a ∈ Z, a ≠ 0.

3) La relación de divisibilidad es reflexiva: a | a.

4) La relación de divisibilidad es transitiva: si a | b y b | c, entonces a | c.

5) Linealidad: si a | b y a | c, entonces a | bx + cy , para todo x, y ∈ Z.

Otras notaciones

Si a divide b, también diremos que a es un divisor de b o que b es un múltiplo de a o que b es divisible por a. Lo denotare-mos por a | b. Si a no divide b, escribiremos a b.|

|

|


3) Se satisface: a = a · 1.

4) Supongamos que a | b y que b | c. Esto quiere decir que hay enteros únicos

x e y tales que:

b = ax y c = by.

Si multiplicamos la primera igualdad por y, obtenemos:

c = by = axy, donde xy ∈ Z porque x e y ∈ Z.

Por lo tanto, a | c .

5) Supongamos que a | b y que a | c. Entonces tenemos enteros s y t tales que

verifican las condiciones siguientes:

b = as y c = at.

Si multiplicamos la primera igualdad por un entero x y la segunda por un en-

tero y y las sumamos, obtenemos:

bx + cy = asx + aty = a(sx + ty), donde sx + ty ∈ Z.

Por lo tanto, a | bx + cy .

Actividad

1. Demostrad de forma análoga a como lo acabamos de hacer las propiedades que presenta-mos a continuación:

a) Si a, b ∈ Z, entonces a | b ⇔ ±a | ±b.

b) Si a, b ∈ Z y a | b, entonces ac | bc, para todo c ≠ 0

c) Si a, b, c ∈ Z y ac | bc y c ≠ 0, entonces a | b.

d) Si a, b ∈ Z y a | b y b ≠ 0, entonces |a| ≤ |b|.

e) Si a, b ∈ Z y a | b y b | a, entonces |a| = |b|.

f) Si a, b ∈ Z y a | b, entonces

Teorema 1: teorema de la división entera

Si a ≥ 0 y b > 0 son enteros dados, entonces existen q y r, enteros únicos,

que satisfacen:

Los enteros q y r se llaman, respectivamente, el cociente y el residuo de

la división entera de a entre b.

ba--- b.

a bq r+= q 0≥ 0 r b .<≤


Demostración

1) Existencia de q y de r

Aplicaremos el principio de la buena ordenación en el conjunto:

Por lo tanto, necesitamos saber que S es un conjunto no vacío formado por

enteros positivos. Podremos deducir que S tiene un elemento mínimo (que

será el residuo r que buscamos).

Se satisfacen las siguientes propiedades:

a) S ≠ ∅, ya que a = a – b · 0 ∈ S y a ≥ 0.

b) Todo elemento de S es mayor o igual que 0 (por definición de S).

Por lo tanto, por el principio de la buena ordenación, S tiene un primer ele-

mento r ∈ S. Este elemento es de la forma:

para cierto entero q ≥ 0 . Debemos darnos cuenta de que, además, r < b. Si fuese

r ≥ b, entonces r – b ≥ 0 y, por lo tanto:

Como, además, q + 1 ≥ 0 porque q ≥ 0, tendríamos que r′ ∈ S. Pero es fácil ver

que, en esta situación, r′ < r (porque b > 0). Es decir, el conjunto S tendría un

elemento mayor o igual que 0 y menor que r y esto no es posible, ya que r es

el elemento mínimo de S. Tenemos demostrada, entonces, la existencia de en-

teros q y r tales que:

2) Unicidad de q y de r

Sean q′ y r′ dos enteros que satisfacen las condiciones del teorema. Entonces,

restando las siguientes igualdades:

obtenemos:

0 = b(q–q′)+(r–r ′), es decir, r′– r = b (q–q ′).

Puesto que r es el mínimo de S , resulta que r ≤ r′, y como, además, b>0, dedu-

cimos que q – q′ ≥0; pero r′–r ≤r′<b; por lo tanto, b (q–q′)<b y q–q ′<1. Sin embar-

go, 0≤q–q′≤1 y, por lo tanto, q = q′ y también r = r′.

S a bx: x 0, a bx 0 }.≥–≥–{=

r a bq 0≥–=

r′ r b– a bq– b– a b q 1 ) 0.≥+(–= = =

a bq r,+= q 0,≥ 0 r b .<≤

a bq r+= a bq′ r′+=


En el teorema anterior hemos supuesto que el entero b era positivo y el entero

a era positivo o nulo. Hay una versión de este teorema donde no es necesario

hacer estas hipótesis. La enunciamos en forma de corolario del teorema de la

división entera.

Ejemplo 3

• Si a = 741 y b = 15, tenemos q = 49 y r = 6:

741 = 15 · 49 + 6.

• Si a = 741 y b = –15, entonces:

741 = (−15) · (−49)+6.

• Si a = –741 y b = 15:

−741 = 15 · (−50)+9

• Si a = –741 y b = –15, obtenemos:

−741 = (−15) · 50 + 9

2.2. El máximo común divisor

En este subapartado estudiamos el concepto de máximo común divisor de un

conjunto finito de enteros, así como sus propiedades básicas.

Un número d es divisor común de un conjunto de enteros si d divide cada

elemento del conjunto.

Corolario 1

Sean a y b ≠ 0 enteros cualesquiera. Entonces hay unos enteros únicos

q y r tales que:

Sean a1, ..., an números enteros. Un número entero d es el máximo co-

mún divisor de los enteros a1, ..., an si, y sólo si, d satisface las propie-

dades siguientes:

1) d es un divisor común de los enteros a1, ..., an;

2) si d′ es un divisor común de estos enteros, entonces d′ divide a d;

3) d es estrictamente positivo.

Denotaremos como mcd(a1 ..., an) el máximo común divisor de los nú-

meros enteros a1, ..., a n.

a bq r+= 0 r b .<≤

Ejemplo 4

Los divisores comunes de los enteros 24 y 60 son ±1, ±2, ±3, ±4, ±6, ±12.

Ejemplo 5

El máximo común divisor de los enteros 24 y 60 es 12: mcd (24, 60) = 12.


Una definición básica que utilizaremos durante todo este módulo didáctico es

la de números primos entre sí.

De las definiciones anteriores se deducen los hechos siguientes:

1) El máximo común divisor de un conjunto finito de enteros es único.

En efecto, si d1 y d2 son dos posibles candidatos a máximo común divisor, en-

tonces, por la propia definición, d1 | d2 y también d2 | d1. Por lo tanto, según

la actividad 1, tenemos que |d1| = |d2| y, puesto que los dos son enteros positi-

vos, será d1 = d2.

2) Recordemos que si a | b, entonces ±a | ±b (observad la actividad 1). Es decir,

que un número entero divida otro no depende de los signos de los enteros in-

volucrados. Puesto que, además, el máximo común divisor es positivo, tene-

mos las igualdades siguientes:

mcd (a,b ) = mcd (−a,b) = mcd (a,−b) = mcd (−a,−b).

Por lo tanto, en el momento de calcular el máximo común divisor de dos o

más enteros podemos suponer, siempre que nos convenga, que los enteros son

positivos.

3) Si a y b ≠ 0 son enteros tales que b | a, entonces cualquier divisor de b tam-

bién lo será de a. Por lo tanto, los divisores comunes de los dos números son

los divisores de b y el máximo común divisor de a y de b es el valor absoluto

de b (recordemos que el máximo común divisor es positivo, por definición).

Resumiendo:

4) Si d = mcd(a,b ), entonces podemos escribir a = da′ y b = db ′ y los enteros a′

y b′ son primos entre sí.

En efecto, d es divisor común de a y de b. Además si d′ | a′ y d′ | b′, entonces dd′

sería un divisor común de a y de b y, por lo tanto, dd′ | d, ya que d es el máximo

común divisor. Sin embargo, entonces d′ = 1. De este modo, hemos demostrado:

d = mcd(a,b)⇒a = da ′, b = db′, y mcd(a′,b ′) = 1.

La propiedad que enunciamos y demostramos a continuación es la base de

todo el algoritmo de Euclides que estudiaremos en el subapartado siguiente.

Dos números enteros a y b son primos entre sí si, y sólo si, los únicos

divisores comunes de a y de b son ± 1. Es decir, si el máximo común di-

visor de a y b es 1.

Ejemplo 6

Los enteros 14 y −27 son primos entre sí; es decir: mcd (14, −27) = 1.

b 0, b a mcd a , b )(⇒≠ b .=


Demostración

Pongamos d1 = mcd(a,b) y d2 = mcd (b, a –b). Veremos que d1 | d2 y que d2 | d1.

Puesto que los dos son enteros positivos, deduciremos que d1 = d2.

• Veamos, en primer lugar, que d1 | d2:

Tenemos que d1 | a y d1 | b. Por lo tanto, por la propiedad de linealidad de la

proposición 1, d1 | a – b. Es decir, d1 | b y d1 | a – b y, como d2 = mcd (b, a – b),

concluimos que d1 | d2.

• Recíprocamente, tenemos que d2 | b y d2 | a – b. Por lo tanto, por la misma

propiedad mencionada anteriormente, tendremos que d2 | a. Es decir, d2 | a

y d2 | b y, por lo tanto, d2 | d1.

2.3. El algoritmo de Euclides

Para encontrar de forma efectiva el máximo común divisor de dos números

enteros, podemos aplicar la propiedad anterior, proposición 2, tantas veces

como sea necesario. De entrada, nos es posible suponer que los números a y b

son positivos y que a ≥ b. Entonces podemos restar de a el entero b tantas veces

como convenga, siempre que el resultado sea positivo. Por este motivo, es lo

mismo que efectuar la división entera de a entre b. Mediante el teorema de la

división entera, podemos encontrar enteros únicos q y r tales que:

Entonces, el máximo común divisor de a y b coincide con el máximo común

divisor de b y r. El algoritmo de Euclides consiste básicamente en repetir este

proceso hasta que encontremos una división exacta (es decir, una división con

residuo nulo).

Ejemplo 7

Encontremos el máximo común divisor de los enteros 62 y 24. Por la proposición 2 y las ob-servaciones que hemos hecho en el párrafo anterior, tenemos:

mcd (62,24) = mcd (24,62 − 2 · 24) = mcd (24,14)= mcd (14,24 − 1 · 14) = mcd (14,10)= mcd (10,14 −1 · 10) = mcd (10,4)= mcd (4,10 − 2 · 4) = mcd (4,2)= mcd (2,4 −2 · 2) = mcd (2,0)= 2 .

Proposición 2

Si a y b son enteros cualesquiera, entonces:

mcd (a,b) = mcd (b,a−b).

Euclides (s. IV -III aC)

Toda la gran obra de Euclides en geometría y aritmética ha sobrevivido al paso del tiempo.

a bq r,+= q 0,≥ 0 r b .<≤


Enunciamos a continuación el algoritmo de Euclides con precisión e, inmedia-

tamente después, una propiedad muy importante que satisface el máximo co-

mún divisor de dos números enteros, la identidad de Bézout.

Esta propiedad consiste en que el máximo común divisor de dos enteros se

puede escribir como combinación de los enteros en cuestión. Una versión am-

pliada del algoritmo de Euclides nos permitirá calcular al mismo tiempo el

máximo común divisor y los coeficientes de la combinación.

Una propiedad relacionada estrechamente con el algoritmo de Euclides es la si-

guiente (de hecho, las demostraciones respectivas se hacen simultáneamente).

Demostraciones simultáneas del algoritmo de Euclides y de la identidad

de Bézout

En primer lugar, observamos que en la aplicación del algoritmo de Euclides

siempre se obtiene un residuo nulo, ya que los residuos forman una sucesión

estrictamente decreciente de enteros mayores o iguales que cero.

Teorema 2: algoritmo de Euclides

Sean a ≥ 0 y b >0 números enteros. Aplicando el teorema de la división

entera sucesivas veces, obtenemos el esquema siguiente:

hasta que la división de un residuo entre el anterior sea exacta. En ese caso,

el máximo común divisor de a y b es el último residuo no nulo. Es decir:

mcd (a,b ) = mcd (b,r1) = mcd (r1,r2) = ... = mcd (rk+1) = rn.

Teorema 3: identidad de Bézout

Si a y b ∈ Z y d = mcd(a, b), entonces existen enteros x e y tales que:

d = ax + by.

Es decir, el máximo común divisor de dos números enteros es una com-

binación lineal con sus coeficientes enteros.

a bq1 r1,+= q1 0,≥ 0 r1 b<≤

b r1q2 r2 ,+= q2 0,≥ 0 r2 r1<≤

…

rn 2– rn 1– qn rn ,+= qn 0,≥ 0 rn rn 1–<≤

rn 1– rnqn 1+=


Sea rn el último residuo no nulo obtenido al aplicar el algoritmo de Euclides a

los enteros a≥0 y b>0. Queremos ver que rn = mcd (a,b) y que hay enteros x e

y tales que rn = ax + by . Para demostrar esto, aplicamos el principio de induc-

ción sobre el número de divisiones; es decir, consideramos la propiedad Pn si-

guiente: el residuo rn obtenido después de n divisiones satisface rn = mcd(a,b)

y hay x, y ∈ Z tales que rn = ax + by.

1) Veamos que la propiedad P0 es cierta:

2) Demos ahora el paso de la inducción. Supongamos que aplicando el algo-

ritmo de Euclides en a y b obtenemos, después de n + 1 pasos, un residuo nulo:

Si olvidamos la primera igualdad, podemos suponer que hemos aplicado el al-

goritmo en b y en r1, y hemos acabado en n pasos.

Por hipótesis de inducción, podemos concluir que:

rn+1 = mcd (b,r1)

y que existen x′ e y ′ ∈ Z:

Teniendo en cuenta todo esto y que r1=a – bq1, resulta:

y si hacemos x = y′ e y = x′ – q1y′, obtenemos la identidad de Bézout para a y b.

Veamos ahora que rn+1 = mcd(a,b). Como rn+1 = mcd(b,r1), resulta que rn+1|b, y

por lo tanto rn+1|bq1, y rn+1|r1. Por otro lado, puesto que r1 = a – bq1, tenemos

que rn+1|r1 + bq1 = a. Es decir, rn+1 es un divisor común de a y b. Finalmente, si

El principio de inducción

Para demostrar que una pro-piedad Pn es válida para todos los valores naturales de n, dare-mos dos pasos:

1. Verificar que P0 se cumple2. Demostrar que de la validez de Pn se deduce la de Pn+1.

a bq b a b⇒⇒ mcd a b,( )= =

b a 0 b 1.⋅+⋅=

a bq1 r1+=

b r1q 2 r2+=

…

rn 1– rnqn 1+ rn 1++=

rn rn 1+ qn 2+=

rn 1+ bx′ r1y ′+=

rn 1+ bx′ r1y′+ bx ′ a bq1–( )y ′+ ay ′ x′ q1y′–( )b+= = =


d es un divisor común positivo de a y b, entonces d divide r1 = a – bq1, y, por lo

tanto, d divide el máximo común divisor de b y r1, que es rn+1. Es decir, d = rn+1,

que es lo que queríamos demostrar.

Ejemplo 8

Calculemos, utilizando el algoritmo de Euclides, el mcd(858, 253) y determinemos los coefi-cientes de la identidad de Bézout correspondiente.

a) Primera división: dividimos 858 entre 253 y obtenemos lo siguiente:

858 = 253 · 3 + 99. (*)

Esta igualdad nos indica que

mcd (858,253) = mcd (253,99).

b) Segunda división: ahora dividimos 253 entre 99, el residuo anterior, y obtenemos:

253 = 99 · 2 + 55. (*)

Esto nos muestra que:

mcd (253,99) = mcd (99,55).

c) Tercera división: dividimos 99 entre 55 y obtenemos:

99 = 55 · 1 + 44. (*)

Por lo tanto, tenemos que

mcd (99,55) = mcd (55,44)

d) Cuarta división: dividimos 55 entre 44 y obtenemos:

55 = 44 · 1 + 11. (*)

Es decir,

mcd (55,44) = mcd (44,11).

e) Quinta división: dividimos 44 entre 11 y obtenemos:

44 = 11 · 4, (*)

y hemos acabado, ya que la división es exacta (tiene residuo nulo); por lo tanto, tenemos que

mcd (44,11) = mcd (11,0) = 11.

Así pues, según el algoritmo de Euclides, el máximo común divisor es 11, el último resi-duo no nulo:

mcd (858,253) = mcd (253,99) = mcd (99,55) = mcd (55,44) = mcd (44,11) = 11.

La identidad de Bézout consiste en expresar el máximo común divisor 11 a partir de 858 y253 como combinación lineal. Esto lo haremos en varios pasos:

• En el primer paso, expresaremos 11 en función de 55 y 44*.

• En el segundo paso, expresaremos 11 en función de 99 y 55.

• En el tercer paso, 11 nos debe quedar en función de 253 y 99.

• En el último paso, 11 quedará en función de 858 y 253.

Notad que todos estos pasos están indicados en las igualdades (*), miradas de derecha a iz-quierda. Para poder hacerlos, debemos aislar el residuo correspondiente a cada división quecompone el algoritmo de Euclides, pero empezando por la penúltima división y acabandopor la primera. Procediendo, encontramos lo siguiente:

* Mirad las igualdades señaladas con un asterisco y veréis de dónde

salen el 55 y el 44.


11 = 55 − 44 · 1 = 55 + (−1) · 44. (1)

44 = 99 + (−1) · 55. (2)

55 = 253 + (−2) · 99. (3)

99 = 858 + (−3) · 253. (4)

Notad que la igualdad (1) nos permite escribir el máximo común divisor 11 en funciónde 44 y 55. Con la ayuda de (2) escribiremos el máximo común divisor 11 en función de55 y 99, de la forma siguiente:

11 = (−1) · 44 + 55 = (−1) · (99 + (−1) · 55) + 55 = 2 · 55 + (−1) · 99.

Ahora, partiendo de la igualdad (3), escribiremos el máximo común divisor 11 en fun-ción de 99 y 253:

11 = 2 · 55 + (−1) · 99 = 2 · (253 + (−2) ·99) + (−1) · 99 = (−5) · 99 + 2 · 253.

Finalmente, mediante la igualdad (4) escribiremos el máximo común divisor 11 en fun-ción de 253 y 858:

11 = (−5) · 99 + 2 · 253 = (−5) · (858 + (−3) · 253) + 2 · 253 = 17 · 253 + (−5) · 858.

Hemos visto, entonces, lo siguiente:

11 = (−5) · 858 + 17 · 253.

Resulta práctico utilizar el esquema de la tabla adjunta para organizar los cálculos

de las divisiones sucesivas. Fijémonos que en cada paso del algoritmo dividimos el

divisor de la operación anterior entre el residuo de la misma división. Por lo tanto,

nos podemos ahorrar volverlos a copiar si ponemos los cocientes de las divisiones

(fila Q) sobre los divisores correspondientes (fila R). Es decir, en cada paso dividi-

mos el residuo rk (fila R) entre el residuo rk+1 de la división anterior, y obtenemos

el cociente qk+2 (fila Q) y el nuevo residuo rk+3; así hasta que obtenemos un residuo

nulo y hasta que el máximo común divisor de a y b sea el residuo anterior rn·

En el cuadro siguiente podemos ver la organización de los cálculos en la ob-

tención del mcd(a, b ) y de los coeficientes de la identidad de Bézout. El máxi-

mo común divisor es rn y rn = axn + byn·

2.4. El algoritmo de Euclides extendido

En la tabla presentada anteriormente vemos también dos filas adicionales, las fi-

las marcadas con una X y una Y. Los dos primeros valores de la fila X son siempre

x−1 = 1 y x0 = 0, y los dos primeros valores de la fila Y son siempre y−1 = 0 e y0 = 1.

Los otros valores se calculan de modo recurrente aplicando las fórmulas si-

guientes, si k ≥ 0:

X x−1=1 x0=0 x1 x2 ... xn−2 xn−1

Y y−1=0 y0=1 y1 y2 ... yn−2 yn−1

Q − q1 q2 q3 ... qn−1 qn qn+1

R a b r1 r2 ... rn−2 rn−1

r1 r2 r3 r4 ... 0

xn

yn

rn

rn


Se puede demostrar que los valores xn e yn del final son unos posibles coefi-

cientes para la identidad de Bézout. Es decir:

Recordemos que rn es el último residuo no nulo y, por lo tanto, el máximo co-

mún divisor de a y b.

Actividad

2. Demostrad, aplicando el principio de inducción sobre el entero n, que rn = axn + byn,donde xn e yn son los enteros que se obtienen por el algoritmo de Euclides extendido.

Ejemplo 9

Queremos calcular el mcd(4.999, 1.109) y escribir la identidad de Bézout. Para sistematizar latarea, utilizamos el esquema anterior.

El último residuo no nulo es el 1 del recuadro, que es también, por lo tanto, el máximocomún divisor de 4.999 y 1.109. Encontremos ahora dos enteros x e y tales que:

4.999x + 1.109y = 1.

Si aplicamos el algoritmo de Euclides extendido, encontramos x = 522 e y = –2.353. Tambiénpodemos encontrar estos coeficientes directamente a partir de las divisiones que hemos rea-lizado, escribiéndolas todas, como también hemos hecho en el ejemplo 8. Después aislamosde cada igualdad el residuo de la división, empezando por la última y yendo hacia atrás,como se muestra a continuación:

4.999 = 1.109 · 4 + 563

1.109 = 563 · 1 + 546

563 = 546 · 1 + 17

546= 17 · 32 + 2

17 = 2 · 8 +

Ahora tenemos:

= 17 − 2 · 8 = 17 − (546 − 17 · 32) · 8

= 546 · (−8) +17 · 257 = 546 · (−8) + 257 · (563 − 546)

= 546 · (−265) + 257 · 563 = (1.109 − 563) · (−265) + 257 · 563

= 1.109 · (−265) + 522 · 563 = 1.109 · (−265) + 522 · (4.999 − 1.109 · 4)

= 4.999 · 522 + 1.109 · (−2.353).

Por lo tanto, encontramos también que x = 522 e y = –2.353.

X 1 0 1 −1 2 −65

Y 0 1 −4 5 −9 293

Q – 4 1 1 32 8 2

R 4.999 1.109 563 546 17 2 1

563 546 17 2 0

xk 1+ xk 1– qk 1+ xk, –= x 1– 1,= x0 0=

yk 1+ y k 1– qk 1+ yk ,–= y 1– 0,= y0 1.=

rn axn byn .+=

522

−2.353

1

1

1


Ejemplo 10

Si aplicamos el esquema que acabamos de exponer en el ejemplo 8, obtenemos lo siguiente:

Es decir, el máximo común divisor es el último residuo no nulo, 11; además, encontra-mos los coeficientes de la identidad de Bézout:

11 = (−5) · 858 + 17 · 253.

A continuación, enunciamos una propiedad que nos será muy útil ocasional-

mente más adelante. La demostración es elemental, a partir de lo que ya he-

mos visto hasta ahora.

Demostración

La identidad de Bézout nos dice que existen enteros x, y ∈ Z tales que verifican

la condición siguiente:

ax + by = 1

Si multiplicamos por c la igualdad y tenemos en cuenta que a | bc, obtenemos

la igualdad siguiente:

2.5. El mínimo común múltiplo

El mínimo común múltiplo m de dos números enteros a y b se caracteriza, de

este modo, por las propiedades siguientes:

1) m>0;

X 1 0 1 −2 3

Y 0 1 −3 7 −10

Q – 3 2 1 1 4

R 858 253 99 55 44 11

99 55 44 0

Proposición 3: lema de Gauss

Si a, b, c son enteros tales que a | bc y mcd(a,b) = 1 (es decir, a y b son

primos entre sí), entonces a | c.

Sean a y b ∈ Z enteros positivos. Se denomina mínimo común múlti-

plo de a y b al número entero positivo mínimo que es al mismo tiempo

múltiplo de a y de b. Lo denotaremos por mcm (a,b ).

−5

17

11

a c acx bcy+=


2) a | m y b | m;

3) si a | r y b | r , entonces m | r.

Demostración

Podemos suponer, sin perder generalidad, que a ≥ 0 y b ≥ 0.

Sean d = mcd(a,b), m = ab/d>0 y pongamos que a = da′ y b = db′, con

mcd(a′ ,b′) = 1. Entonces:

y, por lo tanto, m = a′b = ab′, de donde b | m y a | m.

Sea ahora r un entero tal que a | r y b | r. Veremos que m | r: digamos r = ar1 = br2.

Entonces a′r1 = b′r2, de donde a′ | b′r2; y, como mcd(a′, b′) = 1, el lema de Gauss

nos asegura que a′ | r2. Si ponemos r2 = a′r3, tenemos:

y, por lo tanto, m | r. Así pues, m = mcm(a, b).

Ejemplo 11

Calculemos el mínimo común múltiplo de los enteros –60 y 24.

Si aplicamos la fórmula de la proposición anterior, obtenemos:

Proposición 4

Si a y b son enteros cualesquiera, entonces:

mcm a b,( ) abmcd a b,( )--------------------------=

dab ′ ab dm ab da′b= = = =

r b r2 a′br 3 m r3= = =

mcm 60– 24,( ) 60 24⋅–mcd 60– 24,( )------------------------------------- 1.440

12--------------- 120.= = =


3. Ecuaciones diofánticas

Algunos ejemplos de ecuaciones diofánticas serían los siguientes:

1) Una ecuación diofántica típica es la ecuación pitagórica :

de la que se conocen, desde Pitágoras y Platón, todas sus soluciones enteras

(las positivas dan los posibles triángulos rectángulos con lados enteros).

2) Una generalización de la ecuación pitagórica es la ecuación de Fermat:

Pierre de Fermat conjeturó en el siglo XVII que estas ecuaciones no tienen más

soluciones que las que se ven a primera vista, es decir, alguna incógnita nula.

Estas soluciones se denominan soluciones triviales. Desde entonces, muchos

matemáticos han investigado sobre esta cuestión y, finalmente, el matemático

Andrew Wiles demostró en el año 1996 que la conjetura de Fermat es cierta.

El caso más sencillo de ecuación diofántica que podemos considerar es la ecua-

ción de primer grado y una incógnita:

Está claro que la ecuación anterior tiene solución entera si, y sólo si, a divide

b (por definición) y, en tal caso, la solución es x = b/a ∈ Z.

Consideremos ahora una ecuación de primer grado con dos incógnitas:

La proposición siguiente estudia cuándo una de estas ecuaciones tiene solu-

ción, y da un método para calcularlas. Observemos que guarda un cierto pare-

cido con el espíritu de la identidad de Bézout.

Una ecuación diofántica es una ecuación polinómica con coeficientes

enteros de la que nos interesa conocer las soluciones enteras.

El término de ecuación diofántica...

... proviene del matemático griego Diofante de Alejandría (250 a. C.), que publicó trece libros, de los cuales sólo se conservan seis, dedicados a la teoría de los números y las ecuaciones.

x 2 y2+ z2 ,= x,y ,z Z∈

xn yn+ zn,= x, y , z Z,∈ n 3.≥

ax b ,= a, b Z.∈

ax by+ c ,= a b c Z.∈, ,


Demostración

⇒) Supongamos que la ecuación ax + by = c tiene una solución entera (x0, y0).

Es decir:

Por la propiedad de linealidad de la divisibilidad (ved la proposición 1), tene-

mos que d = mcd(a, b) divide ax0 + by0 = c.

⇐) Recíprocamente, supongamos que d divide c y pongamos c = dc′. Por la

identidad de Bézout, hay enteros x0 e y0 tales que:

Si multiplicamos esta igualdad por c ′, obtenemos:

es decir, la ecuación tiene la solución (x0c ′,y0 c′).

Supongamos ahora que la ecuación lineal ax + by = c tiene soluciones enteras

y, por lo tanto (según el apartado anterior), que d | c. Veamos cómo son todas

las soluciones. Sean (x0,y0) y (x1,y1) dos soluciones de la ecuación, es decir:

Proposición 5

La ecuación ax + by = c, con a, b, c ∈ Z, tiene alguna solución (x0,y0) ∈

Z × Z si, y sólo si, d = mcd (a,b) | c.

En caso de que sea así, la ecuación tiene un número infinito de solucio-

nes y éstas son de la forma:

donde a′ = a/d, b′ = b/d y t ∈ Z es un entero arbitrario.

x x0 b ′t–=

y y0 a ′t+=

ax0 by 0+ c.=

ax0 by 0+ d.=

ax0c ′ by 0c ′+ d c′ c,= =

ax0 by 0+ c=

ax1 by 1+ c.=


Si restamos ambas igualdades, obtenemos:

Ponemos a = da′ y b = db′ con mcd (a′,b′) = 1. Si dividimos la igualdad anterior

por el máximo común divisor de a y b, obtenemos:

(1)

Por esto mismo deducimos, por ejemplo, que a′ divide b′(y1 – y0). Puesto que

a′ y b′ son primos entre sí, podemos aplicar el lema de Gauss y obtendremos

que a′ | (y1–y0). Es decir, podemos escribir:

para cierto entero t. Si sustituimos esta igualdad en la igualdad (1) y aislamos

x1, obtenemos:

Ejemplo 12

Encontremos las soluciones enteras, si las hay, de la ecuación siguiente:

En primer lugar, calculemos el máximo común divisor de los coeficientes 93 y –81. Elresultado es mcd(93, 81) = 3, que divide 15. Por lo tanto, la ecuación tiene solucionesenteras. Para encontrarlas todas, debemos hallar primero una solución particular cual-quiera, y la identidad de Bézout nos la puede proporcionar. Apreciad en la tabla los cál-culos que hemos seguido para encontrar el máximo común divisor y los coeficientes dela identidad siguiente:

Así pues, una solución particular de la ecuación que estamos estudiando es x0 = 7 · 5 = 35 ey0 = 8 · 5 = 40. La solución general es de la forma:

donde t es un entero cualquiera.

X 1 0 1 −6 7

Y 0 1 −1 7 −8

Q – 1 6 1 3

R 93 81 12 9 3

12 9 3 0

a x0 x1–( ) b y0 y1–( )+ 0=

a ′ x0 x1–( ) b′ y0 y1–( )+ 0=

y1 y0 a′t+=

x1 x0 b′t.–=

93x 81y– 15.=

3 93 7 81 8–( )⋅+⋅ 93 7 81 8.⋅–⋅= =

x 35 81 3⁄–( ) t– 35 27 t.+= =

y 40 93 3⁄( )t+ 40 31 t .+= =


4. Números primos y factorización de enteros

A continuación estudiaremos el concepto de número primo y probaremos el

resultado principal de este apartado, el llamado teorema fundamental de la arit-

mética o teorema de la factorización única : cualquier número entero mayor que

1 se puede escribir, esencialmente, de forma única, como producto de núme-

ros primos.

Observad que con esta distinción excluimos explícitamente de la definición

de número primo el 1 y el –1.

Demostración

Aplicaremos el principio de inducción sobre el número natural n>1.

1) Si n = 2, es obvio, ya que 2 es un número primo.

2) Supongamos que la propiedad es cierta para todo entero menor que un

cierto entero fijo m.

a) Si m es primo, ya hemos acabado.

b) Si m no es primo, entonces m tiene un divisor d diferente de 1 y de m (por

definición de número primo). Es decir, m = dd′, pero entonces d′≠ 1 y d′ ≠ m.

Por lo tanto, d<m, d ′<m y, por hipótesis de inducción, tanto d como d′ son pri-

mos o son productos de primos.

En cualquier caso, acabamos de demostrar que m es producto de primos.

Un número entero p ≠ ± 1 es primo si, y sólo si, los únicos divisores de

p son ±1 y ± p.

Un número entero es compuesto si no es primo.

Proposición 6

Todo número entero n>1 o es un número primo o bien es producto de

números primos.


Antes de enunciar y demostrar el teorema fundamental, recordaremos el lema

de Gauss en una versión más adecuada para nuestros propósitos actuales.

Demostración

Podemos suponer que todos los enteros involucrados son positivos.

1) Si p | a , ya hemos acabado.

2) Supongamos que p a y calculemos d = mcd (p, a ). Este máximo común

divisor es un divisor positivo de p. Por lo tanto, d = 1 o d = p . Pero no puede

ser d = p , ya que estamos suponiendo que p a. Por lo tanto, d = 1. Ahora,

aplicando la primera versión del lema de Gauss (proposición 3), obtenemos

que p | b.

Demostración

Sólo debemos demostrar la unicidad de la factorización, ya que la existencia

está demostrada en la proposición anterior. Demostraremos la unicidad por el

principio de inducción aplicado al entero n.

1) Si n = 2, la propiedad es cierta; es decir, el 2 factoriza de forma única como

producto de primos, ya que es un número primo.

2) Supongamos, entonces, que la propiedad es cierta para todos los enteros

positivos menores que un entero dado m>2 y supongamos que tenemos dos

factorizaciones de m como producto de primos positivos:

Queremos encontrar que son la misma factorización; es decir, que hay el mis-

mo número de primos, t = r, y que si los ordenamos por orden creciente, en-

tonces pi = qi.

Si un primo divide un producto de enteros, entonces el primo debe di-

vidir algún factor. Concretamente, si p es un primo y a y b son enteros

tales que p | ab, entonces p | a o p | b .

Teorema 4: teorema fundamental de la aritmética

Todo entero n ≥ 2 factoriza como producto de primos. Esta factorización

es única, excepto el orden en el que escribimos los primos.

|

|

m p1p2 … pt⋅ ⋅ q1q2 … qr .⋅ ⋅= =


Consideremos el número primo p1. Puesto que p1 divide el segundo miembro,

por el lema de Gauss que acabamos de demostrar, tenemos que p1 debe dividir

algún primo de este segundo miembro. Supongamos que este primo es q1 (los

renumeramos si es necesario): p1 | q1. Pero si un primo divide otro primo (los

dos positivos), entonces los primos son iguales. Por lo tanto, p1 = q1 y, por la

ley de cancelación de los enteros, tenemos:

Ahora podemos aplicar la hipótesis de inducción y deducimos que t = r y que

pi = q i (renumerándolos si es necesario).

Sea n>1 un entero. Si agrupamos los primos iguales de la descomposición de n

como producto de primos, podremos escribir:

donde pi son primos diferentes y los e i>0, para i = 1, ..., t. Esta forma de escribir

los enteros se denomina notación exponencial. Con los enteros escritos con

esta notación exponencial es muy fácil calcular los divisores de un entero y,

por lo tanto, el máximo común divisor y el mínimo común múltiplo de dos

enteros:

1) para calcular el máximo común divisor, se toman los primos comunes de

las dos descomposiciones elevados al menor exponente.

2) En lo que respecta al mínimo común múltiplo, se calcula tomando to-

dos los primos de las dos descomposiciones, elevado cada uno al máximo

exponente.

Actividad

3. Proporcionad la expresión del máximo común divisor y del mínimo común múltiplode dos números enteros en función de las factorizaciones como producto de primos delos enteros en cuestión.

Veamos a continuación cómo podemos calcular el número de divisores de un

entero.

¿Cómo son los divisores positivos del entero n? Un divisor d se descompone

de la siguiente forma:

donde los pi son los primos que aparecen en la descomposición del entero en

producto de primos y los exponentes f i satisfacen 0 ≤ fi ≤ e i. De aquí podemos

p2 … pt⋅ ⋅ q 2 … qr.⋅ ⋅=

Ejemplo 13

La descomposición en primos de 60 es 22 · 3 · 5.

n p1e1p2

e2 … ptet⋅ ⋅=

d p1f1p2

f2 ptft⋅=


deducir una fórmula para el número de divisores positivos de un entero (el nú-

mero total de divisores será el doble).

Acabamos este subapartado probando que hay infinitos números primos,

resultado que ya era conocido por los matemáticos griegos hace unos vein-

te siglos, y dando un método simple para calcular todos los números pri-

mos menores que un entero dado: este método recibe el nombre de criba de

Eratóstenes.

Demostración

Haremos una demostración por reducción al absurdo. Supongamos que sólo

hay una cantidad finita de números primos (postivos), p1, p2, ..., pn. Conside-

remos entonces el siguiente número entero:

Observad, en primer lugar, que el residuo de dividir Q entre cualquiera de los

primos pi es 1 (podéis comprobarlo efectuando la división). Es decir, Q , no es

divisible por ninguno de los primos pi. Por otro lado, el teorema fundamental

o de la factorización única asegura que Q descompone como producto de pri-

mos. Pero acabamos de ver que estos primos no son los pi. Por lo tanto, Q debe

ser un primo diferente de los que ya teníamos, y esto entra en contradicción

con lo que habíamos supuesto.

Una forma muy simple de ver si un entero es primo o no consiste en dividir el

entero en cuestión entre todos los enteros anteriores (de hecho, sólo es nece-

sario tomar los enteros anteriores que sean primos). Si ninguna de estas divi-

siones es exacta, entonces el entero es primo. El resultado siguiente dice que,

en este proceso de hacer divisiones, es necesario llegar sólo hasta la raíz cua-

Proposición 7

El número de divisores positivos de un entero n>1, cuya descomposi-

ción viene dada por , es:

Teorema 5: teorema de Euclides

Existen infinitos números primos

n p 1e1p2

e2 … pte t⋅=

e i 1+( )i 1=

t

∏

Reducción al absurdo

Una forma elegante y lógica de verificar la validez de una pro-posición es suponer que ésta no es válida y comprobar que esto nos llevaría a una contra-dicción con las hipótesis de partida.

Q p1p2 … pn 1+⋅ ⋅=


drada del entero, ya que, si el entero es compuesto, siempre hay un factor pri-

mo de este entero menor o igual que su raíz cuadrada. Este resultado lo

usaremos después en la criba de Eratóstenes.

Demostración

Sea n un entero compuesto. Podemos escribir n = ab , con 1<a≤b<n. Entonces

forzosamente tenemos que o , ya que en caso contrario, es decir,

si y , tendríamos que . Ahora bien, cual-

quier factor primo de n debe ser un divisor de a o de b. Por lo tanto, ya hemos

demostrado lo que queríamos.

Sea N un entero positivo dado. Queremos encontrar todos los números primos

(positivos) menores o iguales que N. El algoritmo que describimos a continua-

ción, conocido por el nombre criba de Eratóstenes, da como resultado el con-

junto de todos estos primos.

Escribimos la lista de todos los enteros entre 2 y N (recordemos que 1 no es

primo, por definición) de la que iremos tachando enteros, precisamente los

compuestos o no primos. En cada fase, el primer número entero de la lista no

tachado es un número primo. En este caso, el primer número entero no tacha-

do es el 2, que es un primo. Ahora vayamos tachando los enteros de dos en

dos (es decir, tachemos los múltiplos de 2). El siguiente número entero no ta-

chado es el 3, que también es primo. Ahora tachamos los enteros de tres en

tres (es decir, tachamos los múltiplos de 3). Y así hasta que lleguemos a la raíz

cuadrada de N, según la proposición anterior. Es decir, cuando lleguemos a

dejamos de tachar y los números que no queden tachados son todos los

números primos menores o iguales que N.

Ilustraremos este proceso para N = 100. En primer lugar, no es necesario escri-

bir los pares, ya que sabemos de entrada que sólo el 2 es primo. Escribimos, de

este modo, sólo los enteros impares menores que 100.

Proposición 8

Todo entero compuesto n tiene un factor primo menor o igual que .n

a n≤ b n≤

a n> b n> n ab n n⋅> n= =

N

Aplicación en los códigos secretos

Multiplicar dos primos grandes es muy fácil. Escribir un núme-ro grande como producto de primos es largo y complicado. Muchos códigos secretos han utilizado este principio.

3 5 7 9 11 13 15 17 19 21

23 25 27 29 31 33 35 37 39 41

43 45 47 49 51 53 55 57 59 61

63 65 67 69 71 73 75 77 79 81

83 85 87 89 91 93 95 97 99


5. Congruencias de números enteros

En este apartado estudiaremos una nueva relación: la congruencia de números

enteros.

5.1. La relación de congruencia

En este subapartado introduciremos el concepto de congruencia de núme-

ros enteros, clave en la aritmética y debido al matemático alemán Karl F.

Gauss. Es, al mismo tiempo, una notación clara que recuerda la relación de

igualdad y, de hecho, como veremos, comparte con la igualdad muchas de

sus propiedades.

De este modo, tenemos:

y, si a y b son enteros positivos, todo esto equivale a decir que a y b dan el mis-

mo residuo cuando los dividimos por m.

Ejemplo 14

a) Tenemos los ejemplos siguientes de congruencias:

b) Si a y b son enteros cualesquiera, entonces:

Por lo tanto, la relación de congruencia módulo 1 no es demasiado interesante: cualquier pa-reja de enteros es congruente módulo 1.

c) Un entero n es par si, y sólo si, n ≡ 0 (mod 2)

d) Un entero n es impar si, y sólo si, n ≡ 1 (mod 2).

Sea m un entero positivo. Diremos que dos enteros a y b son congruen-

tes módulo m si la diferencia a – b es múltiplo de m o, de forma equi-

valente, si m divide la diferencia a – b. Lo denotaremos así:

Karl F. Gauss (1777-1855)

Una vez más, como en tantos otros temas en las relaciones de congruencia, el llamado “príncipe de las matemáticas” fue quien puso las bases.

a b (mod m )≡

a b (mod m ) m b a–( ) k∃ Z:b∈⇔⇒≡ a km+=

19 7 (mod 12); 1 1 (mod 2); 32 1 (mod 5).–≡–≡≡

a b (mod 1).≡


Demostración

1) En efecto, m | 0 = a – a.

2) Efectivamente, si m | (a – b), entonces m | (b–a).

3) Supongamos que m | (a–b) y que m | (b–c). Entonces m divide la suma de

los dos números, es decir, m | (a – c).

Estudiemos a continuación otras propiedades interesantes de la relación de

congruencia, que podríamos enmarcar dentro de un álgebra de congruencias,

y que utilizaremos más adelante.

Demostración

1) Tenemos como hipótesis que m divide los números a – b y a′ – b′. Por lo

tanto, también divide su suma:

Es decir, (a + a′) ≡ (b + b′) (mod m).

Proposición 9

Sea m un entero positivo. La relación de congruencia módulo m es

una relación de equivalencia en el conjunto de los enteros. Es decir,

se satisfacen las propiedades siguientes, donde a, b y c son enteros

cualesquiera:

1) Propiedad reflexiva: a ≡ a (mod m).

2) Propiedad simétrica: si a ≡ b (mod m), entonces b ≡ a (mod m).

3) Propiedad transitiva: si a ≡ b (mod m) y b ≡ c (mod m), entonces

a ≡ c (mod m).

Proposición 10

Las congruencias módulo m se pueden sumar y multiplicar término a

término. Concretamente, si a ≡ b (mod m) y a′ ≡ b′ (mod m), entonces

se verifican las siguientes condiciones:

1)

2)

a a+( )′ b b ′+( ) mod m( ).≡

aa′ bb ′ (mod m )≡

m a b )– a ′ b′ )–(+( a a ′+( ) b b ′+( ).–=


2) Por otro lado, tenemos (sumando y restando ba′):

y puesto que a′– b′ y a – b son múltiplos de m, la diferencia aa′ – bb′ también lo es.

En general, las congruencias no se pueden simplificar; es decir, un factor co-

mún en los dos miembros de una congruencia no siempre se puede eliminar;

de este modo, podemos decir que:

Por ejemplo:

, pero 12 18 (mod 10). La forma correcta de simplifi-

car un factor común en una congruencia, si es posible, se explica en la propo-

sición siguiente:

Actividad

4. Probad las propiedades siguientes:

a) Si a, b, k ∈ Z y k ≠ 0, entonces:

a ≡ b (mod m) ⇔ ak ≡ bk (mod mk).

b) Si a ≡ b (mod m) y d | m, entonces a ≡ b (mod d).

c) Si a ≡ b (mod r) y a ≡ b (mod s), entonces a ≡ b (mod m ), donde m = mcm (r, s ).

Todavía en relación con la cuestión de la simplificación de congruencias, da-

mos el resultado siguiente, que dice cuándo podemos resolver una ecuación

en congruencias de primer grado y una incógnita.

ra ≡ rb (mod m) no implica que a ≡ b (mod m).

Proposición 11: simplificación de congruencias

Sea m > 1 un entero. Si a, b, r ∈ Z y d = mcd (m,r), entonces:

Por lo tanto, podemos eliminar un factor común en una congruencia si,

además, dividimos el módulo de la congruencia por el máximo común

divisor del factor eliminado y el módulo de la congruencia original.

Proposición 12

La ecuación en congruencias ax ≡ b (mod m) tiene solución entera x si,

y sólo si, sólo si mcd (a, m) | b.

aa′ bb′– aa′ bb ′– ba ′– ba ′+ b a ′ b ′–( ) a′ a b–( )+= =

5 12 5 18 (mod 10).⋅≡⋅ ≡

ra rb (mod m ) a b (mod m d⁄ ).≡⇔≡

Podéis intentar hacer vosotros mismos la demostración de la proposición 12.


5.2. Clases de congruencias

En el subapartado anterior hemos visto que la relación de congruencia módu-

lo un entero positivo m es una relación de equivalencia en el conjunto de los

números enteros Z. Por lo tanto, los números enteros quedan clasificados au-

tomáticamente en clases de equivalencia, que en este contexto reciben el

nombre de clases de congruencia módulo m.

Cada entero a determina una clase de congruencia que escribimos a. Recorde-

mos del módulo didáctico “Teoría de conjuntos” que la clase de un elemento

a se define como el conjunto de los elementos que están relacionados con él.

En nuestro caso:

Informalmente, decimos que los elementos de la clase del entero a son los de la

forma a + mk, con k un entero cualquiera. Recordemos también que cualquier ele-

mento de una clase la determina. Es decir, si a ≡ b (mod m), entonces a = b.

Denotamos como Zm el conjunto cociente de Z por la relación de congruencia

módulo m. Recordemos que los elementos de un conjunto cociente por una rela-

ción de equivalencia son precisamente las clases de equivalencia. En este contex-

to, el conjunto Zm está formado por las clases de congruencia módulo m:

Ejemplo 15

Determinemos las clases de congruencia módulo 4. Empecemos con la clase del 0:

Es decir, la clase del 0 está formada por los enteros múltiplos de 4. Por las propiedadesde las clases de equivalencia, dos enteros congruentes módulo 4 determinan la mismaclase. Por lo tanto, la clase de cualquier múltiplo de 4 coincide con la clase del 0 por-que son congruentes módulo 4 (está relacionados). Por ejemplo, 4 = 0 = –24 .

Tomemos ahora un entero que no sea múltiplo de 4; por ejemplo, el 1:

Es decir, 1 está formada por los enteros que se obtienen sumando 1 a un múltiplo de 4. Igualque antes, tenemos, por ejemplo: 1 = –3 = –7.

Finalmente, hay dos clases más, que son 2 y 3, formadas por los enteros de la forma 2 + 4k y3 + 4k′, respectivamente (el cálculo explícito lo podéis hacer vosotros mismos).

En total, hay 4 clases de congruencia módulo 4 que se corresponden con los posibles residuosde dividir un entero entre 4. Es decir:

En general, se verifica la siguiente proposición:

a x Z : x a (mod m ) }≡∈{ x Z : k Z, ∈∃ x∈{ a mk }+= = =

Zm a : a Z } .∈{=

0 x : x 0 (mod 4)}≡{ 4k : k Z }∈{ 0, 4, 8, ...} .±±{= = =

1 x : x 1 (mod 4)}≡{ 4k 1 : k Z}∈+{ 1, -3, 5, -7, ...} .{= = =

Z 4 0 1 2 3} ., , ,{=


Demostración

Hemos visto que los elementos de la clase de entero a son los enteros de la for-

ma a + km, donde k es un entero arbitrario. No es difícil demostrar que entre

los enteros de esta forma sólo hay uno que, además, está entre 0 y m – 1 (pro-

bad esto). Es decir, cada clase tiene un único elemento (también se le llama

representante) positivo entre 0 y m – 1. Sin embargo, dos enteros diferentes

que estén en este rango no pueden ser congruentes módulo m, ya que su dife-

rencia es menor que m y un entero positivo menor que m no puede ser múlti-

plo de m. Por lo tanto, hay tantas clases de módulo m como enteros entre 0 y

m – 1, que es lo que queríamos demostrar.

Hemos visto que en cada clase de congruencia hay un único representante posi-

tivo entre 0 y m – 1. Por lo tanto, si queremos un conjunto de enteros que repre-

senten todas las clases de módulo m, podemos tomar los enteros 0, 1, ..., m – 1.

Por ejemplo, los enteros del 0 al 4 representan todas las clases módulo 5. Sin em-

bargo, también podemos tomar otros sistemas de representantes. Por ejemplo, los

enteros –5, 1, 12, –12 y el –1 también representan todas las clases módulo 5.

Ejemplo 16

El conjunto S = {1, 8, –3, –8, 5, 0} es un sistema completo de representantes módulo 6. Enefecto, las clases de los elementos de S son 1, 8 = 2, –3 = 3, –8 = 4, 5, 0 = 6, respectivamente.

Proposición 13

El conjunto cociente Zm contiene m clases de congruencia. Concreta-

mente, tenemos:

Un sistema completo de representantes módulo m es un conjunto S

de m enteros tal que cualquier otro entero es congruente con un entero

de S exactamente.

Zm 0, 1, … , m 1– }{=


6. Anillos de enteros modulares

En este apartado veremos cómo podemos operar con las clases de congruencia

de enteros.

6.1. Operaciones con clases

Habíamos visto en la proposición 10 que las congruencias módulo un en-

tero fijo se pueden sumar y multiplicar término a término. Estas propieda-

des nos permiten definir una suma y un producto de clases de congruencia

módulo m.

Imaginemos que queremos definir una suma de clases módulo m: digamos

que queremos sumar las clases a y b. La forma más natural de definir esta suma

consiste en elegir representantes de cada clase, por ejemplo, a de la clase a y b

de la clase b, sumar estos representantes a y b y tomar la clase del resultado; es

decir, estamos definiendo la suma de clases como a + b = a + b. Pero aquí nos

encontramos con un problema potencial subyacente. Por ejemplo, si quere-

mos sumar las clases 2 y 1 módulo 5, podemos tomar como representantes el

2 y el 1 y definir la suma como la clase del 3, o bien podemos tomar como

representantes de las mismas clases los enteros 7 y –9 (ya que 7 = 2 y 1 = –9)

y tomar como resultado de la suma de clases la clase del –2. Los resultados nu-

méricos de sumar los enteros no son los mismos, 3 ≠ –2, pero, afortunadamen-

te, sus clases módulo 5 son iguales.

El problema de qué representante de cada clase debemos elegir para hacer las

operaciones nos lo resuelve la siguiente proposición.

Sea m ≥ 2 un entero. Definimos la suma y el producto de clases módu-

lo m mediante las fórmulas siguientes:

1) .

2)

Proposición 14

Las operaciones anteriores están bien definidas en el conjunto cociente

Zm. Es decir, la suma y el producto de clases no dependen de los repre-

sentantes que tomemos. Por lo tanto, las fórmulas anteriores definen

unas operaciones binarias en el conjunto de enteros modulares Zm.

a b+ a b+=

a b⋅ ab=


Gracias a este hecho, y recordando las definiciones dadas en el módulo didác-

tico “Teoría de conjuntos”, podemos enunciar otro teorema.

Actividad

5. Elaborad la demostración del teorema 6 vosotros mismos con un poco de paciencia.

Ejemplo 17

Hagamos las tablas de la suma y el producto del anillo (Z6 , +, ·) y comprobemos que este ani-

llo no es un cuerpo (recordemos que un cuerpo es un anillo tal que todo elemento no nulo

tiene un inverso respecto del producto).

Para simplificar las notaciones, escribiremos la clase de a módulo 6 como “a” simplemente.

Observemos que la clase 2 no tiene inverso respecto del producto. Es decir, no hay

ninguna clase x ∈ Z6 tal que 2x = 1 o, equivalentemente, la congruencia 2x ≡ 1 (mod

6) no tiene solución entera (en efecto, el mcd(2,6) = 2, que no divide el término in-

dependiente, 1). La clase 3 tampoco tiene inverso. Por lo tanto, el anillo Z6 no es un

cuerpo.

6.2. Clases invertibles

En el subapartado anterior hemos definido una suma y un producto de clases

en el conjunto Zm de enteros módulo m y hemos demostrado que, con estas

operaciones, este conjunto es un anillo conmutativo y unitario. En general,

como puede verse en el ejemplo 15, los anillos de enteros modulares Zm no

son cuerpos. Es decir, no siempre tenemos inversos respecto del producto. En

este subapartado estudiaremos qué elementos tienen un inverso respecto del

producto y veremos cuándo un anillo de enteros modulares es un cuerpo y

cuándo no lo es.

Teorema 6

Las dos operaciones binarias internas definidas en Zm hacen de este

conjunto un anillo conmutativo con unidad.

La terna (Zm, +, ·) recibe el nombre de anillo de enteros modulares

módulo m.

+ 0 1 2 3 4 5 · 0 1 2 3 4 5

0 0 1 2 3 4 5 0 0 0 0 0 0 0

1 1 2 3 4 5 0 1 0 1 2 3 4 5

2 2 3 4 5 0 1 2 0 2 4 0 2 4

3 3 4 5 0 1 2 3 0 3 0 3 0 3

4 4 5 0 1 2 3 4 0 4 2 0 4 2

5 5 0 1 2 3 4 5 0 5 4 3 2 1


La proposición siguiente nos permitirá calcular las clases invertibles de Zm.

Por lo tanto, podemos deducir lo siguiente:

Por ejemplo, Z*6 = {1, 5}.

En el caso de que una clase sea invertible, su clase inversa se puede calcular apli-

cando el algoritmo de Euclides extendido. Veámoslo en el ejemplo siguiente.

Ejemplo 18

Calculemos el inverso del 6 módulo 13.

• En primer lugar, comprobemos que la clase 6 tiene inverso módulo 13: el mcd (6,13) es 1 y, por lo tanto, tiene inverso.

• Para encontrar este inverso tenemos que calcular las soluciones de la congruencia6x ≡ 1 (mod 13).

Recordemos que esto equivale a resolver la ecuación diofántica:

Si aplicamos el algoritmo de Euclides extendido, obtenemos la solución:

(aunque en este ejemplo, podemos encontrarla a ojo). Si ahora reducimos módulo13, obtenemos:

Por lo tanto, 6−1 = –2 = 11.

Ahora estamos en condiciones de decir cuándo un anillo de enteros modulares

Zm es un cuerpo: para que Zm sea un cuerpo se debe cumplir, por definición

de cuerpo, que todo elemento no nulo tenga un inverso respecto del producto.

El teorema siguiente da la condición que se debe satisfacer.

Una clase a ∈ Zm es un elemento invertible (respecto del producto) si

tiene un inverso, es decir, si hay una clase b tal que a · b = 1. Denotare-

mos como Z*m el conjunto de los elementos invertibles de Zm. Si una

clase a es invertible, su clase inversa es única. La denotaremos por a−1.

Proposición 15

Una clase a ∈ Zm es invertible (es decir, a ∈ Z*m) si, y sólo si, mcd (a,m) =1. Si seguís las definiciones, podéis

desarrollar la demostración de la proposición 15.

Zm* x Zm : mcd (x , m )∈{ 1 } .= =

6x 13y+ 1=

6 2–( ) 13 1⋅+⋅ 1=

6 2–( ) 1 (mod 13)≡⋅


Demostración

⇒) Supongamos que Zm es un cuerpo. Esto quiere decir que si x ≠ 0, entonces

x tiene inverso. Podemos suponer que el representante x está entre 0 y m – 1.

Entonces, la condición anterior equivale a decir que, si x no es múltiplo de m

y 1 ≤ x ≤ m, entonces mcd(x,m) = 1.

Es decir, todo entero entre 1 y m – 1 es primo con m. Si m no fuese primo,

tendría un factor primo entre 1 y m – 1 y, por lo tanto, habría un entero

entre 1 y m – 1 que no sería primo con m. Consecuentemente, m debe ser

un número primo.

⇐) Recíprocamente, supongamos que m es un número primo. Entonces

ningún entero entre 1 y m – 1 tiene un factor en común con m; es decir,

todo entero x entre 1 y m – 1 satisface mcd(x,m) = 1. Por lo tanto, toda

clase x diferente de la clase 0 tiene un inverso en Zm ; es decir, Zm es un

cuerpo.

6.3. La función de Euler

En este subapartado estudiamos la llamada función de Euler, una función

definida para los enteros positivos y que toma valores enteros positivos. La

función de Euler está relacionada, como veremos, con el cardinal del con-

junto de los elementos invertibles de los anillos modulares que acabamos

de estudiar.

Recordando que Z*m = {x ∈ Zm: mcd (x, m) = 1}, tenemos la igualdad siguiente.

Teorema 7

El anillo Zm es un cuerpo si, y sólo si, el entero m es un número primo.

Sea m ≥ 1 un entero positivo. Definamos la función φ de Euler como

sigue: φ(1) = 1 y φ(m) es el número de enteros positivos menores que m

y primos con m. Es decir, si m>1:

φ(m) = # {x∈Zm: 1 ≤ x ≤ m, mcd (x, m) = 1}

Proposición 16

Se cumple: #Z*m = φ(m).

Recordemos

Si p es un número primo, en-tonces el conjunto Zp es un cuerpo. Estos cuerpos son los ejemplos más básicos de los cuerpos finitos: es decir, cuer-pos con un número finito de elementos.


Demostración

En efecto, ya hemos visto que los elementos invertibles de Zm son las clases de

los enteros x módulo m tales que mcd(x, m) = 1. Como cada clase tiene un úni-

co representante que está entre 1 y m – 1, resulta que hay tantas clases inver-

tibles como φ(m).

Ejemplo 19

Calculemos los valores de φ(m), para m desde 1 hasta 10.

Debemos calcular en cada caso cuántos enteros positivos hay entre 1 y m que sean primoscon m. Por ejemplo, φ(2) = 1 porque sólo el 1 es primo con 2 y φ(4) = 2 porque sólo los enteros1 y 3 son primos con 4. En lo que respecta a los demás, tenemos la tabla siguiente:

Hemos introducido el concepto de sistema completo de representantes módu-

lo un entero m. Recordemos que se trata de un conjunto de m enteros no con-

gruentes entre sí tales que cualquier otro entero es congruente exactamente

con un entero del sistema (es decir, elegimos un representante de cada clase

de congruencia módulo m). En ocasiones nos interesa un sistema de represen-

tantes de aquellas clases que son invertibles.

La proposición anterior asegura que hay φ(m) elementos en un sistema redu-

cido de representantes módulo m.

Ejemplo 20

Tomemos m = 8. Un sistema completo de representantes módulo 8 es, por ejemplo, elconjunto:

Scompleto = {0, 1, 2, 3, 4, 5, 6, 7}

y un sistema reducido de representantes módulo 8 podría ser el siguiente:

Sreducido = {1, 3, 5, 7}.

Es decir, un sistema reducido de representantes módulo 8 contiene representantes decada clase invertible de Z*

8. Estas clases pueden estar representadas por los enteros entre1 y 8 que son primos con 8; es decir, los enteros impares entre 1 y 8.

m 1 2 3 4 5 6 7 8 9 10

φm 1 1 2 2 4 2 6 4 6 4

Un sistema reducido de representantes módulo m es un conjunto for-

mado por φ(m) enteros no congruentes entre sí que representan todas

las clases de congruencias que son invertibles módulo m.

Proposición 17

Si {r1, r2, ..., rk} es un sistema completo (respectivamente, reducido) de

representantes módulo m y a es un entero tal que mcd(a, m ) = 1 (es de-

cir, su clase es invertible en Zm, entonces el conjunto:


En la proposición siguiente resumimos las propiedades más importantes de

la función de Euler que, además, nos permiten calcular sus valores con ma-

yor facilidad. En la demostración de estas propiedades utilizamos el con-

cepto y las propiedades de los sistemas reducidos de representantes que

acabamos de estudiar.

Demostración

1) Hay que calcular cuántos enteros hay entre 1 y pr que sean primos con pr.

Observemos, en primer lugar, que ser primo con pr equivale a ser primo con p.

En efecto, si mcd(x,pr) = 1, entonces mcd(x, p) = 1, y de forma recíproca.

Por lo tanto, se trata de contar cuántos enteros hay entre 1 y pr que no tengan

el factor p. Sin embargo, es más fácil contar cuántos enteros lo llevan: precisa-

mente los múltiplos de p, y hay un múltiplo de p cada p enteros. De este modo,

hay pr/p = pr–1 múltiplos de p entre 1 y pr. Puesto que φ(pr) se obtiene restando

del total los múltiplos de p, tenemos:

.

2) Sean m y n enteros positivos tales que mcd(m,n) = 1. Queremos ver que

φ(mn) = φ(m )· φ(n). Se trata de contar cuántos enteros hay entre 1 y mn, pri-

mos con mn.

Hagamos la tabla de los enteros del 1 al nm dispuestos de la forma siguiente:

S = {ar1, ar2, ..., ark}

es otro sistema completo (respectivamente, reducido) de representantes

módulo m. (El índice k es m si el sistema es completo y φ(m) si se trata

de un sistema reducido.)

Proposición 18

1) Si p es un primo y r≥ 1, entonces φ(pr) = pr – pr–1.

2) Si m y n son enteros positivos primos entre sí (es decir, mcd(m, n ) = 1),

entonces φ(mn) = φ(m) · φ(n).

1 2 ... m

m+1 m+2 ... 2m

(n−1)m+1 (n−1)m+2 ... nm

Podéis intentar hacer vosotros mismos la demostración de la proposición 17.

φ pr( ) pr pr 1––=

...

...

... ...


Los enteros de la columna r, con r = 1, ..., m, son de la forma km + r, donde

k = 0, ..., n – 1. Estos enteros son congruentes con r módulo m . Por lo tanto,

para encontrar los enteros primos con mn (en particular, primos con m) de-

bemos buscar sólo en las columnas r tales que mcd( r, m) = 1. De estas co-

lumnas hay φ(m).

Tomamos, entonces, una columna indizada por un entero r primo con m y

contamos cuántos enteros de la columna son primos con mn. Los enteros de

esta columna son:

donde estamos suponiendo que mcd(r, m) = 1. En particular, todos estos ente-

ros son primos con m. Sólo es necesario encontrar los que, además, son primos

con n . Si restamos r a todos los enteros anteriores, obtenemos:

y como estamos suponiendo que mcd(m,n) =1, éste es un sistema completo de

representantes módulo n (y por lo tanto, el anterior también, ya que se obtiene

sumando una constante r). Sin embargo, un sistema completo de representan-

tes siempre contiene un sistema reducido.

Por lo tanto, en cada columna de las seleccionadas hay un total de φ(n) enteros

primos con mn. Como hay φ(m) de estas columnas, tenemos un total de

φ(n)·φ(m) enteros entre 1 y mn primos con mn. Consecuentemente:

si mcd (m, n) = 1.

Ejemplo 21

Calculemos los valores φ(125) y φ(360).

• Por un lado, tenemos (aplicando el primer apartado de la proposición anterior):

.

Es decir, hay 100 enteros positivos entre 1 y 125 que son primos con 125 (de modo equi-valente, que no los divide el 5).

• Por otro lado, la descomposición del 360 es 23 · 3 2 · 5. Por lo tanto, aplicando el segundoapartado de la proposición anterior y después el primero:

.

r, m r, ..., km r , (n 1 )m– r+ + +

0, m , 2m, ..., k m, ..., (n 1 )m–

φ mn( ) φ m( ) φ n( )⋅=

φ 125( ) φ 5 3( ) 53 52– 125 25– 100= = = =

φ 360( ) φ 2 3 32 5⋅ ⋅( )=

φ 2 3( ) φ 32( ) φ 5( )⋅⋅=

2 3 2 2–( ) 32 3–( ) 5 1–( )⋅ ⋅=

96=


Es decir, hay un total de 96 enteros positivos menores que 360 que no son divisibles por2, ni por 3, ni por 5.

6.4. Teoremas de Fermat y de Euler

En este subapartado estudiaremos un par de teoremas, importantes en sí

mismos, que nos facilitan, además, hacer cálculos con congruencias o, si se

prefiere, en el anillo Zm. Como veremos más adelante, el teorema de Fermat

es un caso particular del teorema de Euler, y fue el primero en ser demos-

trado.

Demostración

1) Si p = 2, entonces el teorema es inmediato: la clase a debe ser igual a 1, y

hemos acabado.

2) Supongamos, entonces, que p es un número primo impar. Entonces el con-

junto de los enteros entre 1 y p – 1 es obviamente un sistema reducido de re-

presentantes módulo p. Además, si multiplicamos estos números por el entero

a, que es primo con p, el conjunto que obtenemos también es un sistema re-

ducido de representantes módulo p, para la proposición 17. Es decir, los con-

juntos siguientes:

y

son sistemas reducidos de representantes módulo p: los elementos de S, y los

de T, representan todas las clases de congruencia no nulas módulo p (recorde-

mos que si p es primo, entonces Zp es un cuerpo y, por lo tanto, los elementos

invertibles son todos los no nulos).

Por lo tanto, el producto de los elementos de S debe ser congruente con el pro-

ducto de los elementos de T (en términos de clases es, tal vez, más fácil de ob-

servar: Z*p está formado por las clases de los elementos de S, es decir, 1, 2, ...,

p – 1 ; análogamente, Z*p también está formado por las clases de los elementos

de T, es decir, a, 2a, ..., (p – 1) a. Es decir:

Teorema 8: teorema de Fermat

Si p es un primo y a ∈ Z satisface mcd(p,a) = 1, entonces:

De forma equivalente, si a ∈ Z*p, entonces ap – 1 = 1. Es decir, la potencia

(p – 1)–ésima de cualquier elemento no nulo de Zp es 1.

Pierre Fermat (1601-1665)...

... fue un gran matemático fran-cés que introdujo por primera vez el concepto de infinito en el cálculo y descubrió propieda-des de varios números. Se con-sidera el creador de la moderna teoría de los números.

ap 1– 1 (mod p )≡

S 1 2 … p 1–( ) }, , ,{= T a 2a … p 1–( )a }, ,,{=


.

Pero P es un entero primo con p; por lo tanto, en virtud de la proposición 11,

podemos simplificar los dos lados de la congruencia anterior por P y, enton-

ces, obtenemos:

.

La prueba de este teorema es muy similar a la que hemos hecho del teorema

de Fermat.

Observemos que, en el teorema de Euler, cuando tomamos m = p primo, en-

tonces φ(p) = p –1, y lo que dice el teorema es que si a es un entero primo con

p, entonces ap–1 ≡ 1. Es decir, el teorema de Fermat es el caso particular del teo-

rema de Euler cuando m es un número primo.

Ejemplo 22

Calculemos el resultado de dividir 1.9971.997 entre 12.

Debemos encontrar el representante que está entre 0 y 11 del entero en cuestión. En pri-mer lugar, encontramos la clase de 1.997 módulo 12:

Por lo tanto, tenemos:

.

Ahora podemos aplicar el teorema de Euler, ya que mcd(5, 12) = 1. Este teorema asegura que:

Calculamos φ(12)

Por lo tanto, 54 ≡ (mod 12). Así pues, si ahora dividimos 1.997 entre 4, obtenemos:

Por lo tanto, el residuo de dividir 1.9971.997 entre 12 es 5.

Teorema 9: teorema de Euler

Si a ∈ Z y m>1 satisfacen mcd(a, m) = 1, entonces:

De forma equivalente, la potencia φ(m)–ésima de la clase a es 1; es decir:

aφ(m) = 1 si a ∈ Z*m.

P 1 2 … p 1–( ) a 2 a … p 1–( )a (mod p )⋅ ⋅⋅≡⋅ ⋅ ⋅=

a p 1– 1 2 … p 1–( )⋅ ⋅ ⋅( ) (mod p )⋅≡

a p 1– 1 (mod p )≡

a φ m( ) 1 (mod m )≡

1.997 5 (mod 12)≡

1.997 1.997 51.997 (mod 12)≡

5φ 12( ) 1 (mod 12).≡

φ 12( ) φ 2 2 3⋅( ) φ 2 2( ) φ 3( )⋅ 2 2 2 1–( ) 3 1 30–( )⋅ 2 2⋅ 4= = = = =

1.997 1.997 5 1.997≡ 5 499 4 1+⋅ 54( )499 5⋅ 5 (mod 12).≡= =


6.5. Pruebas de divisibilidad

Ahora estudiamos una aplicación de la teoría de las congruencias en la obten-

ción de las llamadas pruebas de divisibilidad. Son conocidas las pruebas de di-

visibilidad por 2 o por 3, por ejemplo, entre otras. La prueba del 2 dice que un

número entero es divisible por 2 si acaba en cifra par. La del 3 dice que un nú-

mero es divisible por 3 si la suma de sus cifras es un múltiplo de 3. ¿Cómo se

obtienen estos criterios?

Consideremos un entero positivo N escrito en base 10:

donde los ai son dígitos decimales, es decir, números enteros entre 0 y 9. Esto

significa que:

. (2)

1) Prueba de divisibilidad por 2

Tenemos la equivalencia siguiente:

N es par ⇔ N ≡ 0 (mod 2)

⇔ a0 ≡ 0 (mod 2)

⇔ a0 es par

ya que las potencias de 10 son números pares. Por lo tanto, un número es di-

visible por 2 si, y sólo si, acaba en una cifra par.

2) Prueba de divisibilidad por 3

El ejemplo anterior nos define una estrategia a seguir. Se trata de conseguir en

la expresión (2) que N sea congruente con 0 módulo 3 y, por lo tanto, debemos

estudiar cómo son las potencias de 10 módulo 3. Estas potencias son todas

congruentes con 1 módulo 3, ya que 10 ≡ 1. Por lo tanto:

.

Es decir, un entero es múltiplo de 3 si sus cifras decimales suman otro múl-

tiplo de 3.

N a na n 1– …a1a0=

N an 10 n an 1– 10n 1– … a1 10 a0+⋅+ +⋅+⋅=

3 N N 0 (mod 3)≡⇔

an an 1– … a1 a 0 0 (mod 3)≡+ + + +⇔


Como hemos visto en estos dos ejemplos, si queremos obtener una prueba de

divisibilidad por d, debemos calcular las clases de congruencias de las poten-

cias de 10 módulo el entero d.

Ejemplo 23

Encontremos un criterio de divisibilidad para d = 7.

Consideremos la expresión decimal de un entero N:

.

Ahora estudiemos las potencias de 10 módulo 7:

Esta última congruencia era previsible, ya que 10 y 7 son primos entre sí y el teorema de Fer-

mat dice entonces que 106 es congruente con 1 módulo 7. Ahora observamos que las poten-

cias se van repitiendo cíclicamente; es decir, 107 ≡ 3, 108 ≡ 6, etc. Así pues, para que el enteroN sea divisible por 7 se debe cumplir que:

.

Como podemos ver, es un criterio de divisibilidad díficil de recordar y, por lo tanto, pocopráctico.

N an …a1 a0 a n 10n … a1 10 a0+⋅+ +⋅= =

10 1 3,≡ 102 9 2≡ ≡

10 3 6,≡ 104 18 4≡ ≡

10 5 12 5,≡ ≡ 106 15 1≡ ≡

a0 3a1 2a2 6a3 4a4 5a 5 a6 … 0 (mod 7)≡+ + + + + + +


Resumen

En este módulo hemos expuesto una introducción a la aritmética de los nú-

meros enteros. Hemos empezado con los conceptos de divisibilidad y de máxi-

mo común divisor, y hemos hecho especial énfasis en el algoritmo de

Euclides, que permite calcular eficientemente el máximo común divisor de

dos enteros. Después hemos estudiado los números primos y la factorización

de enteros. Finalmente, hemos definido las congruencias de enteros y hemos

visto cómo podemos estudiar y resolver problemas de divisibilidad a partir de

la teoría de congruencias. Para conseguirlo, hemos utilizado sobre todo la es-

tructura algebraica de los anillos de enteros modulares y sus propiedades más

notables, como por ejemplo, los teoremas de Fermat y de Euler.


Actividades complementarias

1. Encontrad el cociente y el residuo resultantes de dividir:a) 100 entre 17.b) –100 entre 17.c) 294 entre –17.d) –294 entre –17.

2. Encontrad el máximo común divisor de los pares de números siguientes y escribid la iden-tidad de Bézout correspondiente:a) 102 y 222.b) 666 y 1.414.c) 3.120 y 270.d) 20.785 y 44.350.

3. Demostrd que si k es un entero arbitrario, entonces los enteros 3k + 2 y 5k + 3 son primosentre sí.

4. Encontrad el mínimo común múltiplo de los pares de números que se indican:a) 5.040 y 7.700.b) 23·57·1113 y 2·3·5·7·11·13.

5. Resolved las ecuaciones diofánticas siguientes, en el caso de que tengan solución:a) 60x + 18y = 97.b) 1.402x + 1.969y = 1

6. Encontrad los enteros que tienen exactamente tres divisores positivos.

7. Dad los valores positivos de los módulos que hacen correctas las siguientes congruencias:

a) .

b) .

c) .

8. Resolved las ecuaciones en las siguientes congruencias:a)

b)

9.a) Encontrad las clases de congruencia módulo 8 y haced las tablas de la suma y el pro-ducto.b) Calculad un sistema completo de representante.c) Calculad un sistema reducido de representante.

10. Proporcionad un sistema completo de representantes módulo 13 formado exclusivamen-te por enteros impares.

11. Probad, por inducción, que para todo entero positivo n se cumple:

12. Encontrad los valores de φ(m) si 11 ≤ m ≤20.

13. Encontrad el residuo de dividir 3997.755 entre 35.

14. ¿Cuál es la última cifra decimal del entero 71.000?

15. Obtened la prueba de divisibilidad para 11.

Ejercicios de autoevaluación

1. Usad el teorema de la división entera para demostrar que:a) el cuadrado de un entero es la forma 3k o 3k + 1b) el cubo de un entero es de la forma 9k, 9k + 1 o 9k + 8.

2. Probad las respuestas siguientes:a) Para todo entero a, mcd(2a + 1, 9a + 4) = 1b) Si mcd (a, b) = 1, entonces mcd (a + b, a – b) es 1 o 2.

27 5 (mod m )≡

1.000 1 (mod m )≡

1.331 0 (mod m )≡

10x 30 (mod 15)≡

21x 18 (mod 24)≡

4 n 1 3n (mod 9)+≡


3. Resolved las ecuaciones diofánticas siguientes:a) 123x + 360y = 99.b) 158x – 57y = 7.

4. Demostrad que si un número primo p divide una potencia an, entonces pn también la di-vide. Es decir, si p | an, entonces pn | an.

5. Probad que si un entero n es una potencia k -ésima, entonces, en la factorización de n comoproducto de primos, los exponentes son múltiplos de k.

6. Encontrad cómo debe ser un entero para que tenga exactamente 4 divisores positivos.

7. Calculad la clase módulo 4 de la suma siguiente:

.

8. Resolved las ecuaciones en congruencias siguientes:

a) .

b) .

9. Encontrad todas las soluciones enteras del sistema de congruencias siguiente:

, , .

10. Probad que si p es un primo impar, entonces la congruencia:

tiene exactamente dos soluciones módulo p.

11. Calculad la clase de 1.9862.061 módulo 7.

12. Encontrad las dos últimas cifras de 3256.

13. Sean n y m dos enteros tales que todo primo que divida n también divida m (por ejemplo,12 y 60). Probad que φ(nm) = n · φ(m). Deducid de ello que φ(n2) = n · φ(n ).

14.a) Sean a y m enteros primos entre sí. Probad que la ecuación en congruencias:

tiene como solución x ≡ aφ(m) – 1 · b (mod m).b) Aplicad este resultado para encontrar la solución de la ecuación:

.

1 5 2 5 … 99 5 100 5+ + + +

34x 60 (mod 98)≡

140x 133 (mod 301)≡

x 2 (mod 3)≡{ x 5 (mod 7)≡ x 3 (mod 4)}≡

x2 1 (mod p )≡

a x b (mod m )≡

3x 5 (mod 16)≡


Solucionario

Actividades

1.a) Si a | b, entonces existe un x tal que a x = b. Entonces –b = (–x) a y –b = x (–a). Por lotanto, ±a | ±b.b) Pongamos ax = b. Si multiplicamos por c ≠ 0, axc = bc. Por lo tanto, ac | bc.c) Recíprocamente, si c ≠ 0, de acx = bc podemos simplificar la c y nos queda ax = b . Por lotanto, a | b.d) Si ax = b y b ≠ 0 , entonces |a| · |x| = |b| >0. Por lo tanto, |a| ≤ |b|.e) Del apartado anterior, tenemos que |a| ≤ |b| y |b| ≤ |a|. Por lo tanto, |a| = |b|.f ) Si a | b, podemos poner ax = b y entonces x = b / a, que también divide b.

2. En cada paso del algoritmo de Euclides extendido se cumple la igualdad:

donde debemos entender que r−1 = a y r0 = b. En efecto, para k = –1 y k = 0 tenemos, res-pectivamente:

Supongamos ahora que se cumple la igualdad:

ri = ax i + by i

para todos los enteros i desde 0 hasta k . Entonces:

3. Sean a y b dos enteros positivos y pongamos:

,

donde los exponentes ei ≥ 0 y los fi ≥ 0. Entonces, el máximo común divisor de a y b vienedado por la fórmula:

y el mínimo común múltiplo, por la fórmula:

4.a) Si a, b, k ∈ Z y k ≠ 0, entonces:

.

b) Si a ≡ b (mod m) y d | m, entonces d | m(a – b) y, por lo tanto, a ≡ b (mod d).

c) Si r | (a – b) y s | (a – b), entonces a – b es múltiplo del mcm(r, s) = m y, por lo tanto, aes congruente con b módulo m.

r k a xk byk+=

a r 1– ax 1– by 1–+ a 1 b 0⋅+⋅= = =

b r0 a x0 by 0+ a 0 b 0⋅+⋅= = =

a xk 1+ byk 1++ a xk 1– qk 1+ xk )– b y k 1– qk 1+ y k–( )+(=

a xk 1– byk 1–+( ) qk 1+ a xk byk+( )–=

rk 1– qk 1+ r k–=

rk 1+=

a p 1e1 … pr

er= b p1

f1 …p r

fr=

mcd (a b ), p1min e

1f1

,( )…p r

min er

fr

,( )=

mcm (a b ), p1max(e1 f1 ), … p r

max( e1 f1 ),=

a b (mod m ) m a b–( )⇔≡

km k a b–( )⇔

ka kb (mod km )≡⇔


5.a) Debemos demostrar, en primer lugar, que el conjunto Zm con la suma es un grupo con-mutativo; es decir, que la suma tiene las propiedades asociativa y conmutativa, que hayun elemento neutro y que cada elemento tiene un inverso o simétrico.

• La propiedad asociativa de la suma de clases se demuestra como sigue (a, b y c son clasesde congruencias módulo m):

suma de clases

suma de clases

asociatividad de la suma en Z

suma de clases

suma de clases.

• La propiedad conmutativa se demuestra de forma completamente análoga (se debe uti-lizar la definición de suma de clases y la propiedad conmutativa de la suma usual a Z).

• El elemento neutro de la suma de clases es la clase 0.

En efecto: a + 0 = a + 0 = a.

• La clase simétrica de una clase a es la clase –a.

En efecto a + –a = a + (–a) = 0.

b) Ahora debemos probar que el producto de clases tiene las propiedades asociativa y conmuta-tiva y que tiene un elemento neutro. Además, se debe comprobar que se satisface la propiedaddistributiva del producto respecto de la suma. En lo que respecta a las propiedades asociativa yconmutativa del producto de clases y la distributividad del producto respecto de la suma, se de-muestran de forma análoga a como lo hemos hecho para la propiedad asociativa de la suma.

• Finalmente, puede comprobarse que el elemento neutro del producto es la clase 1 .

En efecto:

Actividades complementarias

1.a) .

b) .

c) .

d) .

2.a)

b) ;c) mcd (3.120, 270) = 30; 3.120 · 2 + 270 · (−23) = 30d) mcd (20.785, 44.350) = 5; 20.785 · (−1.707) + 44.350 · 800 = 5.

3. Si tenemos en cuenta que mcd (a,b) = mcd (a, b –a ), obtenemos:

4.a) .

b) .

5.a) La ecuación no tiene soluciones enteras, ya que mcd(60,18) = 6 y 6 no divide 97, que es eltérmino independiente.b) Tenemos: mcd (1.402, 1.969) = 1. Por lo tanto, la ecuación tiene soluciones enteras. Laidentidad de Bézout es:

a b c+( )+ a b c+ +=

a b c+( )+=

a b+( ) c+=

a b+ c+=

a b+( )= c+

a 1⋅ a 1⋅ a= =

100 17 5 15+⋅=

100– 17 6–( ) 2+⋅=

294 17–( ) 17–( ) 5+⋅=

294– 17–( ) 18 12+⋅=

mcd (102,222) = 6; 102 13–( ) 222 6⋅+⋅ 6=

mcd (666, 1.414) = 2 666 138–( ) 1.414 65⋅+⋅ 2=

mcd (3 k 2, 5 k 3 )+ + mcd (3k 2 2k 1 )+,+ mcd (2k 1 k 1 )+,+ mcd ( k 1 k ),+= = = =

mcd (k 1 ), 1= =

mcm (5.040 7.700 ), 277.200=

mcm (23 5 7 1113 2 3 5 7 11 13 )⋅ ⋅ ⋅ ⋅ ⋅,⋅ ⋅ 2 3 3 57 7 1113 13⋅ ⋅ ⋅ ⋅ ⋅=


.

Por lo tanto, las soluciones son:

donde t es un entero arbitrario.

6. Sea n un entero positivo y sea:

su factorización como producto de primos. Entonces sabemos que el número de divisores po-sitivos de n viene dado por el producto:

y, en este caso, esto debe ser igual a 3. Puesto que 3 es un primo, resulta que en el productoanterior sólo hay un factor:

y, por lo tanto, e1 = 2. Así pues, los enteros que sólo tienen tres divisores positivos son los

cuadrados de un número primo; es decir, los enteros de la forma ±p2, donde p es un número

primo positivo. Resulta, por lo tanto, que los divisores positivos son 1, p y p2.

7.a) .

b) 1.000 = 1 (mod m) ⇔ m | 1.000 – 1 = 999 = 3 3 · 37, y los divisores positivos de 999 son 1,3, 9, 27, 37, 111, 333, 999.

c) 1.331 ≡ 0 (mod m) ⇔ m | 1.331 = 113 ⇔ m = 11k, donde k es un entero entre 0 y 3.

8.a) El mcd(10,15) = 5 divide el término independiente 30 y, por lo tanto, hay solución. Pode-mos simplificar la congruencia si dividimos por 5 y obtenemos:

que equivale a la ecuación diofántica 2x + 3y = 6. Las soluciones de esta ecuación son:

Por lo tanto, la solución es x ≡ –6 ≡ 0 (mod 3).

b) El mcd(21,24) = 3 divide el término independiente 18 y, por lo tanto, hay solución. Pode-mos simplificar la congruencia si dividimos por 3 y obtenemos:

que equivale a la ecuación diofántica 7x + 8y = 6. Las soluciones de esta solución son:

Por lo tanto, la solución es x ≡ –6 ≡ 2 (mod 8).

9.

a) Tenemos:

donde la clase a está formada por los enteros de la forma a + 8k.

1.402 889 1.969 633–( )⋅+⋅ 1=

x 889 1.969 t–=

y 633– 1.402 t+=

n p1e1 …p r

er=

e1 1+( ) … e r 1+( )⋅ ⋅

e1 1+ 3=

27 5 (mod m ) m 27 5–⇔≡ 22 m 1 2 1 1 2 2 }, , ,{∈⇔=

2x 6 (mod 3 )≡

x 6 3 t––=

y 6 2+ t, t Z∈=

7x 6 (mod 8)≡

x 6– 8– t=

y 6 7 t , t Z∈+=

Z 8 0 1 2 3 4 5 6 7 }, , , , , , ,{=


Las tablas son:

b) Un sistema completo de representantes es el conjunto de los enteros entre 0 y 7:

Scompleto = {0, 1, 2, 3, 4, 5, 6, 7}.

c) Un sistema reducido está formado por los enteros entre 0 y 7 primos con 8:

S reducido = {1, 3, 5, 7}

Por lo tanto, φ(8) = 4.

10. Un sistema completo de representantes módulo 13 es:

S1 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}.

Si queremos uno que sólo contenga enteros impares, podemos sumar múltiplos de 13 a losenteros pares de S1, hasta obtener unos representantes impares. Por ejemplo, 0 + 13 = 13 es

un entero impar congruente con 0 módulo 13.

Por lo tanto, podemos sustituir el 0 por el 13 en S1. De forma análoga, podemos sustituir cada

entero par k de S1 por k + 13 y obtenemos:

S2 = {13, 1, 15, 3, 17, 5, 19, 7, 21, 9, 23, 11, 25}.

que es un sistema como el que queríamos.

11.

1. Para n = 1 tenemos: 41 = 4 ≡ 1 + 3 · 1 (mod 9).

2. Supongamos que la propiedad es cierta para un entero n. Entonces:

(por hipótesis de inducción)

= (1 + 3n) · (1 + 3) = 1 + 3n + 3 + 9n

≡ 1 + 3 · (n + 1) (mod 9).

12.

13.

Tenemos que φ(35) = 24 y 3 es primo con 35. Por lo tanto, por el teorema de Euler:

Por lo tanto, las potencias de 3 módulo 35 se repiten cada 24. Así pues, tenemos:

Es decir, el residuo es 27.

+ 0 1 2 3 4 5 6 7 · 0 1 2 3 4 5 6 7

0 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0

1 1 2 3 4 5 6 7 0 1 0 1 2 3 4 5 6 7

2 2 3 4 5 6 7 0 1 2 0 2 4 6 0 2 4 6

3 3 4 5 6 7 0 1 2 3 0 3 6 1 4 7 2 5

4 4 5 6 7 0 1 2 3 4 0 4 0 4 0 4 0 4

5 5 6 7 0 1 2 3 4 5 0 5 2 7 4 1 6 3

6 6 7 0 1 2 3 4 5 6 0 6 4 2 0 6 4 2

7 7 0 1 2 3 4 5 6 7 0 7 6 5 4 3 2 1

m 11 12 13 14 15 16 17 18 19 20

φ(m) 10 4 12 6 8 8 16 6 18 8

4 n 1+ 4 n 4 1 3 n+( ) 4⋅≡⋅=

3φ 35( ) 3 24 1 (mod 35).≡=

3 997.755 3 24 41.573 3+⋅ 3 24( ) 41.573 3 3 27 (mod 35).≡⋅= =


14.

La última cifra decimal de un entero se obtiene calculando el residuo módulo 10. Puesto que7 y 10 son primos entre sí, podemos aplicar el teorema de Euler.

Ahora, 1.000 es múltiplo de 4 y, así pues,

Por lo tanto, 71.000 se acaba en 1.

15. Debemos estudiar las potencias de 10 módulo 11. Tenemos:

y es fácil apreciar que las potencias con exponente par son congruentes con 1 módulo 11 ylas potencias con exponente impar son congruentes con –1 módulo 11.

Por lo tanto, un entero n es divisible por 11 si sus cifras an ...a0 satisfacen:

Si P (N) denota la suma de las cifras que están en posición par y S(N ) denota la suma delas que están en posición impar, entonces N es divisible por 11 si, y sólo si, P(N) – S(N) esmúltiplo de 11.

Ejercicios de autoevaluación

1.• Un entero n es siempre de la forma 3q + r, con 0 ≤ r < 3; es decir, n = 3q, n = 3q + 1 o n = 3 q + 2.• En el primer caso, n2 = 9q2 = 3 (3q2).• En el segundo, n2 = 9q2 + 6q + 1 = 3 (3q2 + 2q) + 1.• En el tercero, n2 = 9q2 + 12q + 4 = 3 (3q2+4q+1) + 1.• Ahora consideremos los 9 posibles residuos de dividir por 9 y procedamos igual que antes.• Si el residuo de dividir un entero n por 9 es 0, 3 o 6, entonces n3 es de la forma 9k.• Si es 1, 4 o 7, entonces n3 es de la forma 9k + 1.• Si es 2, 5 o 8, entonces n3 es de la forma 9k + 8.

2. a) Tenemos:

.

b) Supongamos que mcd(a,b) = 1. Entonces:

• Si a + b es impar, entonces d = 1, ya que mcd (2b, a + b) = 1.• Por otro lado, si a + b es par, entonces d = 2.

3.a) b)

4. Si p | an = a · a · ... · a, por el lema de Gauss tenemos que p debe dividir algún factor; esdecir, p | a , pero entonces pn | an.

5. Que n sea una k-ésima potencia quiere decir que hay un entero m tal que n = mk. Si facto-rizamos m como producto de primos:

7 φ 10( ) 7 4 1 (mod 10)≡=

71.000 7 4 250⋅ 1 (mod 10)≡=

10 1 1–≡

10 2 1≡

a0 a1– a2 a3– … 0 (mod 11)≡+ +

mcd (2 a 1 9a 4 )+,+ mcd (2a 1 9a 4 4 2 a 1+( ) )–+,+=

mcd (2 a 1 a ),+=

mcd (2 a 1 2a a ),–+=

mcd(a 1 ), 1= =

mcd (a b a b )–,+ mcd (a b a b )– a b+,( )–+ mcd (2 b a b )+, d= = =

x 1.353 120– t y, 462– 41 t t Z∈,+= =x 154– 57 t y,+ 427– 158t t Z∈,+= =

m p1e 1… p r

er=


entonces la factorización de n será:

por lo tanto, los exponentes ke i son todos múltiplos de k .

6. Consideremos la factorización en primos de un entero n :

Sabemos que el número de divisores positivos de n es el producto:

.

El 4 descompone como 4 = 2 · 2; por lo tanto, n tiene sólo dos factores primos elevados a 1.Es decir, n es de la forma n = pq, con p y q primos diferentes.

7. Sea S la suma. Podemos agrupar los sumandos de 4 en 4 de la forma siguiente:

.

Dentro de cada suma el primer sumando siempre es congruente con 15 módulo 4, el segundosumando siempre es congruente con 25 módulo 4, el tercero siempre es congruente con 35

módulo 4 y el último es congruente con 45 módulo 4. Por lo tanto:

.

Es decir, S = 0.

8.

a)

b)

9. Si x ≡ 2 (mod 3), entonces x = 2 + 3y , para cierto entero y . Reducimos esta igualdad a mó-dulo 7 y obtenemos:

y como 3 y 7 son primos entre sí, podemos simplificar por 3 la congruencia anterior e y ≡ 1(mod 7). Esto significa que y = 1 + 7z, para cierto entero z, y que x = 5 + 21z . Reducimos amódulo 4 y obtenemos:

Por lo tanto: z = 2 + 4u, para cierto entero u. Finalmente, obtenemos:

es decir: x ≡ 47 (mod 84).

10. Si x2 ≡ 1 (mod p), entonces:

y por el lema de Gauss, p | (x–1) o bien p | (x + 1); es decir, x ≡ 1 (mod p) o bien x ≡ –1 (modp), que son las dos soluciones de la congruencia. Observemos que –1 y 1 no son congruentesentre sí si p es un primo impar.

11. Tenemos: 1.986 ≡ 5 (mod 7), φ(7) = 6 y 2.061 ≡ 3 (mod 6). Por lo tanto, por el conocidoteorema de Fermat:

1.9862.061≡52.061≡53≡125≡6.

12. Las dos últimas cifras de un entero se obtienen reduciéndolo módulo 100. Puesto que 3y 100 son primos entre sí, podemos aplicar el teorema de Euler. Tenemos:

Por otro lado, 256 ≡ 16 (mod 40). Por lo tanto, por el teorema de Euler:

n mk

p1e1( …p r

er)

kp1

k e1… p r

k er= = =

n p1e1 …p r

er=

P e1 1+( ) … e r 1+( )⋅ ⋅=

S 1 5 25 35 4 5+ + +( ) … 97 5 98 5 99 5 100 5+ + +( )+ +=

S 25 1 5 2 5 35 4 5+ + +( ) 1 0 3 0+ + +≡⋅≡ 4 0 (mod 4)≡=

x 45 (mod 49)≡

x 16 (mod 43)≡

2 3 y+ x 5 (mod 7) 3 y 3 (mod 7)≡⇒≡=

5 21z+ x 3 (mod 4) z 2 (mod 4)≡⇒≡=

x 2 3y+ 5 21z+ 47 84 u,+= = =

p x2 1– x 1–( ) x 1+( )⋅=

φ 100( ) φ 22 5 2⋅( ) φ 2 2( ) φ 5 2( )⋅ 2 20⋅ 40= = = =

3 256 316≡ 814 19–( )4 21 (mod 100)≡ ≡=


13. Supongamos:

,

Entonces:

.

14.

a) Si a y m son primos entre sí, entonces, por el teorema de Euler:

Por lo tanto, tenemos:

Es decir, el entero aφ(m)–1 representa la clase inversa de la clase a. Por lo tanto, si multiplica-mos los dos lados de la congruencia original por aφ(m)–1, obtenemos:

b) Aplicación: φ(16) = φ(24) = 23 = 8:

Glosario

anillo de enteros modularesEl conjunto de clases de congruencia módulo m, denotado como Zm ′ es un anillo conmuta-tivo con unidad con la suma y el producto de clases. Recibe el nombre de anillo de enterosmodulares módulo m.

clases de congruenciaDado un entero a módulo m, es el conjunto de enteros que son congruentes con a módulom. Se escribe a.

clase invertibleClase de congruencia que tiene inverso respecto del producto.

congruenciaVed números congruentes .

cuerpo finitoAnillo Zp son cuerpos finitos si, y sólo si, p es un número primo.

divisorDado un entero a, se dice que es divisor de otro entero b si hay un único entero x tal queax = b. También se dice que a es divisible por b o que b es múltiplo de a.

ecuación diofánticaEcuación polinómica con coeficientes enteros de la que nos interesa conocer las solucionesenteras.

enteros primos entre síEnteros sin ningún factor primo en común. Es decir, enteros que tienen el máximo comúndivisor igual a 1.

función de EulerLa función φ de Euler de un entero m es 1 si m = 1 y el número de enteros positivos menoresque m y primos con m , si m >1. Coincide con el cardinal de Z*

m.

máximo común divisor (mcd)Dado un conjunto de enteros, el mcd entero positivo divisor común de todos los enteros delconjunto tal que cualquier otro divisor común es divisor de aquél.

n p1e1 …p r

er= m p1f 1… p r

f r=

φ nm( ) φ p1e1

f1

+… p r

er

fr

+( ) φ p1

e1

f1

+( )…φ p r

er

fr

+( )= =

p1e1 f 1+

p1e1 f1 1–+–( )= … p r

er f 1+p r

er f r 1–+–( )

p1e1 f 1 1–+= p1 1–( )… pr

er f r 1–+p r 1–( ) nφ m( )=

a φ m( ) 1 (mod m )≡

aφ m( ) 1– a⋅ a φ m( ) 1 (mod m )≡=

aφ m( ) 1– ax x aφ m( ) 1– b (mod m )⋅≡ ≡⋅

3x 5 (mod 16) x 3 8 1– 5 7 (mod 16)≡⋅≡⇒≡


mínimo común múltiplo (mcm)Dado un conjunto de enteros, el mcm es un entero positivo mínimo que es al mismo tiempomúltiplo de cada uno de los enteros del conjunto.

múltiploVed divisor.

número primoUn número entero p es primo si es diferente de ±1 y los únicos divisores de p son ±1 y ±p.

números congruentesDados dos enteros a y b, son congruentes módulo un entero m si la diferencia a – b es múl-tiplo de m. Lo escribimos así: a ≡ b (mod m).

sistema completo de representantesConjunto de enteros no congruentes entre sí módulo m que representan todas las clases decongruencia módulo m y que constituyen un sistema completo de representantes módulo m.

sistema reducido de representantesConjunto de enteros no congruentes entre sí módulo m que representan todas las clases decongruencia módulo m que tienen inverso (es decir, las clases invertibles) y que constituyenun sistema reducido de representantes módulo m .

Bibliografía

Birkhoff, G.; Maclane, S. (1985). Álgebra moderna (3.ª ed.). Barcelona: Vicens-Vives.

Niven, I.; Zuckerman, H. (1985). Introducción a la teoría de los números (1.ª ed.). México:Editorial Limusa.

aritmética de los números enteros - · pdf file2.1. la relación de...

Documents