La Funcion Mayor Entero

La función mayor entero es denotada por los corchetes $[\cdot]$ y es muy útil al tratar con problemas de divisibilidad.

Definición: Para un número real positivo $x$, dentoamos por $[x]$ al entero mayor que es menor o igual a $x$. Esto es $[x]$ es el único entero que satisface

(1)

\begin{align} x-1 < [x] \le x. \end{align}

Notemos que $[x]=x$ si y solamente si $x$ es un entero. También notemos que todo número real $x$ se puede escribir como $x = [x] +y$ con $0\le y <1$.

Queremos investigar cuantas veces un primo $p$ aparece en $n!$. Por ejemplo para $p=3$ y $n=9$ tenemos que $9! = 2^73^4(5)(7)$, así que la potencia exacta de 3 que divide a $9!$ es 4.

Teorema: Si $n$ es un entero positivo y $p$ es un número primo, entonces el exponente $v_p(n!)$ de la potencia más grande de $p$ que divide $n!$ está dada por la fórmula:

(2)

\begin{align} v_p(n!)=\sum_{k=1}^{\infty}\left[\frac{n}{p^k}\right] \end{align}

Notemos que esta suma NO es una suma infinita pues $[n/p^k] = 0$ si $p^k>n$.

Demostración:
En la factorización de $n!$ los números que son múltiplos de $p$ son $p, 2p, 3p, \cdots, [n/p] p$ así que $p$ es un divisor de $n!$ por al menos $[n/p]$ veces, sin embargo falta contar en esta suma a los números menores que n que también son divisores de $n^2$; estos son $p^2, 2p^2,\cdots, [n/p^2] p^2$, pero ahora nos faltan los que son múltiplos de $p^3$… continuando con este proceso vemos que la máxima potencia de $p$ que divide a $n!$ es en efecto $\sum_k [n/p^k]$.

Corolario: Se tiene que $n! = \prod_{p\le n} p^{\sum_k [n/p^k]}$.

Ejemplo: Encontremos el número de ceros con los que termina 50! en su representación decimal. Para esto necesitamos contar cuántas veces 10 divide a $50!$ y esto sucederá tantas veces como $\min{ v_2(50!),v_5(50!}$. Tenemos que :

(3)

\begin{align} v_2(50!) = [50/2]+[50/4]+\ldots + [50/2^5] = 47 \end{align}

mientras que :

(4)

\begin{equation} v_5(50!)= [50/5]+[50/25] = 12 \end{equation}

Por lo tanto $50!$ termina con un total de 12 ceros.

Teorema: Si $n,r$ son enteros positivos con $1\le r<n$ entonces el coeficiente binomial:

(5)

\begin{align} \binom{n}{r} = \frac{n!}{r!(n-r)!} \end{align}

es también un entero.

Demostración: Observemos que $[a+b]\ge [a]+[b]$. En particular para cada factor primo $p$ de $r!(n-r)!$ se tiene que:

(6)

\begin{align} \left[ \frac{n}{p^k}\right] \ge \left[ r/p^k\right] + [(n-r)/p^k]; \end{align}

así que sumando en ambos lados de la igualdad sobre $k$ tenemos que:

(7)

\begin{align} \sum_k [n/p^k] \ge \sum_k [r/p^k] + \sum_k [(n-r)/p^k] \end{align}

la primera suma da $v_p(n!)$ y la segunda suma da $v_p(r!) + v_p((n-r)!) = v_p(r!(n-r)!$ lo que significa que la mayor potencia de un primo que divide a $r!(n-r)$ también divide a $n!$ demostrando que el cociente es un entero.

Corolario: Para un entero positivo $r$, el producto de cualesquiera $r$ enteros consecutivos positivos es divisible por $r!$.

Demostración: En efecto tenemos que

(8)

\begin{align} n(n+1)\cdots (n-r+1) = \binom{n}{r}r! \end{align}

y como $\binom mr$ es entero el resultado se sigue.

Teorema: Sea $f$ y $F$ funciones aritméticas tal que

(9)

\begin{align} F(n)= \sum_{d\mid n} f(d) \end{align}

entonces para cualqier entero positivo $N$ se tiene:

(10)

\begin{align} \sum_{n=1}^N F(n) = \sum_{k=1}^N f(k) [N/k] \end{align}

Demostración: Notemos que

(11)

\begin{align} \sum_{n=1}^N F(n) = \sum_{n=1}^N \sum_{d\mid n} f(d) \end{align}

ahora agrupemos la suma de acuerdo a valores iguales de $f(d)$, para esto notemos que para un entero fijo $k\le N$ el término $f(k)$ aparece en la suma $\sum_{d\mid n }f( d)$ si y sólo si $k$ es un divisor de $n$. Ahora para encontrar el número de sumas $\sum_{d\mid n}f(d)$ en las que $f(d)$ aparece, es suficiente encontrar el número de enteros entre $1,2,\ldots N$ que son divisibles por $k$. Hay exactamente $[N/k]$ de ellos: $k,2k, \ldots, [N/k] k$. Así que para cada $k$ con $1\le k\le N$, $f(k)$ es un término de la suma $\sum_{d\mid n}f(d)$ exactamente para $[N/k]$ diferentes enteros positivos menores o iguales a $N$. Así que podemos reescribir la suma:

(12)

\begin{align} \sum_{n=1}^N F(n) = \sum_{n=1}^N \sum_{d\mid n} f(d) =\sum_{k=1}^{N}f(k)[N/k] \end{align}

y la prueba está terminada.

Corolario: Si $N$ es un entero positivo, entonces:

(13)

\begin{align} \sum_{n=1}^N \tau(n) = \sum_{n=1}^{N}[N/n] \end{align}

y

(14)

\begin{align} \sum_{n=1}^N \sigma(n) = \sum_{n=1}^N n[N/n]. \end{align}

Ejemplo: Calcular $\sum_{n=1}^6 f(n)$ para $f=\tau$ y para $f=\sigma$.