1.
- Antecedentes
A continuacin se presenta un breve resumen de la historia de la divisibilidad en la que
se destaca lo ms caracterstico de su evolucin hasta Euler.
Precursores en la matemtica antigua
Los conceptos relacionados con la divisibilidad se conocen desde la prehistoria con el
descubrimiento del hueso de Ishango que representa el ciclo de un calendario lunar de
seis meses. Posteriormente, tanto en el antiguo Egipto como en Mesopotamia, se
emplearon los conceptos de divisibilidad para resolver problemas de medida cuantos
caben en.
La matemtica griega, a travs de la obra de Euclides (300 a.C.) Elementos, en
particular, con los volmenes VII, VIII y IX (de los trece que elaboro), en los que por
medio de proposiciones formuladas en trminos de medida establece:
- Un procedimiento llamado antenaresis (Algoritmo de Euclides) para calcular el
mximo comn divisor de dos o ms nmeros.
- Propiedades de la divisibilidad.
- Propiedades de los nmeros primos entre s a partir de las proposiciones.
En el libro IX adems se incluye la proposicin que establece que el conjunto de los
nmeros primos es infinito Hay ms nmeros primos que cualquier cantidad propuesta
de nmeros primos, junto con proposiciones prximas al Teorema Fundamental de la
Aritmtica pero sin concebirlo como tal ya que no conceban la matemtica
independiente de la construccin.
En el siglo XVI, debido a las necesidades tecnolgicas, cientficas y mercantiles, se
mejoraron los mtodos operativos. Steven (1548-1620) hizo aportaciones a la fsica,
matemtica, msica, semiologa y contabilidad, al que se le debe la extensin de la
Teora de la Divisibilidad ya que en su obra publicada en 1634 OEuvres
mathematiques... extiende el algoritmo de Euclides al clculo del mximo comn
divisor de dos polinomios.
Pierre de Fermat (1601-1665) tras el estudio de la obra de Diofanto de Alejandra (siglo
III d.C.), se inspir e hizo grandes aportaciones al estudio de la Teora de Nmeros (y a
otras ramas de la matemtica). De entre sus resultados ms conocidos hay que destacar
el Pequeo teorema de Fermat: Para todo numero primo p y para todo numero natural a
no divisible por p tenemos que p divide a ap-1-1. Y el Ultimo teorema de Fermat: No
es posible encontrar cuatro nmeros naturales x, y, z, n para n>2, tales que xn+yn=zn.
Este ltimo lo escribi en el margen del libro al estudiar el problema de Diofanto de
descomponer un cuadrado en suma de dos cuadrados. Este teorema fue demostrado para
el caso general por Andrew Wiles en 1993.
Euler (1707-1783) uni la naturaleza de la distribucin de los nmeros primos con sus
ideas del anlisis matemtico. Demostr la divergencia de la suma de los inversos de los
nmeros primos y, al hacerlo, descubri la conexin entre la funcin zeta de Riemann y
los nmeros primos, lo que se conoce como el producto de Euler para la funcin zeta de
Riemann.
Euler tambin demostr las identidades de Newton, el pequeo teorema de Fermat y el
teorema de Fermat sobre la suma de dos cuadrados. Tambin defini la funcin de
Euler que, para todo numero entero positivo n, cuantifica el nmero de enteros positivos
menores o iguales a n y coprinos con n. Ms tarde, utilizando las propiedades de esta
funcin, generalizo el pequeo teorema de Fermat a lo que se conoce como el teorema
de Euler
Despus de Fermat, la Teora de Nmeros permaneci sin muchos progresos por un
siglo, hasta la llegada del gran matemtico suizo Leonhard Euler, quien naci en 1707
en Basilea. A la edad de 14 aos, ingresa a la Universidad de Basilea, en donde recibe
clases del clebre matemtico Johan Bernoulli I. Demostrando su genialidad desde
temprana edad, publica su primer resultado sobre Matemtica a los 18 aos. En 1726 es
llamado a la Academia de San Petersburgo, donde se le ofrece un cargo de profesor.
All, adems de ensear Matemtica, investiga mucho en ciencias aplicadas como fsica,
ingeniera, navegacin, construccin naval y cartografa. Luego, en 1741, se traslada a
la Academia de Ciencias de Berln, invitado por el Rey Federico el Grande de Prusia.
En esta academia permaneci hasta 1766 cuando la Reina Catalina II de Rusia lo llama
nuevamente a la Academia de San Petersburgo, donde permanece hasta su muerte en
1783.
2.- Preliminares
Definicin: Funcin indicatriz de Euler.
La funcin de Euler (tambin llamada Funcin indicatriz de Euler) es una funcin
importante en teora de nmeros. Si n es un nmero entero positivo, entonces (n) se
define como el nmero de enteros positivos menores o iguales a n y coprimos con n.
Se define como:
( m )= { n Nn m mcd ( m , n )=1 }
Donde |.| significa la cantidad de nmeros que cumplen la condicin
Primeras propiedades y clculo de la funcin:
Se sigue de la definicin que ( 1 )=1, pues el elemento {1} slo puede ser primo
relativo consigo mismo. Por tanto existe un elemento. Y que:
1.
( p )= p1, si p es primo. Cierto porque un nmero primo es coprimo con
todos sus anteriores. Y, por tanto, existe p-1 elementos coprimos con p.
2.
( pk ) =( p1) pk1 si p es primo y k es un nmero natural.
Se demuestra con induccin:
1
0
Supongamos k =1, ( p ) = ( p )=( p1 ) p =p1 es cierto,
k
k1
Supongamos cierto (Hiptesis I.) ( p ) =( p1) p
. Probemos que se cumple
( pk +1 )=( p1) pk
luego
( p1) p k =( p1) pk1 p
y por hiptesis induccin afirmamos,
( ( p1 ) pk1 ) p= ( p k ) p . Como ( pk ) son los nmeros coprimos con pk
si lo
multiplicamos por p se aaden los p nmeros que faltaban para encontrar el valor de
p
( k +1) .
k
k+1
As vemos que ( p ) p= ( p ) .
3. es una funcin multiplicativa condicional: si m y n son primos entre s,
entonces
( mn )= ( m ) ( n ) .
Con esto, el valor de ( n)
puede calcularse empleando el teorema fundamental de la
k1
kr
Aritmtica: si n=p 1 . p r
Donde los pj son nmeros primos distintos, entonces
( n ) =( p 11 ) p k1 11 ( pr 1 ) p krr 1 .
Esta ltima frmula es un producto de Euler y a menudo se escribe como
1
p
()
.
( n ) =n
1
p /n
Donde los p son los distintos primos que dividen a n.
Ejemplo de clculo:
( 13 )(1 12 )=36. 23 . 12 =12
( 36 ) = ( 32 22) =36 1
( 13 )(1 17 )=21. 23 . 67 =12
( 21 )= ( 3.7 )=21 1
Se puede comprobar manualmente que los nmeros coprimos con 36 (o sea, que no son
divisibles por 2 ni por 3) son doce: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, y 35.
r1 r 2
rm
Teorema: Sea n un entero positivo y sea n=p 1 p2 . p m
prima de n entonces
la descomposicin
( n ) =p r11 pr2 2 . p rm
m ( p1 1 )( p 21 ) .( pm1) .
r1 r2
rm
Demostracin: Tenemos que (n)=p 1 p 2 . pm
p
( 1 )( pr2 2 . p rm
m )
r1
rm1
pm
r2
rm
( p 11)( p 2 . pm )
Siguiendo el proceso tenemos que:
( n ) =p r11 pr2 2 . p rm
m ( p1 1 )( p 2 1 ) .( pm1)
El otro concepto involucrado en el teorema de Euler es el de congruencia. En Teora de
Nmeros, se dice que dos nmeros a, b son congruentes respecto a un mdulo n, cuando
n divide al entero a-b. La congruencia de a, b respecto al mdulo n se simboliza como a
b (mod n).
3.- El Teorema de Euler
Si a y n son enteros primos relativos, entonces a(n) 1 (mod n),
donde (n) es la
funcin de Euler.
Demostracin 1:
Considere a1, a2,, a (n), los enteros positivos menores que n y primos relativos
con n . Sea a cualquier nmero tal que mcd ( a , n ) =1
aa1, aa2,, a a (n),
por el teorema anterior:
Son los primos relativos a
y no hay dos de ellos que sean congruentes entre s
modulo n . Por lo tanto, estos ltimos deben ser congruentes, con un reordenamiento,
a los nmeros a1, a2,, a (n), es decir
a (n ) (a1, a2,, a (n)) (a1, a2,, a (n)) mod
aa1, aa2,, a a (n) =
n.
Adems, como el mcd (a1, a2,, a (n), n)= 1 pues para todo, i tenemos que
mcd(ai,n) = 1
y as, podemos aplicar la ley de cancelacin de congruencias,
luego a(n) 1 (mod n).
Demostracin 2:
Consideremos un sistema reducido modulo
Entonces como
( a , m )=1
sistema reducido mdulo
Por consiguiente a cada
el conjunto
mr =x 1 , x 2 , , x (m)
ar=ax 1 , ax 2 , , ax (m)
es tambin un
m .
xi r
le corresponde un solo ax i ar
tal que
x i ax j (modm)
Adems, a elementos diferentes de R, le correspondern elementos diferentes
de ar , por tanto, ax 1 , ax 2 , , ax (m ) , son congruentes con x 1 , x 2 , , x (m)
Modulo m (no necesariamente en ese orden).
Luego, ax 1 , ax 2 , , ax (m ) x1 , x 2 , , x (m ) ( modm )
x
(m)
1
,
x
,
,
x
(
x 1 , x 2 , , x (m ) ( modm )
2
(m) ) a
x
y como ( 1 , x 2 , , x (m) , m)=1
y aplicando la ley de la cancelacin de
congruencias obtenemos que a(n) 1 (mod n).
4.- Aplicaciones
Ejemplo: Determine los valores enteros y positivos de c que son solucin de la
ecuacin
(40)
33
+c 3 mod 40.
Solucin:
Como
33(40) 1 mod 40
k =1,2,3 .
CRIPTOGRAFIA
mcd ( 33,40 )=1 , utilizando el teorema de Euler, se tiene que
y se debe cumplir que
c 2 mod 40 , as,
c=40 k +2
con
La imposibilidad de poder factorizar un nmero de este tipo es lo que garantiza la
seguridad del mtodo.
5.- Bibliografa|
Javier Cobos Gavala, (2001). Introduccin a la Matemtica Discreta.
Cristina Martn Gonzales, (2012). Divisibilidad de nmeros naturales Mltiplos
y divisores.
Murillo, M; Gonzlez, J. (2006). Teora de los Nmeros. Cartago, Costa Rica.
Editorial Tecnolgica de Costa Rica. Pginas 167-194.
Number Theory in Science and Communication Prof. Dr. Manfred Schroeder
Universit at Gottingen Inst. Physik III Friedrich-Hund-Platz 1
Nathanson, Melvyn B., (2000), Elementary Methods in Number
editorial Board, USA.
Dickson, Leonard Eugene, (1919), History of Numbers, Volumen I,
Divisibility and Primality, No. 256, The Carnegie Institution of
Washington, Washigton.
Apostol, Tom M., Introduccin a la Teora Analtica de Nmeros,
Revert, S. A.,
Theory,
[Link]
[Link]