Nociones básicas de aritmética modular. Congruencias

La operación módulo, para dos números enteros $a$ y $b$, se define como $a \mod b := \text{residuo}( a \div b)$, entendiendo la división como la división euclídea: dados $a\in \mathbb{Z}$ y $\mathbb{Z}\ni b\neq 0$, entonces $\exists!\,q,r\in \mathbb{Z}$ tales que $a=b\cdot q+r \wedge 0\le r \lt |b|$ . Así por ejemplo, $15 \mod 7 =1$, ya que $8=7\cdot 2+1$; $-6 \mod 7 = 1$ ya que $-6=7\cdot (-1) +1$.

Decimos que dados dos números enteros $m$ y $n$ son congruentes entre sí con respecto a un determinado número entero $p$, y lo escribimos $m \equiv n (\mod p)$ si $m \mod p = n \mod p$, esto es, si las divisiones euclídeas $m \div p$ y $n \div p$ tienen el mismo resto. Así, por ejemplo, $15 \equiv 22 (\mod 7)$ ya que $15 \mod 7 = 1 = 22 \mod 7$. Tambien podemos decir, entre otras muchas cosas, que $15 \equiv -6 (\mod 7)$ ya que $15 \mod 7 = 1 = -6 \mod 7$

Esta operación módulo es muy importante en la teoría elemental de números (o matemática discreta): es necesaria en los cálculos con congruencias y también para entender y probar proposiciones. Como ejemplo práctico podemos subrayar que la matemática discreta es fundamental en el diseño de algoritmos y en programación.

Muchas calculadoras científicas incorporan esta operación, y la secuencia de tecleo suele ser (para el ejemplo que comento): [15 $\rightarrow$ mod $\rightarrow$ 7 $\rightarrow$ = (o EXE)], presentándose el resultado, $1$, en pantalla.

La congruencia cumple dos propiedades básicas. Si $a_1 \equiv a_2 (\mod p)$ y $b_1 \equiv b_2 (\mod p)$, entonces:

• $a_1+b_1 \equiv a_2 + b_2 \,(\mod p)$
• $a_{1}\cdot b_{1} \equiv a_{2} \cdot b_{2}\, (\mod p)$

Por ejemplo, $26 \equiv 19 (\mod 7)$, ya que $26 \mod 7 = 5 = 19 \mod 7$, y $27 \equiv 13 (\mod 7)$ puesto que $27 \mod 7 = 6 = 13 \mod 7$. Por tanto:

• $26+27 \equiv 19+13 (\mod 7)$, esto es, $53 \equiv 32 (\mod 7)$; en efecto: $53 \mod 7 = 4 = 32 \mod 7$
• $26\cdot 27 \equiv 19\cdot 13 (\mod 7)$, esto es, $702 \equiv 247 (\mod 7)$; en efecto: $702 \mod 7 = 2 = 247 \mod 7$

$\diamond$

Álgebra de permutaciones

Permutaciones

Consideremos el conjunto de índices $\{1,2,\ldots,n\}$. Entendemos por permutación una aplicación inyectiva del conunto $\{1,2,\ldots,n\}$ sobre sí mismo, de manera que $1\mapsto i_1$, $2\mapsto i_2$, $\ldots$, $n\mapsto i_n$, y notamos dicha permutación de la forma $i=[i_1,i_2,\ldots,i_n]$. Así, por ejemplo, la permutación $i=[2,4,3,1]$ significa que a $1$ le corresponde el $2$; al $2$ el $4$; al $3$ el $3$ y al $4$ el $1$, esto es, $i_1=2$, $i_2=4$,$i_3=3$ y $i_4=4$.

A partir de $n$ índices podemos obtener $n!$ permutaciones distintas.

Podemos componer dos permutaciones $i=[i_1,i_2,\ldots,i_n]$ y $j=[j_1,j_2,\ldots,j_n]$, obteniendo otra permutación de las $n!$ posibles. Esta nueva permutación, $k$, que resulta la notamos de la forma $(j\circ i)_k$, leyéndose $i$ compuesta con $j$, queriendo significar con ello que actúa primero la permutación $i$ y en segundo lugar la permutación $j$ sobre el resultado de la primera; así $(j \circ i)_k=j_{i_k}$

Ejemplo de permutación con $n=4$
Consideremos $i=[2,4,3,1]$ y $j=[4,2,1,3]$. Entonces $j\circ i$ es otra permutación, $k=(j\circ i)_k=j_{i_k}$ y es tal que:
  $k_1=j_{i_1}=j_2=2$
  $k_2=j_{i_2}=j_4=3$
  $k_3=j_{i_3}=j_3=1$
  $k_4=j_{i_4}=j_1=4$
Es decir, $$j \circ i=[2,3,1,4]$$

El grupo de permutaciones $(\mathcal{P}_n,\circ)$

El conjunto de las permutaciones, $\mathcal{P}$, de $n$ índices con la operación composición (o producto) de permutaciones, $(\mathcal{P}_n,\circ)$, tiene estructura de grupo. En efecto, la operación es interna; se cumple la propiedad asociativa $i\circ (j\circ k) = (i \circ j) \circ k$, para cualesquiera permutaciones $i,j$ y $k$; y, existe elemento neutro, que no es otro que $e=[1,2,\ldots,n]$, habida cuenta de que $e\circ i=i\circ e$ para toda permutación $i\in \mathcal{P}_n$, y dada cualquier permutación, $i$, existe para ésta un elemento simétrico, que designaremos por $i'$ y es tal que $i_m=n$ si y sólo si $i'_n=m$, para cualesquiera valores de índices $n,m\in \{1,2,\ldots,n\}$, por lo que $i \circ i' = i' \circ i = e$. Cabe decir, además, que, para cualesquiera permutaciones $i$ y $j$, no se cumple la propiedad conmutativa: $i\circ j \neq j \circ i$ luego dicho grupo no es conmutativo.

Ejemplo de cálculo de la permutación inversa de una permutación dada
Consideremos la permutación $\mathcal{P}_4 \ni i=[4,1,2,3]$. Entonces, como $1$ está en el segundo lugar en la permutación $i$, esto es, $i'_1=2$, ya que $i_2=1$; razonando de la misma manera, deducimos que $i'_2=3$, puesto que $i_3=2$; $i'_3=4$ (ya que $i_4=4$), y $i'_4=1$, pues $i_1=4$. Por consiguiente la permutación inversa de $i=[4,3,2,1]$ es $i'=[2,3,4,1]$.
Comprobemos que $e=[1,2,3,4]=i'\circ i=i'_{i_k}$ donde $k=1,2,3,4$:
  $i'_{i_1}=i'_4=1=e_1$
  $i'_{i_2}=i'_1=2=e_2$
  $i'_{i_3}=i'_2=3=e_3$
  $i'_{i_4}=i'_3=4=e_4$
y también que, $e=[1,2,3,4]=i\circ i'=i_{i'_k}$ donde $k=1,2,3,4$:
  $i_{i'_1}=i_2=1=e_1$
  $i_{i'_2}=i_3=2$
  $i_{i'_3}=i_4=3$
  $i_{i_4}=i_1=4$

Trasposiciones

Llamamos trasposición al intercambio de dos índices ($r$ por $s$, y $s$ por $r$) sin alterar el lugar del resto de los índices, y lo escribimos de la forma $(r,s)$. Ejemplo: $(2,4)=[1,4,3,2]$. Resulta evidente que la inversa de una trasposición es ella misma ya que $(r,s)=(s,r)$.

Teorema. Toda permutación se puede escribir como un producto (composición) de un número finito de trasposiciones.
Ejemplo
Se considera la permutación $[3,4,2,1]$. Veamos cómo escribirla como un producto de trasposiciones.
$[3,4,2,1]=(1,3)\circ [1,4,2,3]=$
  $=(1,3)\circ (2,4) \circ [1,2,4,3]$
    $=(1,3)\circ (2,4) \circ (3,4)\circ [1,2,3,4]$, que podemos escribir también como
      $[3,4,2,1]=(1,3)\circ (2,4) \circ (3,4)$, puesto que la última permutación que resulta (a la derecha) en el paso anterior $[1,2,3,4]$ es el elemento neutro del producto.

(...) $\diamond$

La función beta, la función gamma y el número $\pi$

La función beta o integral de Euler de primer orden se define como $$\displaystyle \beta(z,w)=\int_{0}^{1}\,x^{z-1}\,(1-x)^{w-1}\,dx$$ donde $z,w\in \mathbb{C}$ y son tales que $\text{Re}(z)\gt 0$ y $\text{Im}(w)\gt 0$. Una propiedad interesante de la misma es la siguiente $$\beta(z,w)=\dfrac{\Gamma(z)\Gamma(w)}{\Gamma(z+w)}$$

Es sabido que $\Gamma\left(\dfrac{1}{2}\right)=\sqrt{\pi}$ y $\Gamma(1)=1$ —ahora, en particular, $z,w\in \mathbb{Q}$—, luego $$\beta\left(\dfrac{1}{2},\dfrac{1}{2}\right)=\dfrac{\Gamma\left(\dfrac{1}{2}\right)\Gamma\left(\dfrac{1}{2}\right)}{\Gamma\left(\dfrac{1}{2}+\dfrac{1}{2}\right)}=\dfrac{\Gamma\left(\dfrac{1}{2}\right)\Gamma\left(\dfrac{1}{2}\right)}{\Gamma(1)}=\sqrt{\pi}\cdot \sqrt{\pi}=\pi$$ $\diamond$

Integrales impropias de segunda especie

Las integrales impropias de segunda especie son integrales definidas en las que la función integrando tiende a $\pm\infty$ en alguno de los dos límites de integración. Veamos cómo resolverlas con un ejemplo sencillo.

$$\displaystyle \int_{0}^{1}\,\dfrac{dx}{\sqrt{x}}=\displaystyle \lim_{k\rightarrow 0^+}\,\int_{0}^{1}\,\dfrac{dx}{\sqrt{x}}=\displaystyle \lim_{k\rightarrow 0^+}\,\left[2\,\sqrt{x}\right]_{k}^{1}=\displaystyle \lim_{k\rightarrow 0^+}\,\left(2\,\sqrt{1}-2\,\sqrt{k}\right)=\displaystyle \lim_{k\rightarrow 0^+}\,\left(2-2\,\sqrt{k}\right)=2-0=2$$ $\diamond$

Integrales impropias de primera especie

Las integrales impropias de primera especie son integrales definidas en las que alguno de sus dos límites de integración es $\pm\infty$. Veamos cómo resolverlas con un ejemplo sencillo.

$$\displaystyle \int_{1}^{+\infty}\,\dfrac{dx}{x}=\displaystyle \lim_{k\rightarrow +\infty}\,\left[\ln\,|x|\right]_{1}^k=\displaystyle \lim_{k\rightarrow +\infty}\,\left(\ln\,k-\ln\,1\right)=\displaystyle \lim_{k\rightarrow +\infty}\,\left(\ln\,k-0\right)=\ln\,(\lim_{k\rightarrow +\infty}\,k)=\ln(+\infty)=+\infty$$ $\diamond$

Ejemplo de aplicación de la función gamma a la integración de determinadas funciones

Recordemos la definición de la función gamma de $z\in \mathbb{C}$ $$\displaystyle \Gamma(z)=\int_{0}^{+\infty}\,t^{z-1}\,e^{-t}\,dt$$ la cual extiende el concepto de factorial a los números reales y complejos.

Vamos a utilizarla en este ejercicio para integrar la función real de variable real $\displaystyle \int_{0}^{+\infty}\,x\,e^{x^3}\,dx$. Para ello, partiremos de la definición de la función gamma, siendo ahora $z$ una variable real, por lo que, por claridad, reescribiremos la definición para esta situación particular de la forma $p\in \mathbb{R}$ $$\displaystyle \Gamma(p)=\int_{0}^{+\infty}\,t^{p-1}\,e^{-t}\,dt$$

Para ello, parece natural realizar el cambio de variable $t=x^3$ (con lo cual $x=t^{1/3}$); diferenciando en cada miembro de la igualda: $dx=\dfrac{1}{3}\,t^{-2/3}\,dt$. Así, la integral pedida se puede expresar de la forma $$\displaystyle \int_{0}^{+\infty}\,x\,e^{x^3}\,dx=\int_{0}^{+\infty}\,\dfrac{1}{3}\,t^{-1/3}\,e^{-t}\,dt=\dfrac{1}{3}\,\int_{0}^{+\infty}\,t^{2/3-1}\,e^{-t}\,dt\overset{p=2/3}{=}\dfrac{1}{3}\,\Gamma\left(\dfrac{2}{3}\right)$$ Nota: $\Gamma(2/3)$ es un número trascendente que aproximadamente es igual a $1,3541$, tal como puede comprobarse con la herramienta en línea WolframAlpha. $\diamond$

¿Por qué $0!=1$?

El factorial $n!$ se define a partir de la función gamma de $z\in \mathbb{C}$ $$\displaystyle \Gamma(z)=\int_{0}^{+\infty}\,t^{z-1}\,e^{-t}\,dt$$ la cual extiende el concepto de factorial a los números reales y complejos.

En particular, para $0\lt p\in \mathbb{R}$ se tiene que $$\displaystyle \Gamma(p)=\int_{0}^{+\infty}\,t^{p-1}\,e^{-t}\,dt$$ y se demuestra que $$\left\{\begin{matrix}\Gamma(p+1)=p\,\Gamma(p) \\ \Gamma(0)=1\end{matrix}\right.$$

Aplicando dicha recursividad, y tomando $p=n\in \mathbb{N}\cup \{0\}$ se llega, en particular, a la noción de factorial de un número entero no negativo $$\Gamma(n+1)=n! =\displaystyle \int_{0}^{\infty}\,t^{n}\,e^{-t}\,dt$$ Así pues $$0!=\displaystyle \int_{0}^{\infty}\,t^{0}\,e^{-t}\,dt=\int_{0}^{\infty}\,e^{-t}\,dt=1$$ $\diamond$