Download Ejercicio 47.

Página 1 de 14
´
CAPÍTULO DEL LIBRO: “MATEMÁTICA DISCRETA A TRAVÉS DE
UNS INSTRUCCIÓN DIDÁCTICA”. ARRIOLA Y OTROS
Aritmética elemental
por Susana Mastrangelo
Suele considerarse a la aritmética como algo simple, que desde niño se aprende; o bien
como un esquema complejo en el que hay que trabajar rigurosamente, si se la estudia con
mayor profundidad. Sin embargo, presenta otras facetas más interesantes.
La evolución de la computación ha transformado a la aritmética en una ciencia aplicada, la
necesidad de nuevos algoritmos requiere de su conocimiento. Ella facilita el planteo de
algunos problemas complejos, se utiliza en el estudio de la eficiencia de métodos de cálculo
numérico, y es la teoría de números la que subyace bajo numerosas aplicaciones
computacionales.
El objetivo de este trabajo es presentar algunas situaciones que, más allá del manejo de las
propiedades básicas de divisibilidad y aritmética modular, colaboren en la formación
general de los alumnos. La aritmética ofrece grandes posibilidades para el desarrollo de
habilidades tales como: analizar, generalizar, evaluar hipótesis, abstraer, relacionar, y hasta
descubrir nuevos problemas.
Ejercicio 41.
Demostrar que para cualquier entero a, resulta que: mcd (5a  3,7a  4)  1 .
Resolución.
 Sea d = mcd (5a  3,7a  4) . Se quiere demostrar que d =1.
 Datos del problema: de la definición de máximo común divisor, en particular se obtiene
que d es un número natural , y que d es divisor de 5a  3 y de 7a  4 . En símbolos:
d  N  d/ (5a  3)  d /( 7 a  4)
 A partir de esta información y utilizando propiedades de divisibilidad, puede hacerse la
siguiente deducción:
d  N  d / 7(5a  3)  d / 5(7a  4)

d  N  d /(35a  21)  d /(35a  20)
(P1)

d  N  d /[( 35a  21)  (35a  20)]
(P2)

d  N  d /(35a  21  35a  20)

d N  d /1

d =1
 Se enuncian a continuación las propiedades utilizadas:
Cualesquiera sean b, c, d números enteros, b no nulo,
Página 2 de 14
P1) si b/c entonces b/d.c
P2) si b/c  b/d entonces b/(c  d )
Ejercicio 42.
Si a N es coprimo con un número natural b y con el consecutivo de dicho número,
probar que: mcd( a 2b; b 2  b  a)  1
Resolución.
 Los datos del problema pueden expresarse en la forma:
a N , b N , mcd( a; b)  1 , mcd( a; b  1)  1
 Sea d = mcd( a 2b; b 2  b  a) . Se quiere demostrar que d=1.
Para ello se procederá por el método del absurdo, es decir, se supone d  1 .
 Siendo d un número natural (lo es por definición de mcd), distinto de uno, existe al
menos un número primo positivo p tal que p/d (como consecuencia del Teorema
Fundamental de la Aritmética).
Por ser d el máximo común divisor de a 2b y b 2  b  a , se verifica que: d/a 2b y
(P1)
d /(b 2  b  a) , y como p/d, resulta: p / a 2b y p /(b 2  b  a) .
A partir de esta información, puede hacerse la siguiente deducción:
p / a 2b  p /(b 2  b  a)
( p / a  p / b )  p /(b 2  b  a)
(p es primo) (P2) (P3)

2
( p / a  p /(b  b  a) )  ( p / b  p /(b 2  b  a) )

Luego:
 En el caso en que p / a  p /(b 2  b  a) , resulta que
p / a  p /(b 2  b  a  a)
(P4)

p / a  p /(b  b)
p / a  p / b(b  1)

p / a  (p / b  p/(b  1))
(pues p es primo) (P2)

(p / a  p / b)  (p / a  p /(b  1))

p / mcd( a, b)  p / mcd( a, b  1)

Pero los datos del problema indican que mcd(a ,b)=1 y mcd(a ,b+1)=1; resulta
entonces de lo anterior que p/1, lo cual es imposible pues p es primo.
2
 En el caso en que p / b  p /(b 2  b  a) resulta
p / b  p /(b 2  b  a  b 2  b)

p/b p/a
( pues p/b  p/b.(b+1) )
(P5) (P4)
Página 3 de 14
p / mcd( a, b)

y, como antes, esto es imposible pues p no divide a 1.
Así, en cualquier caso resulta un absurdo o contradicción, que proviene de suponer
d  1.
Luego, debe ser d =1, que es lo que se quería demostrar.
 Se enuncian propiedades utilizadas:
Cualesquiera sean a, b, c, p números enteros, n número natural
P1) Si a/b y b/c, entonces a/c
P2) Si p es primo y p/a.b, entonces p/a  p/b
P3) Si p es primo y p/ a n , entonces p/a
P4) Si c/a y c/b, entonces c/ (a-b)
P5) si c/a, entonces c/ a.b
Ejercicio 43.
Si a y b son enteros coprimos, hallar los posibles valores del máximo común divisor entre
3a+7b y 2a+8b
Resolución.
 Sea d=mcd(3a+7b, 2a+8b).
Se quieren determinar los posibles valores de d.
Por definición de máximo común divisor, d/ (3a  7b) y d /( 2a  8b) .
Utilizando propiedades de divisibilidad, puede deducirse de esta información que:
d / 2.(3a  7b)  d/ 3.(2a  8b)  d / 8.(3a  7b)  d / 7.(2a  8b)
(P1)
d /( 6a  14b)  d /( 6a  24b)  d /( 24a  56 b)  d /(14a  56b)

d /[( 6a  24b)  (6a  14b)]  d /[( 24a  56 b)  (14a  56 b)]
(P2)

d / 10 b  d / 10 a

 Si fuese d  1, como d es un número natural, por el teorema fundamental de la
aritmética, existiría algún primo p tal que p/d.
p / 10 b  p / 10 a .
En tal caso, resultará que
p / 10 b  ( p / 10  p / b )
Siendo p primo:
(P3)
p / 10 a  ( p / 10  p / a )
Luego, se tiene que:
( p / 10  p / b )  ( p / 10  p / a )
p / 10  ( p / a  p / b )

Página 4 de 14
Pero, p / a  p / b implicaría que a y b no son coprimos, lo cual no es posible por los
datos del problema. Por lo tanto, se deduce que p / 10 .
 Es decir que podría ser d=1, o bien, si d  1, los únicos primos que intervienen en la
factorización de d son divisores de 10 (esto es: 2 y 5).
En consecuencia, d tiene la forma: d= 2 i.5 j , con i  N0 , j  N0.
- Si fuese i  2 , resultaría que 4 es divisor de d . De las deducciones anteriores se
tenía que d / 10 b  d / 10 a . Si 4/d, entonces:
4 / 10 b  4 / 10 a ,
2 / 5b  2 / 5a
de donde, por (P4):
2/b  2/a
y por (P5):
( 2 y 5 son coprimos)
pero esto es imposible pues a y b son coprimos.
Esta contradicción se produce a partir de la suposición i  2 .
Luego, se ha probado que i  0  i  1.
- De manera similar, si j  2 , resultará que 25 es divisor de d y en consecuencia,
25 / 10 b  25 / 10 a
5 / 2 b  5 / 2 a (P4)

5/b  5/ a
(P5)

lo cual es imposible.
Esto prueba que j  0  j  1 .
 Así, siendo d= 2 i.5 j , con i  0  i  1, j  0  j  1 , los posibles valores del máximo
común divisor d son: 1, 2, 5, 10.
Obsérvese que ninguno de estos valores puede descartarse, dado que es posible hallar
ejemplos diversos (valores enteros de a y b), en los que mcd(3a+7b, 2a+8b) toma
efectivamente estos cuatro valores.
 Propiedades:
Cualesquiera sean a, b, c, p números enteros:
P1) Si b/a entonces b/a.c
P2) Si b/a y b/c, entonces b/(a-c)
P3) Si p es primo y p/a.b, entonces p/a  p/b
P4) Si a.b/a.c, entonces b/c
P5) Si b/a.c y mcd(a,b)=1, entonces b/c
Ejercicio 44.
(a) ¿En qué día de la semana cayó el 9 de julio de 1816?
Página 5 de 14
(b) Averigua en qué día de la semana naciste y verifica que es el mismo que cuando
cumplas 28 años. Prueba que esto es así para cualquier persona nacida entre el 1 de
enero de 1901 y el 31 de diciembre de 2071.
Nota: un año normal tiene 365 días, uno bisiesto, 366. Los años bisiestos son aquellos no
seculares divisibles por 4. Los años seculares son bisiestos si y sólo si son divisibles por
400.
Resolución.
 La observación fundamental para resolver este tipo de cuestiones es que si a una fecha
se le agrega un número de días múltiplo de 7, el día de la semana no cambia.
Si a una fecha dada, por ejemplo jueves 11 de mayo, se le agrega un cierto número de
días M, la nueva fecha es:
jueves,
si M  0 (7)
viernes,
si M  1 (7)
sábado,
si M  2 (7)
domingo,
si M  3 (7)
lunes,
si M  4 (7)
martes,
si M  5 (7)
miércoles,
si M  6 (7)
Un año bisiesto tiene 366 días y esto ocurre en aquellos que son divisibles por 4, como
por ejemplo: 1824, 1980, 1996. Pero hay excepciones: en el caso en que el año es
secular (como 1600, 1700, 1800, 1900, 2000) sólo se consideran bisiestos los divisibles
por 400 (como 1600, 2000).
 Desde el 9 de julio de 1816 al 9 de julio de 2000, hay 184 años.
¿Cuántos de ellos son bisiestos? En este período los bisiestos van desde el 1816
(múltiplo de 4) hasta el 2000 (secular múltiplo de 400), cada 4 años. Sin embargo, no
hay que considerar el 1816 y sí el 2000, puesto que el 9 de julio es posterior al 29 de
febrero; y habrá que descontar el 1900, que no es bisiesto. Luego, habrá
2000  1816
 1  45 bisiestos en este período.
4
Por lo tanto el número de días es 184. 365 +45  5 (7).
Un calendario de 2000 dice que el 9 de julio de 2000 es domingo; desde el 9 de julio
de 1816 han transcurrido M días, con M  5 (7).
Entonces
domingo,
si M  5 (7)
lunes,
si M  6 (7)
martes,
si M  0 (7)
Por lo tanto el 9 de julio de 1816 fue martes.
Ejercicio 45.
Página 6 de 14
a) Verificar con algún número que el siguiente acertijo funciona:
Se elige un número (entero positivo) de tres dígitos; se lo multiplica por 143; se
consideran las tres últimas cifras y a este nuevo número se lo multiplica por 7;
nuevamente se consideran las tres últimas cifras del número obtenido y...éste coincide
con el número elegido al principio!!
b) Justificar que el acertijo funciona siempre.
Resolución.
 El ejemplo que se pide en la parte a) puede ser cualquiera. El objetivo es comprender el
procedimiento.
Ejemplo:
Número elegido:
115
Multiplicado por 143:
16445
Tres últimas cifras:
445
Multiplicado por 7:
3115
Tres últimas cifras:
115, que es el número elegido.
 Justificar que el acertijo funciona siempre es demostrar que cualquiera sea el número
natural de tres cifras, al realizar las operaciones indicadas se vuelve a obtener el mismo
número.
 Una observación: reiteradas veces se pide en el procedimiento considerar las tres
últimas cifras de un número, ¿cómo podría expresarse esto en lenguaje matemático?
Si se tiene en cuenta que
las cifras de un número son los coeficientes que intervienen en la
descomposición decimal de dicho número
entonces puede considerarse que los tres últimos dígitos son el resto de dividir el
número por 1000. Esto es: si los coeficientes a j ( 0  j  n ) son las cifras del número,
resulta:
n
a n 10 n  a n 110 n 1  ...  a 410 4  a 3103  a 210 2  a1101  a 0100   a i10i 
i0




   a i10i   a 210 2  a1101  a 0100  1000   a i10i  3   a 210 2  a1101  a 0100
 i 3

 i 3

n
En términos de congruencia:
n
Página 7 de 14
n
 a 10
i0
i
i
 a 210 2  a1101  a 0100
(1000)
 Volviendo a los pasos que propone el acertijo, puede escribirse en forma general:
Número elegido:
Multiplicado por 143:
Tres últimas cifras:
Multiplicado por 7:
Tres últimas cifras:
a
(natural de tres dígitos)
143a
resto de dividir 143a por 1000, sea b
7b
resto de dividir 7b por 1000, sea c
(Lo que se quiere probar que c es el número elegido a)
En términos de congruencia, se tiene entonces que:
143a  b (1000)  7b  c (1000)
De esta información puede deducirse que:
7.143a  7b (1000) (multiplicando por 7)  7b  c (1000)
1001a  7b (1000)  7b  c (1000)

Pero 1001  1 (1000) , y como la relación de congruencia cumple la propiedad
1001a  a (1000)
transitiva, resulta:
a  c (1000)
y por lo tanto
Como a es número natural de tres cifras, en particular a está en condiciones de ser
resto de una división por 1000 ( 0  a  999 ), pero también c lo está (pues
precisamente era resto de una división por 1000). Al ser congruentes entre sí módulo
1000, deben ser iguales.
Por lo tanto a=c, como se quería demostrar.
 Puede observarse, luego de realizar la demostración, que el secreto del acertijo consiste
entonces en que el producto de los números utilizados (143 y 7) es congruente a 1
módulo 1000. Teniendo en cuenta esto, el mismo podría modificarse utilizando por
ejemplo 91 y 11 como factores; o cualquier otro par de números cuyo producto sea
congruente a 1 módulo 1000. También, por ejemplo, se podría trabajar con las dos
últimas cifras y buscar productos congruentes a 1 módulo 100.
Ejercicio 46.
Probar que cualesquiera sean a Z y k  N, se verifica que 3 /[ a . (a 2 k  1)]
Resolución.
Página 8 de 14
 Como a es cualquier número entero y lo que se desea es comprobar la divisibilidad por
3 de una expresión que involucra a a, puede ser útil comenzar por analizar qué sucede
con a al dividirlo por 3.
Cualquiera sea a Z, al dividirlo por 3, se ubica en alguno de estos tres casos:
- a tiene resto 0
- a tiene resto 1
- a tiene resto 2
Expresado utilizando congruencia módulo 3, los casos son:
- a  0 (3)
- a  1 (3)
- a  2 (3)
 Se demostrará que 3 /[ a . (a 2 k  1)] en cada uno de los casos.
- Si a  0 (3) , entonces 3 / a y por lo tanto 3 divide también a a multiplicado por
-
-
cualquier entero (P1); luego, 3 /[ a . (a 2 k  1)] .
Si a  1 (3) , por propiedad de congruencia, se tiene que: a 2 k  12 k (3) cualquiera
sea k  N (P2), y 12k  1 (3) , de donde a 2 k  1 (3) ; luego, 3 /( a 2 k  1) y en
consecuencia: 3 /[ a . (a 2 k  1)] (P1).
Si a  2 (3) , entonces a 2  22 (3) (P2); como 4  1 (3) , resulta a 2  1 (3) y
elevando a la k, a 2 k  1 (3) (P2), cualquiera sea k  N. Por lo tanto, también en
este caso 3 /( a 2 k  1) y en consecuencia 3 /[ a . (a 2 k  1)] (P1).
 Propiedades utilizadas:
Cualesquiera sean a, b, c números enteros, n, m números naturales:
P1) Si b/a entonces b/a.c
P2) Si a  b (n) , entonces a m  b m (n)
Ejercicio 47.
Cualquiera sea el número natural n , ¿cuál es el resto de
por 6?
n (n  1) (2n  7)
al dividirlo
Resolución.
 Para conjeturar cuál es el resto que se pide, se puede comenzar por tomar algunos
valores particulares para n y calcular el resto de n (n  1) (2n  7) al dividirlo por 6.
De este modo, se observa que el resto, en cualquier ejemplo, es 0.
Pero que esto ocurra en cualquier caso particular que a uno se le puedan ocurrir, no es
demostración de este hecho. Habrá que demostrar que esto ocurre en todos los casos.
Página 9 de 14
 Se demuestra:
Para demostrar que el resto de la división es 0, habrá que probar que
6/ n (n  1) (2n  7) .
Como 6=2.3, y teniendo en cuenta que 2 y 3 son coprimos, será suficiente (P1) probar:
i)
2/ n (n  1) (2n  7)
ii)
3/ n (n  1) (2n  7)
(Así el problema queda reducido a casos más simples)
i)
Para esto se consideran los posibles restos de dividir a n por 2, y a partir de allí se
analizará el resto de la expresión dada.
Al dividir a n por 2, los restos posibles son 0 y 1, es decir que se considerarán los
casos: n par y n impar.
-Si n es par, entonces 2/n y por lo tanto 2 divide a n por cualquier otro entero (P2),
es decir, 2/ n (n  1) (2n  7) .
-Si n es impar, entonces n+1 es par. Así, 2/(n+1) y por (P2) resulta también en este
caso que 2/ n (n  1) (2n  7) .
ii)
Para demostrar que 3/ n (n  1) (2n  7) , se analizarán los tres posibles casos que
corresponden a los restos (que son 0, 1 ó 2) de dividir a n por 3.
-Si n tiene resto 0 al dividirlo por 3, entonces 3/n y por (P2) 3/ n (n  1) (2n  7)
-Si n tiene resto 1 al dividirlo por 3, entonces n  1 (3) .
Luego: 2n  7  2.1  7 (3) , por (P3) y (P4), es decir, 2n  7  0 (3) , lo que
indica que 3/( 2n  7 ) y, en consecuencia, 3/ n (n  1) (2n  7) (P2)
-Si n tiene resto 2 al dividirlo por 3, entonces n  2 (3) .
Luego: n  1  2  1 (3) (P4), es decir, n  1  0 (3) , lo que indica que 3/( n  1 )
y, por (P2), también en este caso resulta que 3/ n (n  1) (2n  7) .
Analizados todos los casos posibles, y habiendo probado la conclusión enunciada en cada
uno de ellos, se demostró entonces que para todo número natural n , el resto de
n (n  1) (2n  7) al dividirlo por 6 es cero.
 Propiedades utilizadas:
Cualesquiera sean a, b, c números enteros, y n número natural:
P1) Si mcd(a,b)=1, a/c y b/c, entonces a.b/c
P2) Si b/a, entonces b/a.c
P3) Si a  b (n) , entonces a.c  b.c (n)
P4) Si a  b (n) , entonces a  c  b  c (n)
En general, no hay una única demostración posible.
Página 10 de 14
 En este ejercicio, una demostración, que es esencialmente diferente de la anterior, es la
siguiente:
Se aplicará el principio de inducción, para lo cual se considera la función proposicional
con universal N (conjunto de números naturales):
P(n): 6/ n (n  1) (2n  7)

Base inductiva:
P(1):

Paso inductivo:
h  N: P(h)  P(h+1)
Suponiendo verdadera
se quiere probar
6/1. 2. 9
es una proposición verdadera pues 18=6. 3
P(h): 6/ h (h  1) (2h  7)
P(h+1): 6/ (h  1) (h  2) (2(h  1)  7)
Se prueba:
(h  1) (h  2) (2(h  1)  7) = (h  1) (h  2) (2h  2  7)
= (h  1) h (2h  2  7)  (h  1) 2 (2h  2  7)
= h (h  1) (2h  7  2)  (h  1) 2 (2h  2  7)
= h (h  1) (2h  7)  h (h  1) 2  (h  1) 2 (2h  9)
= h (h  1) (2h  7)  2 (h  1) (h  2h  9)
= h (h  1) (2h  7)  2 (h  1) ( 3h  9)
= h (h  1) (2h  7)  6 (h  1) (h  3)
(distributiva)
(conmutativa)
(distributiva)
(factor común)
(factor común)
Como 6/ h (h  1) (2h  7) por hipótesis inductiva, y 6/ 6 (h  1) (h  3) ,
resulta que
6/[ h (h  1) (2h  7)  6 (h  1) (h  3) ]
es decir que
6/ (h  1) (h  2) (2(h  1)  7)
como se quería probar.
Demostrados base y paso inductivo, se concluye que la afirmación
n  N: 6/ n (n  1) (2n  7) es verdadera.
Ejercicio 48.
Sea p primo positivo y a entero. ¿Qué conclusión puede obtenerse de la siguiente
afirmación?
( p / a)  a  a ( p)
Resolución.
Página 11 de 14
 Para obtener alguna conclusión a partir de una afirmación, ésta debe asumirse verdadera
(jugará el papel de única premisa de un razonamiento válido del cual se quiere hallar la
conclusión).
 Como la afirmación dada es un condicional,
por equivalencia lógica del mismo
( (s  t)  (s  t) ),
y por doble negación
(aplicada al antecedente),
resulta verdadero:
p / a  a  a ( p )
 Obsérvese que a  a ( p)  p / 2a  ( p / 2  p / a )
(esta última equivalencia se debe a que p es primo, y por lo tanto, si divide a un
producto, entonces divide a alguno de los factores)
 En consecuencia, será verdadera la afirmación siguiente:
p / a  ( p / 2  p / a)
Por conmutatividad, asociatividad e idempotencia para la disyunción, resulta:
p/a  p/2
Siendo p primo positivo, será entonces finalmente la conclusión:
p/a  p  2
Ejercicio 49.
Hallar todos los enteros m que verifican:
a) 13 /(15m  6)75
b) 17 /( m2  1)
c) el resto de dividir 24m por 15 es 12.
Resolución.
a) Como 13 es primo, si se verifica que
13 /(15m  6)75 ,
13 /(15m  6)
entonces resulta:
15m  6  0 (13)
Esto puede expresarse:
Como 15  2 (13) :
2m  6 (13)
2m  7 (13)
y como  6  7 (13) :
(P1)
(P2)
Luego, basta resolver esta ecuación de congruencia, que tiene solución (única en Z13 ),
pues mcd(2,13)=1.
Se resuelve:
mcd(2,13)= 1=2.(- 6) +13.1

7=2.(- 42)+13.7
Página 12 de 14
7  2.(42) (13)

Como  42  10 (13) , resulta: 2.10  7 (13) . Luego, m=10 es una solución de la
ecuación. Por lo tanto, todas las soluciones enteras son: m  10  13k, k  Z .
b) Si se verifica que 17 /( m2  1) entonces m2  1  0 (17)
(P2)

m2  1 (17)
2

m  16 (17) (pues  1  16 (17) y la relación es transitiva)

17 /( m2  16)
17 /( m  4)( m  4)

17 /( m  4)  17 /( m  4)
( 17 es primo) (P3)

m  4 (17)  m  4 (17)

m  4 (17)  m  13 (17)
(  4  13 (17) )

Por lo tanto, todas las soluciones enteras son:
m  4  17k, k  Z
 m  13  17k, k  Z
c) Si se verifica que 24m tiene resto 12 al dividirlo por 15, entonces: 24m  12 (15)
Como mcd(24,15)= 3 y 3/12, esta ecuación de congruencia tiene solución (tres
soluciones diferentes en Z15 ).
24m  12 (15)
Se resuelve:
 15 /( 24m  12)
 3.5 / 3.(8m  4)
(P4)
 5 /(8m  4)
mcd(8,5)= 1=8.2 +5.(- 3)
 8m  4 (5)
 4=8.8+5.(-12)
4  8.8 (5)

Como 8  3 (5) resulta: 8.3  4 (5) .
Luego, m=3 es una solución de la ecuación 8m  4 (5) . Por lo tanto, todas las
soluciones enteras de 8m  4 (5) son: m  3  5k, k  Z .
En consecuencia, las tres soluciones de 24m  12 (15) en Z15 son:
3; 3+5; 3+5.2, es decir: 3; 8 y 13.
O bien, expresado de otra manera, todas las soluciones enteras de la ecuación
24m  12 (15) son:
m  3  15k, k  Z
 m  8  15k, k  Z
 m  13  15k, k  Z
 Se enuncian a continuación propiedades utilizadas:
Cualesquiera sean a, b, c, p números enteros, n número natural:
Página 13 de 14
P1) Si p es primo y p/ a n , entonces p/a
P2) Si a  b (n) , entonces a  c  b  c (n)
P3) Si p es primo y p/a.b, entonces p/a  p/b
P4) Si a.b /a.c, entonces b/c
Ejercicio 50.
a) Analizar qué determina la salida “verdadero” o “falso” del siguiente algoritmo
Paso 1) Entrada de dato: m, número natural mayor que 2
Paso 2) Se inicializa contador i:=2
Paso 3) Si i divide a m, entonces ir a paso 4); si no, i:=i+1 e ir a paso 5)
Paso 4) Salida:”falso”. Finaliza.
Paso 5) Si i  m-1, entonces ir a paso 3); si no, salida: “verdadero”. Finaliza.
b) Demostrar que, si k es el mayor entero que verifica k  m , entonces, en el algoritmo
anterior, se obtendría la misma conclusión si i tomara el valor 2 o fuese cualquier entero
impar tal que 1< i  k.
c) Probar que si m, número natural mayor que 1, no es divisible por ningún primo positivo
p  m , entonces m es primo.
Resolución.
a) Puede observarse que se obtiene salida “verdadero” sólo cuando ningún i divide a m,
para los valores de i: 2  i  m  1. En cambio, si m es divisible por alguno de estos
valores de i, inmediatamente se obtiene salida “falso”. ¿Qué información sobre el dato
de entrada m está dando este algoritmo? Evidentemente tiene que ver con los divisores
de m.
En el caso de salida “verdadero”, ¿cuáles son los divisores posibles del número m?
Si se buscan divisores positivos de m, no puede ser ninguno entre 2 y m-1; luego, los
únicos divisores positivos resultan ser 1 y m (divisores triviales), pues m no tiene
divisores mayores que m (P1).
Así, la salida “verdadero” indica que los únicos divisores de m son los triviales,
mientras que la salida “falso” se produce cuando m admite otros divisores. Por lo tanto
este algoritmo determina si m es primo (“verdadero”) o no (“falso”).
Propiedad:
(P1) Si a, b son números naturales y a/b, entonces a  b.
b) Lo que quiere demostrar en este caso, es que basta con comprobar que m no es divisible
por 2 ni por los impares entre 3 y k, para poder asegurar que m es primo. (Observar que
se reduce el número de comprobaciones con respecto al caso anterior).
Página 14 de 14
Se demuestra:
Sea q  N un divisor de m, entonces m = q.h, con h  N . También h resulta ser divisor
de m. Se prueba que alguno de ellos, q o h, es menor o igual que m , pues: si fuese
q  m y h  m , entonces resultaría m  q.h  m . m  m , que es un absurdo.
Por lo tanto , q  m  h  m . Pero entonces, por la forma en que se definió el
número k, resulta que q  k  h  k. En cualquier caso, existe un divisor natural de m
(que puede ser q o h) que verifica que es menor o igual que k.
Pero entonces este divisor:
- no puede ser par porque resultaría m divisible por 2 y se está suponiendo que no
- si es impar, como es menor o igual que k, no puede ser mayor que 1, pues se está
asumiendo que m no tiene divisores de este tipo
En consecuencia, este divisor sólo puede ser igual a 1. Entonces se tiene que q=1 
h=1, o , lo que es lo mismo, q=1  q=m.
En definitiva, si m tiene algún divisor natural q, resulta que éste es un divisor trivial; se
ha probado entonces que m es primo.
c) El problema aquí planteado es del tipo de los anteriores, pero se reduce aún más la
cantidad de comprobaciones de divisibilidad que hay que hacer para confirmar que m es
primo.
Se demuestra:
Sea q  N un divisor de m. Según lo desarrollado en el item anterior, puede asegurarse
que existe un divisor natural de m (que puede ser q o h) que verifica que es menor o
igual que m .
Si este divisor no fuese igual a 1, por el teorema fundamental de la aritmética, admitiría
un divisor p, primo positivo.
Luego, p sería divisor de m (por ser divisor de un divisor de m) y p  m (por P1 y
transitividad de la relación  ), y p primo positivo. Pero esto contradice los datos, que
indican que m no tiene divisores de este tipo.
La contradicción proviene de suponer que el divisor (que puede ser q o h) de m no es
igual a 1.
Por lo tanto resulta: q=1  h=1, o , lo que es lo mismo, q=1  q=m.
En definitiva, si m tiene algún divisor natural q, resulta ser un divisor trivial; se ha
probado entonces que m es primo.