DISTINTAS FUNCIONES EN MATEMÁTICA DISCRETA, SU IMPORTANCIA Y PROPIEDADES. Ángel Gabriel Broder – María del Luján Digiovani Universidad Autónoma de Entre Ríos – Facultad de Ciencia y Tecnología [email protected] [email protected] Eje temático: Matemática discreta. Investigación: El curriculum de Matemática en el Profesorado de Matemática.

Es conveniente apreciarel valor tecnológico de la Matemática en este siglo, puesto que se vive en plena era del conocimiento, o era digital. Al alcance de todos está la tecnología digital o la llamada “era digital” (computadoras, cámaras digitales, teléfonos celulares, MP3, MP4, etc.). Nadie duda en cuanto a los usos de la computadora, pero quién se imagina cuando está hablando por el celular cuánta Matemática está involucrada en ese proceso y cómo opera la Teoría Algebraica de la Codificación para que el mensaje llegue con tanta nitidez. Todos usamos tarjetas de débito, operamos contarjetas de crédito, se hacen compras por Internet, pero no tenemos presente que allí intervienen la Codificación, la Comprensión de Datos y la Criptografía. Pues bien, la Matemática está allí, pero es la llamada Matemática Discreta, que está en el fundamento de todas las modernas Teorías de la Información y de la Comunicación (las famosas TICs). En el Profesorado en Matemática dentro de los contenidos de Matemática Discreta, se estudian temas de la Teoría Elemental de Números, teoría que estudia las propiedades de los enteros. Dichos números constituyeron el primer descubrimiento matemáticoy el interés en ese conjunto numérico es tan antiguo como la misma civilización. Los retosintelectuales de los problemas de la teoría de números han atraído a matemáticos desde la época de Pitágoras (540 a.c.) y el trabajo realizado en la búsqueda de soluciones a dichos problemas ha resultado en lacreación de nuevas ramas de la matemática. En estas últimas décadas con el advenimiento de las computadoras la Teoría de Números resultó muy relevante para dar soluciones a problemas prácticos. Al estudiar la teoría elemental de números aparecen varias funciones con propiedades útiles (la 1 2 función sigma, la función phi de Euler , la funciónµ de Möbius , la función tau, entre las que veremos) pero frecuentemente en las introducciones a la teoría de números se presentan de forma bastante inconexa. Aquí veremos que pueden obtenerse sistemáticamente y que muchas de las demostraciones, aunque puedan ser algo laboriosas, se reducen a cálculos cuyos resultadosson muchas veces previsibles de antemano. Una de las aplicaciones de las funciones multiplicativas lo constituye eldiseño de esquemas criptográficos modernos de clave pública, a la cual dedicamos un apartado. Por otro lado, el uso del lenguaje simbólico ha estimulado la aplicación de técnicas computacionales aproblemas de teoría de números; en este trabajo las ilustraremos. El material presupone solamente un conocimiento básico de la notacióny nociones de teoría de números, provenientes de un curso introductorio de matemática discreta, dentro del curriculum de los Profesorados de Matemática. Funciones aritméticas. Una propiedad importante que le pedimos a una función aritmética es que sea sea multiplicativa, “una función G es multiplicativa si , para a y b naturales y coprimos”. Esta propiedad permite explotar el hecho de que los números pueden factorizarse como producto de potencias de números primos y, tal como aquí se muestra, esto es suficiente para justificar la definición y el estudio de todas estas funciones. Una de las aplicaciones de las funciones multiplicativas lo constituye el diseño de esquemas criptográficos modernos de clave pública. Se mostrará en este trabajo las definiciones de estas funciones, las relaciones entre ellas, algunas aplicaciones y las propiedades más sobresalientes. • φ(n): Función Indicadora de Euler que cuenta la cantidad de números coprimos menores que n. • µ(n): la función de Möbius, relacionada con el número de factores primos de los números no divisibles por un cuadrado perfecto. • τ(n) = d(n): el número de divisores positivos de n. 1

Leonhard Paul Euler (1707 – 1783): matemático y físico suizo, vivió en Rusia y Alemania la mayor parte de su vida y realizó importantes descubrimientos en áreas tan diversas como el Cálculo y la Teoría de Grafos. 2 August Ferdinand Möbius (1790 – 1868): matemático y astrónomo alemán. Es considerado como el pionero de la Topología, ya que en sus trabajos matemáticos anticipó muchos conceptos de la moderna Geometría Proyectiva, en especial la algebraica.

• σ(n): la suma de todos los divisores positivos de n. 1. La Función Phi (φ) o Función Indicadora de Euler. Definición: Para cada de Euler se define por

, la función φ

φ(n) = Es decir que “cuenta” la cantidad de enteros positivos k menores o iguales que n, coprimos con n. Esta función aparece en varias demostraciones importantes relacionadas con la Teoría de Grupos, tiene una fuerte relación con las fracciones irreducibles. Por otro lado, siempre es interesante recordar que este resultado tan simple es la base de los algoritmos aplicados a criptografía, tema tan importante para mantener nuestras comunicaciones secretas. Propiedades: • Multiplicativa: Si mcd(a, b) = 1: φ(ab) = φ(a)φ(b) • Si p es primo y k > 0: φ(pk) = pk – pk-1. • φ(n) es par si n ≥ 3. •

Para todo

, se tiene que

• Teniendo en cuenta estas propiedades, y sabiendo que todo entero positivo n se puede factorizar de manera única mediante el Teorema Fundamental de la Aritmética podemos calcular el valor que toma la Función Phi de Euler para dicho n. Recordando el Teorema Fundamental de la Aritmética: si n es un entero positivo entonces existen números enteros positivos primos diferentes y enteros positivos . Además esta factorización es única, salvo por el orden de tales que los factores. de una manera sencilla: Esto nos permite determinar

Para distintos valores de n se puede construir la tabla para esta función y su representación gráfica: n 1 2 3 4 5 6 7 8 9 10 1 1 2 2 4 2 6 4 6 4 φ(n) A continuación se muestra en la Figura Nº1 el gráfico de la función primeros enteros positivos.

para los primeros diez

Figura Nº1: Gráfico de la función Phi de Euler 2. La Función Tau ( ). Para todo número entero positivo n se define la función tau de n como el número de divisores positivos de n. Esta función se denota por la letra griega τ . Simbólicamente: Ejemplo: el número 12 tiene como divisores positivos: 1,2,3,4,6,12. Es decir, tiene 6 divisores, por lo tanto τ (12) = 6.

Propiedades: • La función •

τ (n) es multiplicativa α Si p es un número primo τ ( p ) = α + 1 .

• Como la función es multiplicativa entonces • es impar sii n es un cuadrado perfecto 14 Desafío: enumerar los divisores de 3 .Por la propiedad anterior la cantidad de divisores de es igual a 15. Ellos son:1; 3; 9; 27; 81; 243; 729; 2.187; 6.561; 19.683; 59.049; 177.147; 531.441; 1.594.323; 4.782.969. Ejemplo:

τ (108)

Para distintos valores de n se puede construir la tabla para esta función y seguidamente el gráfico de la Función Tau para los diez primeros números enteros positivos. n

τ (n)

1 1

2 2

3 2

3. La Función Sigma (σ) Definición: Para cada

4 3

5 2

6 4

7 2

8 4

9 3

10 4

9 13

10 18

la función sigma se define por

Es decir, suma los divisores positivos de n. Ejemplos:Los divisores de 8 son: 1; 2; 4; 8, entonces Para distintos valores de n se puede construir la Tabla para esta función. 1 1 •

2 3

3 4

4 7

5 6

6 12

7 8

8 15

La función sigma de n está relacionada con el clásico problema de los números perfectos, que encierra temas abiertos en la Teoría de números: a) Determinar si existen infinitos números perfectos. Hasta abril del año 2013 se conocían 48 números perfectos.b) Demostrar la imposibilidad de un número perfecto impar o encontrar uno.

Decimos que un entero positivo n es perfecto si la suma de sus divisores menores que n coincide con n. Es decir, si σ(n) = 2n. El primer número perfecto es el 6 cuyos divisores son 1; 2; 3 y 6. El siguiente es 28 = 1 + 2 + 4 + 7 + 14. Propiedades: • La función sigma de n es multiplicativa • Si p es un número primo, entonces •

Si p es un número primo

•

Si n =

•

Si

r

∏i=1 piαi , entonces σ (n)= con

entonces

∏

r

i =1

p iα i +1 − 1 pi − 1

es impar

4. Función de Möbius. La Función de Möbius µ(n), nombrada así en honor a August Ferdinand Möbius, es una función multiplicativa estudiada en teoría de números y en combinatoria. Definición: µ(n) está definida para todos los números naturales n y toma valores en dependiendo de la factorización de n en sus factores primos. Se define como sigue: • µ(n) = 1 si n es libre de cuadrados y tiene un número par de factores primos distintos. • µ(n) = -1 si n es libre de cuadrados y tiene un número impar de factores primos distintos. • µ(n) = 0 si n es divisible por algún cuadrado.

Observaciones: a) Un número entero n es libre de cuadrados si no lo divide ningún cuadrado perfecto o bien 2 si no existe un número primo p tal que p divide a n. Así n = 22 = 2.11 es libre de 3 cuadrados, pero 24=2 ·5 no lo es, porque es divisible por un cuadrado perfecto (22). b) La definición implica que µ(1) = 1, ya que 1 tiene 0 factores primos distintos, por lo tanto, un número par. Algunas relaciones interesantes entre las funciones aritméticas mencionadas: • Para n entero positivo se tiene que:

•

Para todo

, se tiene que

• •

Si n es un número par:

• • •

n es primo si y sólo si

• • Aplicaciones:El Criptosistema RSA. El modelo fue desarrollado por Rivest, Shamir y Adleman, y se conoce con el nombre de Criptosistema RSA. El protocolo desarrollado por estos autores es el siguiente: 1. Cada usuario U elige dos números primos (actualmente se recomienda que tales números primos tengan más de 200 dígitos) p y q y calcula . El grupo a utilizar por el usuario U es, entonces, . El orden de este grupo es . Para U es fácil calcular este orden, pues conoce p y q. 2. Después, U selecciona un entero positivo e, , de modo que sea primo con el orden del grupo, es decir, de modo que . 3 3. Mediante el Algoritmo de Euclides Extendido calcula el inverso de e en

, d, se tiene

entonces que , con . 4. La clave pública del usuario U es la pareja , mientras que su clave privada es el número d. Por supuesto, también deben permanecer secretos los números p, q y . Si un usuario A desea enviar un mensaje m de a otro usuario B, utiliza la clave pública de B, , para calcular el valor de , que envía a B. Para recuperar el mensaje original, B calcula . Conclusiones.

3

Euclides (330 a.C. – 275 a.C.): Matemático griego. Poco se conoce a ciencia cierta de la biografía de Euclides pese a ser el matemática más famoso de la antigüedad.

El enfoque tradicional de la Enseñanza de Matemática Discreta en los Profesorados de Matemática no incluye este tipo de funciones, o si se hacen son apenas mencionados. Es un área a explorar y divulgar. Tiene la capacidad de poder realizar cálculos, investigar conjeturas, interesar a los alumnos en las cuestiones matemáticas aún no resueltas, además de notables notas históricas. La relación de algunas de estas con temas tan simples como fracciones irreducibles, y otros temas simples de Matemática hace que deban ser tratados en el curriculum del Profesorado. Bibliografía. 1) Fúster, S. A (2001). Técnicas criptográficas de protección de datos. México: Alfaomega Ediciones. 2) Tattersall, J. J. (1999). Elementary Number Theory in Nine Chapter. Reino Unido: Cambridge ediciones 3) Lauritzen, N. (2003). Concrete Abstract Algebra. Reino Unido: Cambridge Ediciones 4) Rosen, K. H. (2004). Matemática discreta y sus aplicaciones. Madrid: MC Graw Hill ediciones 5) Pietrocola, N. (2001). Aritmética. Argentina: Red Olímpica Ediciones. 6) Gentile, E. (1991). Aritmética para la formación Matemática. Volumen 1. Argentina: Red Olímpica 7) Gentile, E. (2012). Aritmética para la formación Matemática. Volumen 2. Argentina: Red Olímpica