• Author / Uploaded
• Piero Alonso

Citation preview

1.- Antecedentes A continuación se presenta un breve resumen de la historia de la divisibilidad en la que se destaca lo más característico de su evolución hasta Euler. Precursores en la matemática 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 matemática griega, a través de la obra de Euclides (300 a.C.) “Elementos”, en particular, con los volúmenes VII, VIII y IX (de los trece que elaboro), en los que por medio de proposiciones formuladas en términos de medida establece: - Un procedimiento llamado “antenaresis” (Algoritmo de Euclides) para calcular el máximo común divisor de dos o más números. - Propiedades de la divisibilidad. - Propiedades de los números primos entre sí a partir de las proposiciones. En el libro IX además se incluye la proposición que establece que el conjunto de los números primos es infinito “Hay más números primos que cualquier cantidad propuesta de números primos”, junto con proposiciones próximas al Teorema Fundamental de la Aritmética pero sin concebirlo como tal ya que no concebían la matemática independiente de la construcción. En el siglo XVI, debido a las necesidades tecnológicas, científicas y mercantiles, se mejoraron los métodos operativos. Steven (1548-1620) hizo aportaciones a la física, matemática, música, semiología y contabilidad, al que se le debe la extensión de la Teoría de la Divisibilidad ya que en su obra publicada en 1634 “OEuvres mathematiques...” extiende el algoritmo de Euclides al cálculo del máximo común divisor de dos polinomios.

Pierre de Fermat (1601-1665) tras el estudio de la obra de Diofanto de Alejandría (siglo III d.C.), se inspiró e hizo grandes aportaciones al estudio de la Teoría de Números (y a otras ramas de la matemática). De entre sus resultados más conocidos hay que destacar el “Pequeño 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 números 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 distribución de los números primos con sus ideas del análisis matemático. Demostró la divergencia de la suma de los inversos de los números primos y, al hacerlo, descubrió la conexión entre la función zeta de Riemann y los números primos, lo que se conoce como el producto de Euler para la función zeta de Riemann. Euler también demostró las identidades de Newton, el pequeño teorema de Fermat y el teorema de Fermat sobre la suma de dos cuadrados. También definió la función φ de Euler que, para todo numero entero positivo n, cuantifica el número de enteros positivos menores o iguales a n y coprinos con n. Más tarde, utilizando las propiedades de esta función, generalizo el pequeño teorema de Fermat a lo que se conoce como el teorema de Euler Después de Fermat, la Teoría de Números permaneció sin muchos progresos por un siglo, hasta la llegada del gran matemático suizo Leonhard Euler, quien nació en 1707 en Basilea. A la edad de 14 años, ingresa a la Universidad de Basilea, en donde recibe clases del célebre matemático Johan Bernoulli I. Demostrando su genialidad desde temprana edad, publica su primer resultado sobre Matemática a los 18 años. En 1726 es llamado a la Academia de San Petersburgo, donde se le ofrece un cargo de profesor. Allí, además de enseñar Matemática, investiga mucho en ciencias aplicadas como física, ingeniería, navegación, construcción naval y cartografía. Luego, en 1741, se traslada a la Academia de Ciencias de Berlín, 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 Definición: Función indicatriz de Euler. La función φ de Euler (también llamada Función indicatriz de Euler) es una función importante en teoría de números. Si n es un número entero positivo, entonces φ(n) se define como el número de enteros positivos menores o iguales a n y coprimos con n. Se define como:

φ ( m )=¿ { nϵ N∨n ≤ m ∧mcd ( m , n )=1 } ∨¿

Donde |.| significa la cantidad de números que cumplen la condición Primeras propiedades y cálculo de la función: Se sigue de la definición que φ ( 1 )=1, pues el elemento {1} sólo puede ser primo relativo consigo mismo. Por tanto existe un elemento. Y que: 1.

φ ( p )= p−1, si p es primo. Cierto porque un número primo es coprimo con todos sus anteriores. Y, por tanto, existe p-1 elementos coprimos con p.

2.

φ ( pk ) =( p−1) pk−1 si p es primo y k es un número natural. Se demuestra con inducción:

1 0 Supongamos k =1, φ ( p ) =φ ( p )=( p−1 ) p =p−1 es cierto,

k k−1 Supongamos cierto (Hipótesis I.) φ ( p ) =( p−1) p . Probemos que se cumple

φ ( pk +1 )=( p−1) pk

luego

( p−1) p k =( p−1) pk−1 p

y por hipótesis inducción afirmamos,

( ( p−1 ) pk−1 ) p=φ ( p k ) p . Como φ ( pk ) son los números coprimos con pk

si lo

multiplicamos por p se añaden los p números que faltaban para encontrar el valor de

p φ( ¿¿ k +1) . ¿ k k+1 Así vemos que φ ( p ) p=φ ( p ) .

3. φ es una función 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 Aritmética: si n=p 1 … . p r

Donde los pj son números primos distintos, entonces φ ( n ) =( p 1−1 ) p k1 1−1 … ( pr −1 ) p krr −1 . Esta última fórmula 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 cálculo:

( 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 números 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 descomposición

φ ( n ) =p r11 pr2 2 … . p rm m ( p1 −1 )( p 2−1 ) … .( pm−1) .

r1 r2 rm Demostración: Tenemos que φ(n)=p 1 p 2 … . pm

p φ(¿ ¿1 )φ( pr2 2 … . p rm m ) ¿¿ r1

rm−1

¿ pm

r2

rm

( p 1−1)φ( p 2 … . pm )

Siguiendo el proceso tenemos que: φ ( n ) =p r11 pr2 2 … . p rm m ( p1 −1 )( p 2 −1 ) … .( pm−1)

.

El otro concepto involucrado en el teorema de Euler es el de congruencia. En Teoría de Números, se dice que dos números a, b son congruentes respecto a un módulo n, cuando n divide al entero a-b. La congruencia de a, b respecto al módulo 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

función φ de Euler. Demostración 1: Considere a1, a2,…, a φ (n), los enteros positivos menores que n y primos relativos con n . Sea a cualquier número tal que mcd ( a , n ) =1 aa1, aa2,…, a aφ (n),

por el teorema anterior:

Son los primos relativos a

n

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 números a1, a2,…, a φ (n), es decir aφ (n ) (a1, a2,…, a φ (n)) ≡ (a1, a2,…, a φ (n)) mod

aa1, aa2,…, a aφ (n) = n.

Además, 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 cancelación de congruencias,

luego aφ(n) ≡ 1 (mod n). Demostración 2:

Consideremos un sistema reducido modulo Entonces como

( a , m )=1

sistema reducido módulo Por consiguiente a cada

el conjunto

mr =x 1 , x 2 , … , x φ(m) ar=ax 1 , ax 2 ,… , ax φ(m)

es también un

m .

xi ϵ r

le corresponde un solo ax i ϵ ar

tal que

x i ≡ ax j (modm) Además, a elementos diferentes de R, le corresponderán 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 cancelación de

congruencias obtenemos que aφ(n) ≡ 1 (mod n).

4.- Aplicaciones Ejemplo: Determine los valores enteros y positivos de c que son solución de la ecuación

φ(40)

33

+c ≡3 mod 40.

Solución: 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 número de este tipo es lo que garantiza la seguridad del método.

5.- Bibliografía|



Javier Cobos Gavala, (2001). Introducción a la Matemática Discreta.



Cristina Martín Gonzales, (2012). Divisibilidad de números naturales Múltiplos y divisores.



Murillo, M; González, J. (2006). Teoría de los Números. Cartago, Costa Rica. Editorial Tecnológica de Costa Rica. Páginas 167-194.



Number Theory in Science and Communication Prof. Dr. Manfred Schroeder Universit ¨at G¨ottingen 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., Introducción a la Teoría Analítica de Números, Reverté, S. A.,



Theory,



http://es.wikipedia.org/wiki/Teorema_de_Euler.



http://es.wikipedia.org/wiki/Peque%C3%B1o_teorema_de_Fermat_Euler