1.15: Funciones teóricas numéricas
- Page ID
- 117418
Volveremos a los primos de Mersenne en el próximo capítulo. Antes de hacerlo, introducimos algunos conceptos que serán útiles tanto entonces como posteriormente en el texto.
La función de recuento de primos\(\pi(x)\) que aparece en el Teorema de los Números Primos (Teorema 1.11.3) y las funciones generadoras imaginadas y estudiadas en la Sección 1.14 no son de ninguna manera las únicas funciones estudiadas en la teoría de números. Los matemáticos a través de la historia han mirado de manera rentable varias funciones adicionales ligadas a nuestras preguntas clave sobre los enteros. En este capítulo presentamos tres de estos. Aunque sus definiciones puedan parecer un poco extrañas al principio, ojalá los resultados de este capítulo y los ejercicios que siguen te convenzan de que sus propiedades son lo suficientemente interesantes como para que el estudio de estas funciones valga la pena.
Funciones relacionadas con divisores
Comenzamos con dos funciones relacionadas con los divisores positivos de un entero\(n\).
Para cada entero\(n>0\), defina\[\begin{aligned} \tau(n) &=\text{the number of positive divisors of }n, \\ \sigma(n) &=\text{the sum of the positive divisors of }n.\end{aligned}\]
El entero\(12=3\cdot 2^2\) tiene divisores positivos\[1,2,3,4,6,12.\nonumber \] Por lo tanto\[\tau(12)=6\nonumber \] y\[\sigma(12)=1+2+3+4+6+12=28.\nonumber \]
Se dice que un divisor positivo\(d\) de\(n\) es un divisor adecuado de\(n\) if\(d<n\). Denotamos la suma de todos los divisores propios de\(n\) by\(\sigma^\ast(n)\).
Tenga en cuenta que si\(n\ge 2\) entonces\[\sigma^\ast(n)=\sigma(n)-n.\nonumber \]
Llevando nuestro último ejemplo más lejos,\[\sigma^\ast(12)=16.\nonumber \]
El siguiente teorema muestra una forma sencilla de calcular\(\sigma(n)\) y a\(\tau(n)\) partir de la factorización principal de\(n\).
Vamos\[n=p_1^{e_1}p_2^{e_2}\dotsm p_r^{e_r},\quad r\ge 1,\nonumber \] donde\(p_1<p_2<\dotsb<p_r\) están los primos y\(e_i\ge 0\) para cada uno\(i\in\{1,2,\dotsc,r\}\). Entonces
- \(\tau(n)=(e_1+1)(e_2+1)\dotsm(e_r+1)\);
- \(\sigma(n)=\left(\dfrac{p_1^{e_1+1}-1}{p_1-1}\right)\left(\dfrac{p_2^{e_2+1}-1}{p_2-1}\right)\dotsm \left(\dfrac{p_r^{e_r+1}-1}{p_r-1}\right)\).
Prueba
(1) Del Teorema Fundamental de la Aritmética, cada factor positivo\(d\) de\(n\) tendrá sus factores primos provenientes de los de\(n\). De ahí\(d\mid n\) si y solo si\(d=p_1^{f_1}p_2^{f_2}\dotsm p_r^{f_r}\) para algunos exponentes enteros\(f_i\) donde para cada uno\(i\), es\[0\le f_i\le e_i.\nonumber \] decir, para cada uno\(f_i\) podemos elegir un valor en el conjunto de\(e_i+1\) números \(\{0,1,2,\dotsc,e_i\}\). Entonces, en total, hay\((e_1+1)(e_2+1)\dotsm(e_r+1)\) opciones para los exponentes\(f_1,f_2,\dotsc,f_r\), y por el Teorema Fundamental de la Aritmética, cada conjunto de elecciones arroja un factor diferente. Entonces (1) sostiene.
Para probar (2), primero establecemos dos lemmas.
Antes de probarlo veamos un ejemplo. Tomar\(n=72=8\cdot 9=2^3\cdot 3^2\). El teorema dice que se\[\begin{aligned} \tau(72) &=(3+1)(2+1)=12 \qquad \text{and}\\ \sigma(72) &=\left(\frac{2^4-1}{2-1}\right)\left(\frac{3^3-1}{3-1}\right)=15\cdot 13=195.\end{aligned}\] puede calcular\(\tau(72)\) y a\(\sigma(72)\) partir de sus definiciones originales para verificar que estos resultados son correctos (¡y mucho más rápidos de calcular!).
Dejemos\(n=ab\) dónde\(a,b>0\) y\(\gcd(a,b)=1\). Entonces\(\sigma(n)=\sigma(a)\sigma(b)\).
Prueba
Ya que\(a\) y\(b\) tienen sólo\(1\) como factor común positivo, utilizando el Teorema Fundamental de la Aritmética es fácil ver que\(d\mid ab\Leftrightarrow d=d_1d_2\) dónde\(d_1\mid a\) y\(d_2\mid b\). Es decir, los divisores de\(ab\) son productos de los divisores de\(a\) y los divisores de\(b\). Dejar\[1,a_1,\dotsc,a_s\nonumber \] denotar los divisores de\(a\) y dejar\[1,b_1,\dotsc,b_t\nonumber \] denotar los divisores de\(b\). Entonces\[\begin{aligned} \sigma(a) &=1+a_1+a_2+\dotsb+a_s, \\ \sigma(b) &=1+b_1+b_2+\dotsb+b_t.\end{aligned}\] Los divisores de se\(n=ab\) pueden enumerar de la siguiente manera\[\begin{gathered} 1,b_1,b_2,\dotsc,b_t, \\ a_1\cdot 1, a_1\cdot b_1, a_1\cdot b_2,\dotsc, a_1\cdot b_t, \\ a_2\cdot 1, a_2\cdot b_1, a_2\cdot b_2,\dotsc, a_2\cdot b_t, \\ \vdots \\ a_s\cdot 1, a_s\cdot b_1, a_s\cdot b_2,\dotsc, a_s\cdot b_t.\end{gathered}\] Es importante señalar que ya que\(gcd(a,b)=1\),\(a_ib_j = a_kb_\ell\) implica que\(a_i=a_k\) y\(b_j=b_\ell\). Es decir, no hay repeticiones en la matriz anterior.
Si sumamos cada fila obtenemos\[\begin{gathered} 1+b_1+\dotsb+b_t=\sigma(b) \\ a_11+a_1b_1+\dotsb+a_1b_t=a_1\sigma(b) \\ \vdots \\ a_s\cdot 1+a_sb_1+\dotsb+a_sb_t=a_s\sigma(b).\end{gathered}\] Al sumar estas sumas parciales juntas obtenemos\[\begin{split} \sigma(n) &=\sigma(b)+a_1\sigma(b)+a_2\sigma(b)+\dotsb+a_3\sigma(b) \\ &=(1+a_1+a_2+\dotsb+a_s)\sigma(b) \\ &=\sigma(a)\sigma(b). \end{split}\] Esto prueba el lema.
Si\(p\) es un prime y\(k\ge 0\) tenemos\[\sigma(p^k)=\frac{p^{k+1}-1}{p-1}.\nonumber \]
Prueba
Ya que\(p\) es primo, los divisores de\(p^k\) son\(1,p,p^2,\dotsc,p^k\). Una fórmula estándar para series geométricas rinde\[\sigma(p^k)=1+p+p^2+\dotsb+p^k=\frac{p^{k+1}-1}{p-1},\nonumber \] según se desee.
Prueba
(2) Vamos\(n=p_1^{e_1}p_2^{e_2}\dotsm p_r^{e_r}\). Nuestra prueba es por inducción en\(r\). Si\(r=1\),\(n=p_1^{e_1}\) y el resultado se desprende de Lemma\(\PageIndex{2}\). Supongamos que el resultado es cierto cuando\(1\le r\le k\). Consideremos ahora el caso\(r=k+1\). Es decir, vamos\[n=p_1^{e_1}\dotsm p_k^{e_k}p_{k+1}^{e_{k+1}}\nonumber \] donde los primos\(p_1,\dotsc,p_k,p_{k+1}\) son distintos y\(e_i\ge 0\). Vamos\(a=p_1^{e_1}\dotsm p_k^{e_k}\),\(b=p_{k+1}^{e_{k+1}}\). Claramente\(\gcd(a,b)=1\). Entonces por Lemma\(\PageIndex{1}\) tenemos\(\sigma(n)=\sigma(a)\sigma(b)\). Por la hipótesis de inducción\[\sigma(a)=\left(\frac{p_1^{e_1+1}-1}{p_1-1}\right)\dotsm\left(\frac{p_k^{e_k+1}-1}{p_k-1}\right)\nonumber \] y por Lemma\(\PageIndex{2}\)\[\sigma(b)=\frac{p_{k+1}^{e_{k+1}+1}-1}{p_{k+1}-1}\nonumber \] y se deduce que\[\sigma(n)=\left(\frac{p_1^{e_1+1}-1}{p_1-1}\right)\dotsm\left(\frac{p_{k+1}^{e_{k+1}+1}-1}{p_{k+1}-1}\right).\nonumber \] Así el resultado se mantiene para\(r=k+1\). Por PMI se sostiene para\(r\ge 1\).
Las funciones\(\sigma(n)\) y\(\sigma^*(n)\) aparecerán en el siguiente capítulo a medida que introducimos números perfectos. Propiedades adicionales de\(\tau(n)\) y\(\sigma(n)\) se discuten en los ejercicios.
Función totiente de Euler
La función final que presentaremos en este capítulo se conoce como la función phi-function de Euler, o la función totiente de Euler. A diferencia de\(\tau\) y\(\sigma\), que se ocupó de los divisores de su entrada,\(\phi\) se ocupará de números que no tienen factor primo en común\(n\).
Si\(X\) es un conjunto, el número de elementos en\(X\) se denota por\(|X|\).
Por ejemplo,\(|\{1\}|=1\) y\(|\{0,1,3,9\}|=4\).
Si\(m\ge 1\), la función totiente de Euler\(n\) está definida por\[\phi(n)=|\{i\in\mathbb{Z}\mid 1\le i\le n\text{ and }\gcd(i,n)=1\}|.\nonumber \]
A primera vista,\(\phi(n)\) puede parecer tedioso de calcular. Por ejemplo, para poder calcular\(\phi(1000)\), ¿una persona necesitaría enumerar todos los números relativamente primos a 1000 y luego contarlos?
Afortunadamente, los siguientes teoremas muestran que una vez que\(n\) se da la factorización prima de, la computación\(\phi(n)\) es fácil.
Si\(a>0\) y\(b>0\) y\(\gcd(a,b)=1\), entonces\[\phi(ab)=\phi(a)\phi(b).\nonumber \]
Si\(p\) es primo y\(n>0\) luego\[\phi\left(p^n\right)=p^n-p^{n-1}.\nonumber \]
Dejar\(p_1,p_2,\dotsc,p_k\) ser primos distintos y dejar\(n_1,n_2,\dotsc,n_k\) ser enteros positivos, entonces\[\phi\left(p_1^{n_1}p_2^{n_2}\dotsm p_k^{n_k}\right)=\left(p_1^{n_1}-p_1^{n_1-1}\right)\dotsm\left(p_k^{n_k}-p_k^{n_k-1}\right).\nonumber \]
Antes de discutir las pruebas de estos tres teoremas, vamos a ilustrar su uso:
\[\begin{gathered} \phi(12)=\phi\left(2^2\cdot 3\right)=\left(2^2-2^1\right)\left(3^1-3^0\right)=2\cdot 2=4 \\ \begin{split} \phi(9000)=\phi\left(2^3\cdot 5^3\cdot 3^2\right) &=\left(2^3-2^2\right)\left(5^3-5^2\right)\left(3^2-3^1\right) \\ &=4\cdot 100\cdot 6=2400. \end{split}\end{gathered}\]
Tenga en cuenta que si\(p\) hay algún primo entonces\[\phi(p)=p-1.\nonumber \]
Pospondremos una prueba de Teorema\(\PageIndex{2}\) hasta la Sección 1.23. Aquí damos la prueba del Teorema\(\PageIndex{3}\).
Prueba
Queremos contar el número de elementos en el conjunto\(A=\{1,2,\dotsc,p^n\}\) que son relativamente primos a\(p^n\). Dejar\(B\) ser el conjunto de elementos de\(A\) que tienen un factor mayor que\(1\) en común con\(A\). Tenga en cuenta que si\(b\in B\) y\(\gcd\left(b,p^n\right)=d>1\), entonces\(d\) es un factor de\(p^n\) y\(d>1\) así\(d\) tiene\(p\) como factor. De ahí\(b=pk\), para algunos\(k\), y\(p\le b\le p^n\), así\(p\le kp\le p^n\). De ello se deduce que\(1\le k\le p^{n-1}\). Es decir,\[B=\left\{p,2p,3p,\dotsc,kp,\dotsc,p^{n-1}p\right\}.\nonumber \] nos interesa el número de elementos de\(A\) no en\(B\). Desde\(|A|=p^n\) y\(|B|=p^{n-1}\), este número es\(p^n-p^{n-1}\). Es decir,\(\phi\left(p^n\right)=p^n-p^{n-1}\).
La prueba del teorema\(\PageIndex{4}\) se desprende de los teoremas\(\PageIndex{2}\) y \(\PageIndex{3}\). La prueba es por inducción\(n\) y es bastante similar a la prueba del Teorema\(\PageIndex{1}\) (2), por lo que omitimos los detalles. Otras propiedades de la\(\phi\) función -se desarrollan en los ejercicios.
Funciones multiplicativas
Las funciones\(\tau\),\(\sigma\), y\(\phi\) todas tienen una propiedad común, mostrada en Teorema\(\PageIndex{1}\)\(\PageIndex{1}\), Lema y Teorema\(\PageIndex{2}\).
Una función\(f(n)\) definida para enteros positivos\(n\) se llama multiplicativa si\(f(ab)=f(a)f(b)\) siempre\(\gcd(a,b)=1\).
De los resultados mencionados anteriormente,\(\tau\),\(\sigma\), y\(\phi\) son todas las funciones multiplicativas. Si estás tan inclinado, haz algunas lecturas adicionales por tu cuenta para conocer varias propiedades agradables que las funciones multiplicativas tienen en común; ¡valdrá la pena el esfuerzo!
Algunas palabras finales
Estudios posteriores en teoría de números te llevarán a una mayor profundidad con\(\tau\)\(\sigma\), y\(\phi\), así como con la función de conteo de primos\(\pi\), y te introducirán a otras funciones que satisfacen propiedades notables. Aunque diremos poco más en este libro sobre las funciones teóricas de números, \(^{1}\)terminamos nuestra discusión con un intrigante problema sin resolver en la teoría de números.
En 1907 Robert Carmichael anunció que había demostrado la siguiente declaración:
Por cada entero positivo n existe un entero positivo diferente\(m\) para el cual\(\phi(n)=\phi(m)\).
En otras palabras, la declaración de Carmichael es que si tuviéramos que enumerar\(\phi(n)\) para todos los enteros positivos\(n\), cada valor se mostraría al menos dos veces; cada entero comparte su\(\phi\) valor -valor con al menos otro entero.
Desafortunadamente, la prueba de Carmichael fue defectuosa, y hoy la conjetura aún no se ha demostrado cierta (¡o desmentida!). En 1998 Kevin Ford demostró que si la conjetura de Carmichael no es cierta, entonces el contraejemplo más pequeño (es decir, el número más pequeño\(n\) tal que ningún otro número tenga el mismo\(\phi\) -valor que\(n\)) debe ser mayor que\(10^{10^{10}}\). ¡Eso es enorme! Por otro lado, los matemáticos han demostrado que si existe algún contraejemplo, entonces hay infinitamente muchos contraejemplos.
Puedes encontrar más sobre la conjetura de Carmichael con una búsqueda rápida en internet o en bibliotecas. ¡Feliz lectura!
Ejercicios
Encuentra\(\sigma(n)\) y\(\tau(n)\) para los siguientes valores de\(n\).
- \(n=900\)
- \(n=496\)
- \(n=32\)
- \(n=128\)
- \(n=1024\)
¿Se\(\PageIndex{1}\) sostiene Lemma si reemplazamos\(\sigma\) por\(\sigma^\ast\)?
(Pista: La respuesta es no, pero encuentra números explícitos\(a\) y\(b\) tal que el resultado falla todavía\(\gcd(a,b)=1\).)
Demostrar que\(\tau(n)\) es extraño si y sólo si\(n\) es un cuadrado.
Demostrar que\(\displaystyle\prod_{d|n} d = n^{\tau(n)/2}\), donde el producto es sobre todos los divisores positivos\(d\) de\(n\).
Observe que se\(n=30\) puede escribir de múltiples maneras como la suma de uno o más enteros positivos consecutivos:\[30, \qquad 9+10+11, \qquad 6+7+8+9, \qquad 4+5+6+7+8.\nonumber \] Mostrar que por cada entero positivo\(n\), si\(n=2^p q\), donde\(p \geq 0\) y\(q\) es impar, entonces \(\tau(q)\)es el número de formas que se\(n\) pueden escribir como la suma de una secuencia de números enteros consecutivos.
(Pista: Para múltiples valores de\(n\), intente mirar todas las formas que se\(n\) pueden escribir como una suma de enteros positivos consecutivos. Trate de hacer coincidir diferentes sumas con diferentes divisores de una\(q\) manera que siempre funcione, no importa lo que\(n\) sea.)
Mostrar que si\[m=p_1^{n_1}p_2^{n_2}\dotsm p_k^{n_k}\nonumber \] donde\(p_1,\dotsc,p_k\) están distintos primos y cada uno\(n_i\ge 1\), entonces\[\phi(m)=m\left(1-\frac1{p_1}\right)\left(1-\frac1{p_2}\right)\dotsm\left(1-\frac1{p_k}\right).\nonumber \]
Demostrar que\(\phi(n)\) es par para todos los enteros positivos que no\(n\) sean 1 o 2.
Determinar, con comprobante, todos los números de\(n\) tal manera que
- \(\phi(n)=2\)
- \(\phi(n)=4\)
- \(\phi(n)=6\)
Demostrar que si\(\phi(n) \mid (n-1)\), entonces ningún primo aparece más de una vez en la factorización prima de\(n\).
Dejar\[S(n) = \sum_{d \mid n} \phi(d),\nonumber \] es decir,\(S(n)\) es la suma de los valores que obtenemos cuando evaluamos\(\phi(d)\) para todos los divisores positivos\(d\) de\(n\). Por ejemplo,\[S(4)=\phi(1)+\phi(2)+\phi(4)=1+1+2=4,\quad\text{and}\nonumber\]\[S(15)=\phi(1)+\phi(3)+\phi(5)+\phi(15)=1+2+4+18=15.\nonumber\]
Calcula\(S(n)\)\(1 \leq n \leq 10\) y conjetura \(^{2}\)una fórmula para\(S(n)\).
Para cada función a continuación, decida si la función es multiplicativa o no. (Supongamos que las funciones están definidas en el conjunto de enteros positivos.)
- \(f(n) = 1\)
- \(f(n) = n\)
- \(f(n) = 1+n\)
- \(f(n) = \log(n)\)
- \(f(n) = 2^n\)
- \(f(n) = 1/n\)
Para enteros positivos\(n\), defina la función\(\rho\) por por\[\rho(n) = \text{the number of prime factors of}\;n;\nonumber \] ejemplo,\(\rho(4)=1\) (ya que 4 es divisible por 2 y ningún otro primo) y\(\rho(100)=2\) (ya que 100 es divisible por 2 y 5 y ningún otro primo).
- ¿La función es\(\rho(n)\) multiplicativa? Explique por qué o por qué no.
- ¿La función es\(f(n) = (-1)^{\rho(n)}\) multiplicativa? Explique por qué o por qué no.
Mostrar eso para cualquier número entero positivo\(a\) y\(b\), si\(f\) es una función multiplicativa, entonces\(f(a)\cdot f(b) = f(\gcd(a,b)) \cdot f(\operatorname{lcm}(a,b))\).