La función indicatriz de Euler, el teorema de Euler-Fermat y el pequeño teorema de Fermat

La función indicatriz de Euler

La función indicatriz de Euler es muy importante en teoría de números. La función indicatriz de Euler de un número entero positivo $m$, y se escribe $\varphi(m)$, proporciona el número de números enteros positivos, menores o iguales que $m$, que son coprimos con $m$. En el lenguaje matemático: $\varphi(m):=\text{cardinal}\left(\{n\in \mathbb{N}: (1\le n \le m) \wedge \text{m.c.d.}(m,n)=1\}\right)$. Se demuestra que dicha cantidad es igual a $\displaystyle \varphi(m):=m\,\prod_{p_i|m}\,\left(1-\dfrac{1}{p_i}\right)$; siendo $\{p_i\}$, el conjunto de números primos que dividen a $m$. Así, por ejemplo $\varphi(9)=9\cdot \left(1-\dfrac{1}{3}\right)=9\cdot \dfrac{2}{3}=6$; en efecto, el conjunto de números naturales que cumplen la condición requerida es $\{1,2,4,5,7,8\}$, y, claro está que $\text{cardinal}\left(\{1,2,4,5,7,8\}\right)=6$

El teorema de Euler-Fermat

La función indicatriz de Euler-Fermat aparece por ejemplo en el teorema de Euler-Fermat: Si $a,m \in \mathbb{N}$ son primos relativos, esto es, $\text{m.c.d.}(a,m)=1)$, entonces $a$ es congruente con $1$ módulo $m$: $a^{\varphi(m)} \equiv 1 (\text{mod}\, m)$, y es de gran importancia en el cálculo de congruencias.

El pequeño teorema de Fermat

El teorema de Euler-Fermat generaliza el pequeño teorema de Fermat. El pequeño teorema de Fermat dice así: dado un número $p$, primo, y un número entero $a$, siendo $a$ y $p$ coprimos, esto es $\text{m.c.d.}(a,p)=1$, entonces $a^{p-1}\equiv 1 (\text{mod}\, p)$, afirmación que es equivalente a $a^p ≡ a (\text{mod}\, p)$. Por ejemplo, si $p=3$ y $a=4$, se tiene que el residuo de la división euclídea de $a^p=4^{3-1}=16$ entre $3$ es $1$, como debe ser; esto es, el residuo de la división $4^3=64$ entre $3$ es igual a $4$.

-oOo-

Observación. Una consecuencia de este teorema es la siguiente: Como al dividir $a^{p-1}$ entre $p$ se obtiene resto igual a $1$, existe un $k\in \mathbb{Z}$ para el cual $a^{p-1}=k\, p +1$, multiplicando por $a$ en cada miembro de la igualdad, se tiene que $a^{p}= k \,p \,a + a$, luego $a^{p} - a$ es múltiplo de $p$ puesto que $k\,a$ és también un número entero.

Ejemplo. Sea $a=9$ y $p=2$ (primo), siendo $(9,2)=1$ y cumpliéndose así las condiciones suficientes del teorema. Comprabamos, en efecto, que $a^p=9^2=81 \mod 2 = 1$, coincidiendo con $a=9 \mod 2 =1$; y, además, $a^p-a \in (\overset{.}{p})$ pues $81-8=72 \in (\overset{.}{2})$.

$\diamond$

Introducción a la resolución de ecuaciones diofánticas

Antes de exponer la solución del ejercicio que resolveremos como ejemplo, vamos a decir algunas cosas sobre las ecuaciones con números enteros; en concreto, las que toman la forma $ax+by=c$ (que son las más sencillas), y que llamamos ecuaciones diofánticas lineales. Los coeficientes $a,b,c \in \mathbb{Z}$ vienen dados; y, de tener solución la ecuación, las incógnitas $x$ e $y$, que debemos determinar deben ser, también, números enteros.

Algo de teoría:
Veamos lo que nos dice la teoría: Una ecuación diofántica lineal del tipo $ax+by=c$ tiene solución si y sólo si $d\overset{.}{=}\text{m.c.d.}(a,b)$ es divisor del término independiente $c$, lo cual anotamos de la forma abreviada $d|c$; y, teniendo solución dicha ecuación, se demuestra que hay infinitos pares de valores $(x,y)$ que satisfacen dicha ecuación. Encontramos las infinitas soluciones ( solución general ) encontrando, primero, una solución particular $(x_1,y_1)$, y, a continuación, la solución general, que es de la forma

$$\left\{\begin{matrix}
x=x_1+\lambda\,\dfrac{b}{d} & \\
\\
y=y_1-\lambda\,\dfrac{a}{d} & \\
\end{matrix}\right. \forall \lambda \in \mathbb{Z}$$

Vamos, ahora, a exponer un ejemplo.

ENUNCIADO:
Sea la ecuación diofántica lineal $6x+50y=108$. ¿ Tiene solución ? En caso afirmativo, ¿ cómo son los infinitos pares de valores enteros $(x,y)$ ?

SOLUCIÓN:
Observemos que $a=6$, $b=50$ y $c=108$. Como el máximo común divisor de $a$ y $b$, $d:=\text{m.c.d.}(6,50)=2$, es divisor del término independiente $c=108$, esto es $2 | 108$, podemos afirmar que la ecuación tiene solución en $\mathbb{Z}$ y que ésta consta de infinitos pares de números enteros $(x,y)$, que vamos a ver cómo son a continuación.

Encontremos, para empezar, una solución particular de la ecuación dada. Para ello, determinaremos primero una solución particular de la ecuación $ax+by=d$ (identidad de Bézout) y, partiendo de ésta, encontraremos la solución general a una ecuación diofántica lineal.

La identidad de Bézout, $ax+by=d$ es, en el caso que nos ocupa, $6x+50y=2$. Y vemos fácilmente que, $-8$ y $1$ son dos números enteros que cumplen dicha igualdad; en efecto, $6(-8)+50\cdot 1 = 2$   (1). Y, como el término independiente, $108$, de la ecuación pedida se obtiene multiplicando el término independiente de la identidad de Bézout ( que es $2$ ) por $108/2=54$, mutiplicaremos pues ambos miembros de (1) por $54$ para obtener $$6\cdot (-8)\cdot 54+50\cdot 1 \cdot 54 = 2 \cdot 54$$ con lo cual $$6 \cdot \underset{x_1}{\underbrace{\left((-8)\cdot 54\right)}}+50 \cdot \underset{y_1}{\underbrace{\left( 1 \cdot 54 \right)}}= 108$$ es decir $$6 \cdot \underset{x_1}{\underbrace{(-432)}}+50 \cdot \underset{y_1}{\underbrace{54}}= 108$$ luego una solución particular es $$x_1=-432\,,\,y_1=54$$ Así pues, finalmente, construyendo la solución general, llegamos a $$\left\{\begin{matrix}
x=-432+\lambda\,\dfrac{50}{2} & \\
\\
y=54-\lambda\,\dfrac{6}{2} & \\
\end{matrix}\right. \forall \lambda \in \mathbb{Z}$$
es decir
$$\left\{\begin{matrix}
x=-432+25\,\lambda \\
\\
y=54-3\,\lambda \\
\end{matrix}\right. \quad \quad \forall \lambda \in \mathbb{Z}$$

Ahora, dando valores (enteros) arbitrarios al parámetro $\lambda$ podemos encontrar cualesquiera de los pares de números enteros $(x,y)$ - hay infinitos - que constituyen la solución general; así, por ejemplo, para $\lambda = 4$, encontramos $(-332,42)$, etcetera.


Referencias:
  [1] BUJALANCE, E.; et. al., Elementos de Matemática Discreta, Sanz y Torres, Madrid, 2005 ( tercera edición )
  [2] PARSONS, P.; DIXON, G.et. al., Matemáticas en segundos, Librero, Madrid, 2020 ( pp. 42-43 )
  [3] Wikipedia, https://es.wikipedia.org/wiki/Ecuación_diofántica

$\square$

La conjetura de Collatz ( o c. "3n+1" )

El problema 3n+1 consiste en estudiar el comportamiento de una sucesión de números naturales que empezando por un número natural cualquiera se obtiene a continuación el número 3n+1 si n es impar o bien n/2 si n es par. La conjetura 3n+1 nos dice que empezando con cualquier número natural n y construyendo dicha sucesión, siempre se llega al número 1.

No se ha probado aún dicha conjetura, si bien se ha llegado a demostrar es cierta para números menores o iguales que 16172831301712733 ( abril de 2021 ).

Referencias:
  [1] https://es.wikipedia.org/wiki/Conjetura_de_Collatz, Wikipedia