Divisibilidad en N - Módulo II

Máximo divisor Común

Ejemplo:
Dos terrenos de 12 y 18 hectáreas se fraccionan en parcelas de igual área, siendo esta la mayor posible.
Se pide calcular el número de parcelas para cada terreno.

Teniendo en cuenta situaciones vistas, como los terrenos se dividen en lotes de igual área, entonces hay que
buscar los divisores comunes de 12 y 18.
d(12)= {1 ; 2 ; 3 ; 4 ; 6 ; 12} d(18)= {1 ; 2 ; 3 ;6 ;9 ;18}
Los divisores comunes son:
d (12)∩d (18) = {1 ; 2 ; 3 ;6}
Buscamos que los lotes sean de mayor área posible, por lo tanto deben ser de 6 hectáreas cada uno. El primer
terreno se fraccionará en 2 lotes y el segundo en 3 lotes.
Para resolver este problema calculamos el máximo divisor común entre 12 y 18.

Definición: Sean a y b naturales, no simultáneamente nulos, llamaremos máximo común divisor de a y b, al

máximo del conjunto de los divisores comunes.
Anotamos: D(a;b)

Calcularemos el máximo común divisor en los casos a continuación:

1) D(20;12)
d(20)={1;2;4;5;10;20} y d(12)={1;2;3;4;6;12} → D(20;12)=4

2) D(7;12)
d(7)={1;7} y d(12)={1;2;3;4;6;12} → D(7;12)=1
Los números 7 y 12 se denominan primos entre sí.

Definición: Dos números naturales a y b, tales que D(a;b)=1 se les denomina primos entre sí, o coprimos.

Ejercicios
1) Calcular D(20;0) y D(15;30)
2) Justifica las siguientes propiedades:
A) D(a;0)=a; para todo a distinto de 0.
B) a y b naturales , a /b → D( a ; b)=a

Observemos que calcular el máximo común divisor de 720 y 4620 no es tan sencillo por el camino anterior.
Escribir los conjuntos de divisores de estos números no es práctico. Mostraremos otro camino posible.

Algoritmo de Euclides
Determinaremos el D(300;120)
En el ejercicio 2, parte B), sabemos que si a/b entonces D(a;b)=a
Procederemos de la siguiente forma:
300 120 → 120 no divide a 300
60 2
Como además probamos que los divisores comunes del divisor y del resto, son divisores del dividendo,
busquemos ahora divisores comunes de 60 y 120. Como
120 60 →D(60;120)=60
0 2
Por lo tanto 60/120 y 60/60 → 60/300, utilizando la propiedad recién nombrada y además 60 es el mayor
divisor común de 120 y 300, si tuvieran un divisor común mayor a 60, tendría que ser divisor de 60 porque
los divisores comunes del dividendo 300 y cociente 120, son divisores del resto 60, y esto no es posible.
Concluimos que D(300;120)=60

Con este procedimiento calcularemos D(710;250)

710 250 → 250 210 → 210 40 → 40 10
210 2 40 1 10 5 0 4
Estas divisiones se suelen plantear así:
-------------------------------------- cocientes -----------------------------
////////// 2 1 5 4
710 250 210 40 10
210 40 10 0 /////
-------------------------- restos ----------------------------------------------

D(710;250)=10

El proceso se justifica por la propiedad nombrada en el ejemplo anterior:

d/10 y d/40 → d/210
d/210 y d/40 → d/250
d/250 y d/210 → d/710
Como el mayor divisor común de 10 y 40 es 10, entonces se concluye D(710;250)=10
Al esquema anterior se le denomina algoritmo de Euclides.
En general para hallar D(a;b) realizamos divisiones sucesivas hasta lograr resto 0 y los ordenamos según el
esquema visto.
-------------------------------- cocientes ---------------------------------------
///////////// q1 q2 q3 ----------- qn q n+1
a b r1 r2 ----------- r n-1 rn
r1 r2 r3 r4 ----------- 0 //////////////
--------------------------------------- restos -------------------------------------

Siendo D(a;b) = r n

Ya vimos las propiedades que nos aseguran que r n es el D(a;b).

Una duda que puede surgir es respecto a si siempre terminamos consiguiendo resto 0.
Esto es así, debido a que la sucesión de restos naturales es decreciente, por ser el resto menor que el divisor.

Ejercicios
1) Hallar el D(720;4620)
2) Hallar a, b, c, d, e en el algoritmo de Euclides siguiente:

/////////////////// 1 2 3
a b c 75
d e 0 ///////////////////

3) Hallar los naturales a y b, sabiendo que D(a;b)=10 y los cocientes de las divisiones sucesivas de a
por b en el algoritmo de Euclides son 2; 1; 4; 1 y 5 respectivamente.

//////////////// 2 1 4 1 5
a b r1 r2 r3 10
r1 r2 r3 10 0 ////////////////
ALGUNAS PROPIEDADES:

I) Cualquier divisor de dos números naturales es divisor de su máximo común divisor.

d/a y d/b → d/D(a;b)
Demostración:
Utilizando la propiedad:
a b y d no nulo, entonces: 1) d/a y d/b à d/r 2) d/b y d/r à d/a
r q
deducimos que d(a)∩d(b)=d(b)∩d(r)

///////////// q1 q2 q3 ----------- qn q n+1

a b r1 r2 ----------- r n-1 rn
r1 r2 r3 r4 ----------- 0 //////////////

En el algoritmo de Euclides, utilizamos esta propiedad de forma sucesiva. Es decir:

d(a)∩d(b)=d(b)∩d(r1)=d(r1)∩d(r2)=.........=d(rn)∩d(0)=d(rn)=d(D(a;b))
Concluimos de forma inmediata que si d/a y d/b → d ∈d a∩d b → d ∈d  Da ; b , es decir
d/D(a;b)
II) A partir del algoritmo de Euclides se pueden probar las siguientes propiedades:
Sean a ∈N −{0} ; b∈ N y k ∈N −{0}
1) D(ak;bk)=k.D(a;b)
Ejemplo: D(15;36)=3.D(5;12)=3.1=3
a b 1
2) k /a∧k /b → D( ; )= . D(a ; b)
k k k

3) A partir de la propiedad anterior, tomando k=D(a;b)=D:

a b 1 a b
D( ; )= . D( a ; b)=1 entonces y son primos entre sí.
D D D D D

Esta última propiedad se suele enunciar de la siguiente forma:

Si D(a;b)=D, entonces a=a ´ . D∧b=b ´ . D con D(a ´ ; b ´ )=1

Algunos ejemplos:

1) Hallar las parejas de naturales a y b, a>b, cuya suma sea 96 y tal que D(a;b)=12

Se cumple que a=12.a´ y b=12b´ con D(a´; b´)=1

Como a + b = 96, entonces 12a´ + 12b´ = 96
12(a´ + b´) = 96
96
a´ + b´ = es decir: a´ + b´ = 8
12
Tenemos los siguientes casos:

a´ b´ a b
8 0 ----- ----- D(8;0)=8
7 1 84 12
6 2 ----- ----- D(6;2)=2
5 3 60 36
4 4 ----- ----- D(4;4)=4
Las parejas de naturales son: 1ª) a=84 y b=12
2ª) a=60 y b=36

2) Hallar las parejas de naturales m y p, m>p, m.p=750 y D(m;p)=5

Como D(m;p)=5, m=5m´ y p=5p´
Entonces 52.m´.p´=750
750
m´.p´= =30
25

En la siguiente tabla, tendremos en cuenta que m´.p´=30, m´ y p´ son primos entre sí y

m´ >p´.

m´ p´ m p
30 1 150 5
15 2 75 10
10 3 50 15
6 5 30 25

Parejas buscadas: m=150 y p=5

m=75 y p=10
m=50 y p=15
m=30 y p=25

3) Halla las parejas a y b de naturales, tales que: D(a;b)=6 y a 2 – b2 = 6156

a=6a´ y b=6b´ con D(a´;b´)=1

Sustituyendo en a2 – b2 = 6156
(6a´)2 – (6b´)2 = 6156
36.a´2 – 36.b´2 = 6156
36(a´2 – b´2) = 6156
6156
a´2 – b´2 = = 171
36
Factorizando (a´+b´)(a´- b´)=171
En una tabla escribimos los posibles valores de (a´+b´) y (a´- b´) cuyo producto es 171, sabiendo
que a´+ b´ > a´- b´.

a´+b´ a´-b´ a´ b´ a b
171 1 86 85 516 510
57 3 30 27 ---------------- ---------------
19 9 14 5 84 30

Parejas buscadas: a=516 y b=510

a=84 y b=30
 TEOREMA DE EUCLIDES
“Si un número es divisor del producto de dos naturales y es coprimo con uno de ellos, es divisor
del otro factor”

a∈N , b∈N −{0}; k ∈ N

{ d /a.k } → d/a
D d ; k =1

Demostración:
D(d;k)=1 → D(d.a;k.a)=a
d/a.k (por Hip) → d/a
→ d/D(a.k;a.d)
d/a.d

Ejercicios

1) Mediante el algoritmo de Euclides calcula: D(52;48), D(n+1;n), D(2n+2;2n)

2) Calcula a y b en cada caso:
/////// 1 2 3
a b
6 0

/////// 139 1 3
a b D
0

b + D=85

/////// 8c c c
3
a b 54
0

b+1=65c

3) Hallar todas las parejas de naturales a y b que cumplen:

a – b= 544, D(a;b ) = D(480;2464) y 2a > 9b
Números primos y compuestos

Recordemos que:
I) Un número natural primo es aquel que admite sólo dos divisores naturales.
Es decir: p es primo ↔ p≠1 y d(p)={1;p}

En consecuencia 0 y 1 no son números naturales primos.

II) Un número natural compuesto admite más de dos divisores.

En consecuencia:
• 0 es compuesto.
• 1 no es primo ni compuesto.

Admitiremos que todo número natural compuesto, distinto de 0, se puede escribir como producto de
factores primos. Dicha descomposición es única.

Observemos la descomposición en factores primos del número 72

72 2
36 2
18 2 divisores primos
cocientes obtenidos 9 3
3 3
1

Por lo tanto 72=23.32

Esta descomposición del número 72 en factores primos es única.
Sin embargo no existe una única forma de descomponer el 72, como producto de factores compuestos, o no
todos primos.
Veamos 72=36.2
72=18.4
72=9.2.4
72=[Link]

Ejercicios
1) Hallar la descomposición en factores primos de: 4320 ; 578 ; 121 ; 726

2) Hallar en cada caso el D(a;b)

a) a y b son primos
b) a=0 y b≠0
c) a es divisor de b
d) a y b son naturales consecutivos
e) a y b son pares consecutivos
f) a y b son múltiplos consecutivos de k, k natural no nulo.
Mínimo Común Múltiplo

César y Danilo están en una playa disfrutando del mar. César vuelve a esta playa cada 6 días y Danilo cada 4
días. ¿Después de cuántos días los dos amigos volverán a encontrarse?
César vuelve cada 6 días. El conjunto de múltiplos de 6 nos daría la información referida a César.
m(6)={0;6;12;18;24;30;36;42.........................................}

Danilo vuelve cada 4 días. El conjunto de múltiplos de 4 nos daría la información referida a Danilo..
m(4)={0;4;8;12;16;20;24;28;32;36;40;...........................}

El conjunto de múltiplos comunes es:

m(6)∩m(4)={0;12;24;36;.............}
Es decir, los amigos se encontrarán en esa playa cada 12 días.
El número 12, el mínimo no nulo de este conjunto, se le denomina mínimo común múltiplo de 4 y 6.
Anotamos: m(4;6)=12

Definimos: Mínimo Común Múltiplo de dos naturales a y b (no nulos), al mínimo del conjunto de los
múltiplos comunes, exceptuando el cero.
Anotamos: m(a;b)

Observaciones:
➔ m(a;1)=a ; con a≠0
➔ Si a es divisor de b, entonces: m(a;b)=b
En caso de querer hallar el m(720;4620), el método mostrado en el ejemplo no es práctico. Veamos otras
herramientas para hallarlo.

Relación entre m(a;b) y D(a;b)

Consideremos el número w, múltiplo común no nulo de a y b.
Entonces existen n y p naturales no nulos tales que:
w=a.n y w=b.p

Por propiedad vista, a=a´.D(a;b) y b=b´.D(a;b) con D(a´;b´)=1 (I)

Sustituyendo tenemos:
w=a´.D(a;b).n y w=b´.D(a;b).p (II)

Igualamos
a´.D(a;b).n=b´.D(a;b).p

Cancelamos por ser D(a;b)≠0

a´.n=b´.p

Esto nos permite afirmar que a´/b´.p. Como D(a´;b´)=1 entonces, aplicando el teorema de Euclides
tendremos que a´/p, lo que implica que existe k natural, no nulo, tal que a´.k=p

Sustituyendo en una de las expresiones en (II) queda:

w=b´.D(a;b).a´.k con k≠0
La expresión anterior determina todos los múltiplos comunes de a y b, no nulos. El menor de ellos lo
obtenemos para k=1.
Es decir: m(a;b)=a´.b´.D(a;b)
Utilizando (I) y sustituyendo en la expresión anterior:
a b a.b
m a ; b = . . Da ; b → m a ; b= o´ m(a;b).D(a;b)=a.b
D a ; b D a ; b Da ; b
Aplicación:
Mediante el algoritmo de Euclides podemos calcular D(720;4620)=60
Luego utilizando la fórmula recién probada tendremos
m(720;4620).60=720.4620
720.4620
Entonces m720 ; 4620= =55440
60

Recordemos una forma alternativa de obtener el D(a;b) y el m(a;b)

Calculemos el D(720;4620) y m(720;4620) a partir de la descomposición en factores primos de dichos
números.
720 2 4620 2
360 2 2310 2
180 2 1155 3
90 2 385 5
45 3 77 7
15 3 11 11
5 5 1
1
Así que: 720=24.32.5 4620=[Link].11

El mayor divisor común es D(720;4620)=22.3.5=60

El menor múltiplo común es m(720;4620)=[Link].11= 55440

Ejercicio:
Hallar D(9360;4116420) y m(9360;4116420)

Número de divisores
Calcularemos el número de divisores de 1620
No es sencillo escribirlos todos sin olvidar alguno. Veamos un camino alternativo.
1620=22.34.5
Divisores de 22
d(22)={1;2;22} o sea que 22 tiene 3 divisores, anotamos υ(22)=3 = 2+1
Divisores de 34
d(34)={1;3;32;33;34} o sea 34 tiene 5 divisores, υ(34)=5 = 4+1
Divisores de 5
d(5)={1;5} o sea 5 tiene 2 divisores, υ(51)=2 = 1+1

En definitiva la cantidad de divisores de 1620=22.34.5 la calculamos efectuando el producto de la cantidad de

divisores de 22, la cantidad de divisores de 34 y la cantidad de divisores de 5.

υ(22.34.5)=υ(22).υ(34).υ(5)=(2+1)(4+1)(1+1)=3.5.2=30, 1620 tiene 30 divisores.

En general, los exponentes correspondientes a los distintos factores primos de la descomposición

nos permiten calcular el número de divisores de un número.

N=p1n1.p2n2...........phnh, con pi primo, para 1≤i≤h

υ(N)=(n1 + 1)(n2 + 1). ….... .(nh + 1)

Ejercicio

Sea N=2a.3b.52 . Hallar a y b sabiendo que:

➔ 3N tiene 9 divisores más que N
➔ 5N tiene 12 divisores más que 3N