Teoria De Numeros

DIVISIBILIDAD
Lic. Walter Otoniel Campos Granados

1.
1.1.

DIVISIBILIDAD
Lema de la Divisi´n
o

Los siguientes resultados nos ayudaran a establecer el teorema principal
de esta secci´n, sus pruebas son sencillas y las omitiremos.
o
Teorema 1.1 Si x es cualquier n´mero real distinto de uno, entonces
u
n−1
xn − 1
xi = 1 + x + x2 + . . . + xn−1 =
x−1
i=0
Corolorario 1.1 Si m y nson enteros positivos y m > 1, entonces mn ≥ n
Teorema 1.2 (Teorema de Representaci´n de Bases) Sea k cualquier
o
entero mayor que uno. Entonces, para cada entero positivo n, existe una
representaci´n
o
n = a0 k s + a1 k s − 1 + . . . + as
donde a0 = 0, y cada ai es no negativo y menor que k . Adem´s, esta
a
representaci´n es unica; llamada la representaci´n de n en la base k .
o
´
oDemostraci´n:
o
Sea Pk (n) el n´mero de representaciones de n en la base k . Se debe probar
u
que Pk (n) siempre es igual a 1.
N´tese que algunos de los ai en una representaci´n particular pueden ser
o
o
cero. Sin afectar dicha representaci´n, se pueden excluir dichos t´rminos.
o
e
As´ sup´gase que
ı
o
n = a0 k s + a1 k s − 1 + . . . + as − t k t ,
1

Lic. Walter Otoniel

2donde ahora ni a0 ni as−t son iguales a cero. Entonces
n − 1 = a0 k s + a1 k s − 1 + . . . + as − t k t − 1
= a0 k s + a1 k s−1 + . . . + (as−t − 1)k t + k t − 1
t−1

(k − 1)k i − 1

= a0 k s + a1 k s−1 + . . . + (as−t − 1)k t +
i=0

en el ultimo renglon se ha utilizado el Teorema 1.1 con x = k . De aqu´ se
´
ı
deduce que para cada representaci´n de n en la base k , se puedeencontrar
o
una representaci´n para n − 1. As´
o
ı
Pk (n) ≤ Pk (n − 1)
donde la ultima desigualdad es cierta a´n si n no tiene representaci´n ya que
´
u
o
Pk (n) = 0 ≤ Pk (n − 1) en dicho caso. Si n tiene otra representaci´n en la
o
base k , por el mismo proceso se establecer´ otra representacion para n − 1.
ıa
De manera que
Pk (n + 2) ≤ Pk (n + 1) ≤ Pk (n),
Pk (n + 3) ≤ Pk (n + 2) ≤ Pk (n+ 1) ≤ Pk (n),
y, de manera general, si m ≤ n + 4,
Pk (m) ≤ Pk (m − 1) ≤ Pk (m − 2) ≤ . . . ≤ Pk (n + 1) ≤ Pk (n)
por ser k n > n y por tener k n al menos una representaci´n (¿cual?), se tiene
o
que
1 ≤ Pk (k n ) ≤ Pk (n) ≤ Pk (1) = 1
Una vez una base k > 0 ha sido escogida, se puede representar cualquier
entero positivo n unicamente como sumas de potencias de k :
´
n = a0 k s + a1 k s− 1 + . . . + as
donde los a0 , a1 , . . . , as son enteros no negativos menores que k . Esta representacion es usualmente denotada por el s´
ımbolo “a0 a1 . . . as ”.
Es com´n que para bases menores o iguales que diez, los ai son escogidos de
u
los s´
ımbolos 0, 1, 2,..., 9 con su significado usual, sin embargo, si k es mayor
que diez, se deben inventar s´
ımbolos de manera que se tengan ks´
ımbolos
diferentes.

Lic. Walter Otoniel

3

Ejemplo 1.1 En base dos (23)10 ≡ (10111)2 ; la base 16 es bastante com´n,
u
aqui se acostumbra tomar A = 10, B = 11, C = 12, D = 13, E = 14,
F = 15, en esta base (543)10 ≡ (21F )16 , ya que 543 = 1 • 162 +2 • 161 +15 • 160 .

Las bases 2, 8, 16 son muy importantes en Ciencia Computacional.
Nota: Para obtener los coeficientes en laexpansi´n, basta con hacer divio
siones sucesivas del n´mero en base diez, entre la base k , luego se toma el
u
ultimo cociente y todos los residuos partiendo del ultimo hasta el primero,
´
´
en ese orden.
Definici´n: Dados dos n´meros enteros a, b, con a = 0, se dice que a divide
o
u
a b (lo cual se denota por a|b) si existe un entero x tal que b = ax.
Si a no divide a b se escribe a | b.
Si adivide a b, tambi´n se dice que b es m´ltiplode a, que a es divisor b, que
e
u
a es un factor de b o que b es divisible por a.
N´tese que seg´n la anterior definici´n 2|4, 5|30, 3|24, 11|242, 7 |18, 4 |27.
o
u
o
Algunas Propiedades B´sicas:
a
1. Si a|b entonces a|bc para todo entero c.
2. Si a|b y b|c entonces a|c.
3. Si a|b y a|c entonces a|bx + cy , para todo par de enteros x,...