Download distintas funciones en matemática discreta, su importancia y

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