Tema 3: Ecuaciones diofnticas, congruencias y criterios de

divisibilidad

J. Sendra, E. Martn, A. Mndez y C. Ortiz

Marzo 2011

ndice

Gua del tema II

1. Ecuaciones Diofnticas 1

2. Congruencias 4

3. Sistemas de Numeracin y criterios de divisibilidad 10

I
Matemtica Discreta. Curso 2010/11. 2o semestre. (Dpto. Matemtica Aplicada a la I.T.T.) E.U.I.T.Telecomunicacin (U.P.M.)

Gua del tema

Asignatura: Matemtica Discreta

Titulo de la Unidad: Ecuaciones diofnticas, congruencias y criterios de divisibilidad

Semanas de imparticin en el cuatrimestre: Del 21 de marzo al 1 de abril

Requisitos para seguir con aprovechamiento el tema

Manejar con soltura el algoritmo de la divisin.

Conocer y manejar relaciones de equivalencia.

Atencin y paciencia para asimilar los resultados.

Conocer y utilizar el principio de induccin matemtica.

Objetivos

Objetivo general: Conocer y manejar ecuaciones diofnticas, congruencias y sistemas de numeracin

Objetivos Especficos:

Manejar los restos de las divisiones.

Conocer y resolver las ecuaciones diofnticas.

Manejar el concepto de congruencia.

Aplicar propiedades bsicas de las congruencias.

Conocer el Teorema Pequeo de Fermat.

Calcular el inverso de un nmero en Zm .

Resolver Ecuaciones con congruencias.

Entender el Teorema de los restos chinos y saber aplicar el mtodo para resolver un sistema de

congruencias.

Conocer los comandos ms bsicos de Maple en relacin con congruencias.

Deducir criterios de divisibilidad a partir de resultados generales,

Aplicar los resultados para conocer los divisores de un nmero entero no negativo.

Contenidos tericos

II
Matemtica Discreta. Curso 2010/11. 2o semestre. (Dpto. Matemtica Aplicada a la I.T.T.) E.U.I.T.Telecomunicacin (U.P.M.)

Ecuaciones Diofnticas

Congruencias

Sistemas de numeracin y criterios de divisibilidad

Evaluacin Se entregarn los ejercicios propuestos antes de la fecha lmite 11 de abril de 2011

III
Matemtica Discreta. Curso 2010/11. 2o semestre. (Dpto. Matemtica Aplicada a la I.T.T.) E.U.I.T.Telecomunicacin (U.P.M.)

1. Ecuaciones Diofnticas

Se llama ecuaciones diofnticas a una amplia clase de ecuaciones algebraicas con ms de una indeter-

minada en Z y Q. En primer lugar, se estudian las ecuaciones lineales diofnticas de la forma ax + by = n. A

continuacin, se analiza la ecuacin diofntica de la forma x2 y 2 = n con n > 0, as como la ecuacin, tambin

llamada pitagrica, de la forma x2 + y 2 = z 2 . Se termina la seccin enunciando la famosa conjetura de Fermat.

Teorema 1.1. Sean a, b y n Z. La ecuacin lineal ax + by = n tiene solucin entera x0 , y0 si y slo si

d = mcd(a, b) divide a n.

Demostracin. Si la ecuacin tiene soluciones enteras x0 , y0 entonces ax0 + by0 = n. Ahora bien, como d | ax0

y d | by0 se tiene que d | n. Supongamos ahora que d | n, es decir existe r Z tal que n = dr. Si n = 0 entonces

x0 = 0 e y0 = 0 es una solucin trivial de la ecuacin. Si n 6= 0 entonces d 6= 0 y existen u, v Z tales que

au + bv = d. Multiplicando por r ambos lados de esta ecuacin se tiene a(ur) + b(vr) = dr = n, de donde se

deduce que x0 = ur, y0 = vr es una solucin de la ecuacin ax0 + by0 = n.

Algoritmo para encontrar una solucin.

Sea la ecuacin diofntica ax + by = n. En primer lugar se calcula el mcd(a, b) mediante el algoritmo

de Euclides:
a = bq1 + r1

b = r1 q2 + r2
..
.

rt2 = rt1 qt + rt

rt1 = rt qt+1

donde rt = mcd(a, b) = d. Por tanto despejando de la penltima ecuacin se tiene:

rt2 rt1 qt = d

y substituyendo el valor de rt1 de la ecuacin anterior a sta, se obtiene:

rt2 (rt3 rt2 qt1 )qt = d

que es equivalente a:

rt3 qt + rt2 (1 + qt qt1 ) = d.

Siguiendo este proceso de substitucin ascendiendo por las igualdades, se obtiene

aq1 + bq2 = d

1
Matemtica Discreta. Curso 2010/11. 2o semestre. (Dpto. Matemtica Aplicada a la I.T.T.) E.U.I.T.Telecomunicacin (U.P.M.)

donde q1 , q2 son expresiones en funcin de q1 , , qt . Por tanto, una solucin de la ecuacin diofntica es:

nq1 nq2
x0 = , y0 = .
d d

Ejemplo 1.1. Se quiere encontrar una solucin entera de la ecuacin diofntica:

525x + 100y = 50.

En primer lugar observamos que mediante el algoritmo de Euclides:

525 = 100 5 + 25

100 = 4 25

por tanto mcd(525, 100) = 25 y adems como 25 | 50, se tiene que la ecuacin diofntica tiene soluciones enteras.

Despejando de la primera ecuacin se tiene:

525 + (5)100 = 25

y en este caso obtenemos:

1 50 5 50
x0 = = 2, y0 = = 10
25 25

que es una solucin entera de la ecuacin diofntica.

Proposicin 1.1. Sean a, b y n Z. Si x0 , y0 es una solucin particular de la ecuacin diofntica ax + by = n,

entonces todas las soluciones enteras de la ecuacin son de la forma

x = x0 + (b/d)t, y = y0 (a/d)t, t Z

donde d = mcd(a, b).

Demostracin. Para los detalles sobre la demostracin ver [3] Proposicin 2.2.6.

Ejemplo 1.2. Se quiere encontrar las soluciones enteras de la ecuacin diofntica del ejemplo anterior:

20x + 50y = 430.

Sabemos que x0 = 2 y0 = 10 es una solucin particular, por tanto aplicando la proposicin anterior se tiene

que todas las soluciones son de la forma:

x = 2 + (100/25)t = 2 + 4t, y = 10 (525/25)t = 10 21t, t Z.

Ejercicio 1. Nos preguntamos si ser posible llenar exactamente un depsito de 25 litros con recipientes de 6

y 8 litros.

A continuacin se estudia la resolucin en Z de las ecuaciones diofnticas de la forma x2 y 2 = n.

2
Matemtica Discreta. Curso 2010/11. 2o semestre. (Dpto. Matemtica Aplicada a la I.T.T.) E.U.I.T.Telecomunicacin (U.P.M.)

Teorema 1.2. La ecuacin diofntica x2 y 2 = n con n > 0, tiene solucin n se puede factorizar como

producto de dos nmeros de la misma paridad, es decir ambos pares o ambos impares. Si existen, las soluciones

son de la forma:
a+b ab
x= , y=
2 2
donde a y b recorren todos los pares de nmeros de la misma paridad y tales que n = ab.

Demostracin. Para los detalles sobre la demostracin ver [1] Teorema 1-4.7.

Ejemplo 1.3. Encontrar todas las soluciones positivas de x2 y 2 = 40.

Como 40 = 23 5, se tiene que 40 puede expresarse como el producto de dos nmeros de la misma paridad como

40 = 10 4 = 20 2. Por tanto, si a = 10 y b = 4 se tiene

14 6
x= = 7, y = = 3
2 2

y si a = 20 y b = 2 se tiene
22 18
x= = 11, y = = 9.
2 2
Por tanto, las soluciones buscadas son {7, 3} y {11, 9}.

Como aplicacin del resultado anterior, Fermat estableci un algoritmo para estudiar si un nmero

natural impar es compuesto.

Algoritmo de factorizacin de Fermat.

Sea n un nmero natural impar, esto es n = ab con a y b impares. Por el Teorema 1.2 se puede expresar:

a+b 2 ab 2
( ) ( ) = n.
2 2

Por tanto, el problema se traduce en resolver la ecuacin: x2 y 2 = n o equivalentemente, x2 n = y 2 . Para ello,

primero se determina el mnimo entero positivo q que satisfaga q 2 n y estudiamos si alguno de los siguientes

nmeros:

q 2 n, (q + 1)2 n, (q + 2)2 n,

es un cuadrado. Obsrvese que este proceso es finito pues:

n+1 2 n1 2
( ) n=( ) .
2 2

De todo ello se deduce que los nicos valores que hay que estudiar son los m tales que:

n+1
qm .
2

Concluyendo, que si para ninguno de estos valores de m, el valor de m2 n es un cuadrado, entonces el nmero

n es primo.

3
Matemtica Discreta. Curso 2010/11. 2o semestre. (Dpto. Matemtica Aplicada a la I.T.T.) E.U.I.T.Telecomunicacin (U.P.M.)

Ejemplo 1.4. Veamos si el nmero 22733 es un nmero compuesto. En primer lugar se obtiene que el menor q

tal que q 2 22733 es q = 151. Por tanto, habr que estudiar si alguno de los nmeros m comprendidos entre:

(22733 + 1)
151 m = 11367.
2

verifican si m2 22733 es un cuadrado.

1512 22733 = 22801 22733 = 68

1522 22733 = 23104 22733 = 371

1532 22733 = 23409 22733 = 676 = 262 .

De donde se concluye que 22733 = 179 127.

Analizamos ahora la ecuacin diofntica de la forma:

x2 + y 2 = z 2

con x, y, z Z, tambin llamada ecuacin pitagrica. Obsrvese que este problema es equivalente a encontrar

todos los tringulos rectngulos con lados de longitud entera.

Teorema 1.3. Las soluciones de la ecuacin pitagrica x2 + y 2 = z 2 que satisfacen las condiciones:

mcd(x, y, z) = 1, 2 | x, x, y, z Z

vienen dadas por las frmulas:

x = 2st, y = s2 t2 , z = s2 + t2

para s, t con s > t tales que mcd(s, t) = 1 y s y t tienen distinta paridad.

Demostracin. Para los detalles sobre la demostracin ver [1] Teorema 1-4.11.

Conjetura de Fermat. La ecuacin xn + y n = z n no tiene soluciones con x, y, z N cuando n 3.

Desde mediados del siglo XVII la conjetura de Fermat ha constituido un problema del que se han ocupado

numerosos matemticos, algunos de gran renombre como por ejemplo Euler, Gauss, Legendre, Cauchy, Lam

o Dirichlet y se propusieron premios para quien demostrase su veracidad, o falsedad. En 1995 Andrew Wiles

demostr un resultado, con un pequeo error detectado por Richard Taylor, mediante el que la conjetura de

Fermat quedaba demostrada.

2. Congruencias

Definicin 2.1. Si m es un nmero entero positivo, se dice que dos nmeros enteros a, b son congruentes

mdulo m si existe k Z tal que a b = km. Simblicamente se denota a b mod(m).

4
Matemtica Discreta. Curso 2010/11. 2o semestre. (Dpto. Matemtica Aplicada a la I.T.T.) E.U.I.T.Telecomunicacin (U.P.M.)

Observacin 2.1. Siguiendo la definicin anterior se tiene que

a b mod(m) m | (a b).

El lenguaje de congruencias fue introducido por K. Gauss a los 24 aos en su libro Disquisitiones

Arithmeticae, y hoy seguimos utilizndolo en la vida cotidiana. La esfera de un reloj funciona con congruencias

mdulo 12, los cuentakilmetros de los coches lo hacen mdulo 100000 y los meses se representan mdulo 12.

Ejemplo 2.1.
0 8 mod(4)

6 4 mod(2)

18 3 mod(5)

Proposicin 2.1. La relacin de congruencia mdulo m en Z, es de equivalencia y divide a Z en clases de

equivalencia de manera que dos diferentes de ellas son disjuntas.

Demostracin. Para los detalles sobre la demostracin ver [3] Proposicin 2.4.1.

Proposicin 2.2. Fijado m > 0, cada nmero entero a Z es congruente mdulo m con uno de los enteros

0, 1, 2 , m 1.

Demostracin. Dividiendo a entre m, se tiene que existen q y r nicos tales que a = qm + r con 0 r < m.

De donde se deduce que a r mod(m).

Observacin 2.2. La congruencia mdulo m divide a Z en m clases de equivalencia que son [0],[1],[2], .., [m1],

cuyo conjunto cociente viene dado por

Zm = {[0], [1], , [m 1]}

Ejemplo 2.2. Las clases de equivalencia en Z mdulo 3 son [0],[1], y [2]:

[0] = {a Z \ a 0 mod(3)} = {a Z \ a = k 3, k Z} = { , 6, 3, 0, 3, 6, }

De forma anloga:

[1] = {a Z \ a 1 mod(3)} = {a Z \ a = 1 + k 3, k Z} = { , 5, 2, 1, 4, 7, }

[2] = {a Z \ a 2 mod(3)} = {a Z \ a = 1 + k 3, k Z} = { , 4, 1, 2, 5, 8, }

Teorema 2.1. Sea m entero positivo y a, a0 , b, b0 Z.

a) Si a a0 mod(m) y b b0 mod(m) entonces a + b a0 + b0 mod(m).

b) Si a a0 mod(m) y b b0 mod(m) entonces ab a0 b0 mod(m).

5
Matemtica Discreta. Curso 2010/11. 2o semestre. (Dpto. Matemtica Aplicada a la I.T.T.) E.U.I.T.Telecomunicacin (U.P.M.)

c) Si a a0 mod(m) y h 6= 0 nmero entero, entonces ah a0 h mod(m).

a a0
d) Si h | a, h | a0 , mcd(h, m) = 1 y a a0 mod(m), entonces h h mod(m).

Demostracin. Se deja como ejercicio al lector.

Ejemplo 2.3. Como 9 1 mod(8), aplicando c) del teorema anterior se tiene que

9 9 1 9 mod(8) 1 mod(8)

as sucesivamente

3400 = (32 )200 1200 mod(8) 1 mod(8).

Las congruencias tienen varias aplicaciones en matemticas, una de ellas es la obtencin de los criterios

de divisibilidad que se estudiarn en la siguiente seccin. Otra aplicacin de las congruencias es el siguiente

resultado.

Teorema 2.2. El Teorema Pequeo de Fermat. Sea p un nmero primo y a un nmero natural tal que p no

divide a a. Entonces, ap1 1 mod(p).

Demostracin. Para los detalles sobre la demostracin ver [3] Teorema 2.4.7.

Proposicin 2.3. Sea a b mod(m1 ), a b mod(m2 ), , a b mod(mk ) donde a y b son nmeros enteros

y m1 , m2 , , mk son enteros positivos. Entonces

a b mod(m.c.m(m1 , m2 , , mk )).

Demostracin. Para los detalles sobre la demostracin ver [3] Proposicin 2.4.8.

Corolario 2.1. Sea a b mod(m1 ), a b mod(m2 ), , a b mod(mk ) donde a y b son nmeros enteros

y m1 , m2 , , mk son enteros positivos primos dos a dos. Entonces

a b mod(m1 m2 mk ).

Clculo del Inverso en Zp .

Todo elemento [a] Zp tiene su opuesto respecto a la suma, [p a], y si p es primo, y [a] 6= [0] , tiene inverso

multiplicativo y es nico. A continuacin, se exponen dos mtodos distintos para calcular el elemento inverso.

El primero se basa en el Teorema Pequeo de Fermat anteriormente estudiado y que escribimos de la

forma:

[a]p1 = [1].

6
Matemtica Discreta. Curso 2010/11. 2o semestre. (Dpto. Matemtica Aplicada a la I.T.T.) E.U.I.T.Telecomunicacin (U.P.M.)

Esto es:

[a]p2 [a] = [a]p1 = [1] [a]1 = [a]p2 .

El segundo mtodo se basa en el Teorema de Bezout (vase Teorema 5.1.1 en [9]) que afirma que dados

a, b Z no nulos, existen u, v Z tales que ua + vb = mcd(a, b). Por tanto, si [a] Zp , con 0 < a < p 1

entonces existen u, v Z tales que ua+vp = 1. Tomando clases de equivalencia se tiene: [u][a] = [1][p] =

[1], de donde se deduce que:

[a]1 = [u].

Computacionalmente, el segundo mtodo es ms apropiado que el primero, la idea bsica para calcular [a]1 = [u]

es seguir el proceso explicado en la seccin 1 en el algoritmo para encontrar una solucin de una ecuacin

diofntica, utilizando el algoritmo de Euclides. (Ver Capitulo 4 en [9]). Ntese que es equivalente a encontrar

una solucin de la ecuacin diofntica ax + py = 1.

Ejemplo 2.4. Calcular el inverso de [7] en Z31 . Aplicando el algoritmo de Euclides de la divisin se tiene:

31 = 4 7 + 3

7=23+1
Despejando los restos de las dos igualdades se tiene:

31 4 7 = 3

723=1
Ahora substituyendo el valor del resto de la primera en la segunda igualdad se tiene:

1 = 7 2 3 = 7 2 (31 4 7) = 9 7 2 31.

De donde se deduce que el inverso es [7]1 = [9].

Observacin 2.3. El comando igcdex de Maple devuelve el mcd de dos nmeros enteros a y b, tal que

g = mcd(a, b) con g = sa + tb.

> igcdex(7,31,s,t);

> s;t;

9
2

7
Matemtica Discreta. Curso 2010/11. 2o semestre. (Dpto. Matemtica Aplicada a la I.T.T.) E.U.I.T.Telecomunicacin (U.P.M.)

Ecuaciones con congruencias.

Se considera la ecuacin ax b mod(m) con a, b nmeros enteros y m entero positivo. Esta ecuacin

se satisface cuando existe y Z tal que:

ax b = ym.

Es decir, si (x, y) es una solucin de la ecuacin diofntica ax b = ym, x es una solucin de ax b mod(m).

Ejemplo 2.5. Queremos encontrar las soluciones enteras de 4x 2 mod(6). Si x es una solucin entera

de esta ecuacin, existe un nmero entero y tal que 4x 2 = 6y, esto es 4x 6y = 2. Ahora bien, como

mcd(4, 6) = 2 divide a 2, por el Teorema 1.1 se tiene que la ecuacin diofntica tiene solucin entera. Adems,

por la Proposicin 1.1, la ecuacin tiene infinitas soluciones que pueden expresarse de la forma:

x = x0 + (b/2)t, y = y0 (a/2)t, t Z

siendo (x0 , y0 ) una solucin particular. Por ello, en primer lugar calculamos (x0 , y0 ) utilizando el algoritmo de

Euclides. Obsrvese que como 6 = 1 4 + 2 se tiene despejando que (1) 4 (1) 6 = 2, de donde se deduce

que x0 = 1, y0 = 1 es una solucin particular. Por tanto, las soluciones de 4x 2 mod(6) son de la forma

x = 1 3t, t Z. Ntese que todas estas soluciones pertenecen slo a dos clases de equivalencia: si t es par

x 1 mod(6) y si t es impar x 2 mod(6).

Teorema 2.3. Sean a y b dos nmeros enteros y m un entero positivo con mcd(a, m) = d. Si d no divide a b,

la ecuacin ax b mod(m) no tiene solucin. Si d divide a b, la ecuacin ax b mod(m) tiene exactamente

d soluciones no congruentes entre s mdulo m.

Observacin 2.4. Las d soluciones no congruentes entre s mdulo m a las que se refiere el Teorema anterior

se pueden expresar de la forma:

x = x0 (m/d)n, n = 0, 1, 2, 3, , d 1.

Un antiguo problema Chino.

Encontrar un nmero que dividido entre 3 d como resto 1, dividido entre 5 d como resto 2 y que dividido entre

7 d como resto 3.

Esto es, se trata de resolver el sistema:

x 1 mod(3)



x 2 mod(5)



x 3 mod(7).

Este tipo de problemas, han dado lugar al siguiente teorema.

8
Matemtica Discreta. Curso 2010/11. 2o semestre. (Dpto. Matemtica Aplicada a la I.T.T.) E.U.I.T.Telecomunicacin (U.P.M.)

Teorema 2.4. El Teorema de los Restos Chinos. Sun Tsu, siglo I. Sean m1 , m2 , ms enteros primos entre s.

Entonces el sistema de congruencias:

x a1 mod(m1 )






x a2 mod(m2 )

..

.




x a mod(m ).
s s

tiene una nica solucin entera en cada uno de los intervalos

[u, u + m1 ms ) con u Z.

Demostracin. Para los detalles sobre la demostracin ver [9] Captulo 4, Seccin 4.3.1.

Observacin 2.5. De la demostracin se deduce que si k 6= j entonces mcd(mk , mj ) = 1 y por el Teorema

de Bezout se tiene que existen enteros uk,j , uj,k tales que uk,j mk + uj,k mj = 1, y por tanto la solucin

mencionada es de la forma:

a = a1 (u2,1 m2 us,1 ms ) + a2 (u1,2 m1 u3,2 m3 us,2 ms ) + + as (u1,s m1 us1,s ms1 ).

Para resolver un sistema con ms de dos ecuaciones de congruencias se procede como sigue: primero se

resuelve el sistema formado por las dos primeras

x a1 mod(m1 )

x a2 mod(m2 )

en cada [u, u+m1 m2 ) y denotemos por A la solucin encontrada. A continuacin se resuelve, de la misma

forma, el sistema

x A mod(m1 m2 )

x a3 mod(m3 )

en cada [u, u + m1 m2 m3 ). Finalmente, se repite el proceso hasta terminar con las ecuaciones del sistema

inicial. (Para ms detalle ver [9], Captulo 4, Seccin 4.3.1.)

Ejemplo 2.6. Resolver el sistema:

x 1 mod(3)



x 2 mod(5)



x 3 mod(7).

En primer lugar se resuelve el sistema formado por las dos primera ecuaciones:


x 1 mod(3)

x 2 mod(5)

9
Matemtica Discreta. Curso 2010/11. 2o semestre. (Dpto. Matemtica Aplicada a la I.T.T.) E.U.I.T.Telecomunicacin (U.P.M.)

En este caso m1 = 3 y m2 = 5, y aplicando el algoritmo de Euclides se tiene que el sistema:

5=13+2

3=12+1

tiene solucin nica en [0, 0 + 3 5) = [0, 15). Para calcular esta solucin, despejamos los restos en las dos

igualdades

513=2

3 1 2 = 1.

Ahora, substituyendo r1 = 2 en la segunda igualdad se tiene 2 3 1 5 = 1, y por tanto u = 2 y v = 1.

Siguiendo la observacin anterior se tiene que la solucin es de la forma

a = a1 vm2 + a2 um1 = 1 (1) 5 + 2 2 3 = 7.

A continuacin, se resuelve el sistema de congruencias:

x 7 mod(15)

x 3 mod(7).

Siguiendo el mismo procedimiento encontramos la solucin en el intervalo [0, 0 + 15 7) = [0, 105):

15 = 7 2 + 1.

de donde se deduce que 15 7 2 = 1 y por tanto u = 1 y v = 2. Por tanto, la solucin es

a = a1 vm2 + a2 um1 = 7 (2) 7 + 3 1 15 = 53.

Obsrvese que como la solucin ha de estar en [0, 105), se tiene que la solucin es 105 58 = 52. Comprubese

que efectivamente x = 52 es una solucin del problema inicial.

En Maple podemos utilizar el comando chrem(L1,L2) con L1 := [a1 , , as ] y L2 := [m1 , , ms ],

calcula la solucin nica del sistema de congruencias en el intervalo [0, m1 ms ). Veamos un ejemplo en Maple.

> chrem([1,2,3],[3,5,7]);
>

52

3. Sistemas de Numeracin y criterios de divisibilidad

El sistema de numeracin utilizado habitualmente para escribir nmeros enteros agrupa de 10 en 10

unidades de un orden para formar una unidad de un orden superior. Por ejemplo, el nmero 3501213 se puede

escribir como potencias de 10 de la forma

3501213 = 3 106 + 5 105 + 0 104 + 1 103 + 2 102 + 1 101 + 3 100

10
Matemtica Discreta. Curso 2010/11. 2o semestre. (Dpto. Matemtica Aplicada a la I.T.T.) E.U.I.T.Telecomunicacin (U.P.M.)

Histricamente se han utilizado otros sistemas de numeracin, as la forma de contabilizar las horas en el reloj

es una consecuencia del sistema de potencias de 60 usado en la antigedad. En la actualidad los ordenadores

utilizan sistemas de numeracin de potencias de 2, por ejemplo 16, o 32.

Un nmero entero cualquiera se puede representar como una combinacin lineal de potencias de un

nmero natural (Ta . 3.1), por ejemplo 21 en potencias de 2 es 1 24 + 0 23 + 1 22 + 0 2 + 1 20 y en potencias

de 5 es 4 5 + 1.

Observacin 3.1. En general, dado un nmero natural b y si el nmero n se puede representar en combinaciones
k
X
lineales de potencias de b como n = ak bk + ak1 bk1 + . . . + a1 b + a0 b0 = ai bi , escribiremos
i=0
n = (ak ak1 . . . a1 a0 )b .

Si el nmero b es mayor que 9 los smbolos para valores superiores a 9 se representan por letras maysculas

A para 10, B para 11, C para 12 y as sucesivamente, con lo que (A2C3)16 = 10163 +2162 +1216+3 = 41667.

Teorema 3.1. Sea un nmero natural, b, fijo al que llamaremos base. Entonces, para cualquier nmero entero

n existen ak , . . . , a0 Z, con 0 ai < b i = 0, . . . , k tal que n = ak bk + . . . + a0 b0 .

Demostracin. Sin prdida de generalidad supondremos que n es positivo. Por el algoritmo de la divisin

n = c1 b + a0 , con 0 a0 < b. Aplicando otra vez el mismo algoritmo c1 = c2 b + a1 , con 0 a1 < b.

Continuando con el proceso obtenemos una secuencia n > c1 > . . .. Puesto que todo subconjunto no vaco de

nmeros naturales tiene un elemento menor que los dems (Principio de la Buena Ordenacin) existe un primer

elemento ck 6= 0, tal que ck = 0 b + ak , con 0 ak < b. Entonces,

n = c1 b + a0 = (c2 b + a1 ) b + a0 = c2 b2 + a1 b + a0 = (c3 b + a2 ) b2 + a1 b + a0 =

= c3 b3 + a2 b2 + a1 b + a0 = . . . = ak bk + . . . + a2 b2 + a1 b + a0

Supongamos n = ak bk + . . . + a1 b + a0 = k bk + . . . + 1 b + 0 , sin prdida de generalidad podemos

suponer que el nmero de sumandos es el mismo, ya que en otro caso se completa con trminos nulos. Restando

ambas expresiones obtenemos

0 = (ak k ) bk + . . . + (a1 1 ) b + a0 0 0 a0 = (ak k ) bk + . . . + (a1 1 ) b

b divide a todos los trminos del miembro de la dcha. de la ltima igualdad por lo que debe dividir a 0 a0 ,

es decir b|0 a0 , y puesto que 0 |0 a0 | < b, se debe cumplir que 0 a0 = 0, por lo que 0 = a0 .

Reordenando la ltima expresin, dividiendo por b y repitiendo el proceso obtenemos ai = i para todos los

i = 0, 1, . . . , k.

El teorema previo nos asegura que dada cualquier base, b,todo nmero entero positivo admite una

representacin nica como combinacin lineal de potencias de b, donde los coeficientes son todos inferiores a b.

11
Matemtica Discreta. Curso 2010/11. 2o semestre. (Dpto. Matemtica Aplicada a la I.T.T.) E.U.I.T.Telecomunicacin (U.P.M.)

Ejemplo 3.1.

1. Para escribir el nmero 1864 en base 13, dividimos sucesivamente por 13 y consideramos los restos,

1864 = 11 132 + 0 13 + 5 = (C05)13

2. Para resolver la ecuacin (225)7 = (x)4 consideramos el nmero en base 10 y, despus expresamos el

resultado en base 4.

(225)7 = 2 72 + 2 7 + 5 = 117 = 43 + 3 42 + 4 + 1 = (1311)4 x = 1311

X
Corolario 3.1. Sea n un nmero entero y b un nmero natural. El nmero n = ai 10i es divisible por
X i=0
b ai ri es divisible por b, siendo ri el resto de dividir 10i por b (10i ri mod (b)). Otra forma de
i=0 X
expresarlo es diciendo que ai ri es congruente con 0 mod (b)
i=0

Demostracin. Supondremos que n es positivo y que su representacin en base 10 es

k
X
k k1
n = ak 10 + ak1 10 + . . . + a1 10 + a0 = ai 10i , con 0 ai < 10 i = 0, . . . , k
i=0

Si ri el resto de dividir 10i por b, para i = 0, . . . , k, se tiene que 100 r0 mod (b) 1 mod (b);

101 r1 mod (b), . . . , 10k rk mod (b). Entonces, utilizando que

a b mod (m) a b mod (m) y a b mod (m) y c d mod (m) (a+c) (b+d) mod (m)

se tiene !
k
X k
X k
X
i
n= ai 10 ai ri mod (b) ai ri mod (b)
i=0 i=0 i=0
Pk
Entonces, n es divisible por b n 0 mod (b) i=0 ai ri es divisible por b.

Ejemplo 3.2. En los dos siguientes ejemplos obtendremos criterios particulares para divisin por 3 y 7.

1. Puesto que 101 1 mod (3) 10h 1h mod (3). Entonces,

k
X
n= ai 10i es divisible por b a0 1 + . . . + ak 1 es divisible por b
i=0

Es decir, un nmero entero es divisible por 3 si la suma de sus dgitos es divisible por 3.

2. Para establecer el criterio de divisibilidad por 7 ntese que:

1 1 mod (7); 103 6 mod (7) 1 mod (7)

10 3 mod (7); 104 4 mod (7) 3 mod (7)

102 2 mod (7); 105 5 mod (7) 2 mod (7)

12
Matemtica Discreta. Curso 2010/11. 2o semestre. (Dpto. Matemtica Aplicada a la I.T.T.) E.U.I.T.Telecomunicacin (U.P.M.)

Adems, 106 1 mod (7), por lo que para un valor k > 6 cualquiera se verifica

10k = 106l+r , con 0 r < 6 10k 1 10r mod (7)

con lo que se van repitiendo en el mismo orden los restos. As, el criterio de divisibilidad por 7 es
k
X
n ai 10i es divisible por 7 a0 + 3a1 + 2a2 a3 3a4 2a5 + . . . es divisible por 7
i=0

Si dado un entero positivo b y consideramos el vector Vb = (l0 , l1 , . . . , ln , . . .), llamado adjunto de b,

formado por los enteros ms prximos a cero que es solucin de x 10n mod (b), con n N, el criterio general

de divisibilidad podemos expresarle como

k
X
n= ai 10i es divisible por b a0 l0 + . . . + ak lk es divisible por b Vn Vb es divisible por b
i=0

siendo Vn = (a0 , a1 , . . . , an , 0, . . .).

A la vista de los casos anteriores V3 = (1, 1, . . .) = (1), donde 1 significa que 1 se repite indefinidamente

(es el periodo de 3). Se puede demostrar que todo nmero entero positivo tiene vector adjunto peridico, y, en

particular V7 = (1, 3, 2, 1, 3, 2).

13