Fórmula para el máximo común divisor de dos números impares

Question

Estaba tomando el determinante de la matriz de adyacencia de un gráfico cuando me topé con esta interesante (aparente) coincidencia:

Si $m$ y $n$ son números impares, entonces $$ 2^{\textsf{gcd}(m,n)} = \prod_{k=1}^{m} \prod_{l=1}^{n} \left( e^{\frac{2k\pi i}{m}} + e^{\frac{2 l \pi i}{n}} \right).$$

Si tomamos $\log_2$ de ambos lados, obtenemos una expresión explícita que describe el máximo común divisor. ¿Alguien desea intentar una demostración de este hecho?

Aquí hay un código MATLAB que verifica la fórmula anterior. (Guárdalo como un archivo *.m en tu directorio de MATLAB; luego utiliza greatcd(m,n) para producir el máximo común divisor de los números impares seleccionados $m$ y $n$.)

function [I,J] = greatcd(m,n)
for k=1:m
for l=1:n
  H(k,l) = exp((2*pi*i*k)/m) + exp((2*pi*i*l)/n);
end
end
G=prod(H(:));
log2(real(G))

Parece que si $g = \textsf{gcd}(m,n)$, entonces $$\prod_{k=1}^{m} \prod_{l=1}^{n} \left( e^{\frac{2k\pi i}{m}} + e^{\frac{2 l \pi i}{n}} \right) = \prod_{k=1}^{g} \prod_{l=1}^{ng^{-1}} \left( 1 + e^{\frac{2l\pi i}{ng^{-1}}}\right)$$ y también creo que $$ \prod_{l=1}^{ng^{-1}} \left( 1 + e^{\frac{2l\pi i}{ng^{-1}}}\right) = 2.$$ Si mantengo fijo $l$ y tomo el producto sobre $k$, parece que obtengo $$\prod_{k=1}^{m} \left( e^{\frac{2k\pi i}{m}} + e^{\frac{2 l \pi i}{n}} \right) = 1 + e^{\frac{2l\pi i}{ng^{-1}}}.$$

Answer 1

Para mayor simplicidad, tomemos $n = 1$.

$\prod\limits_{k,l = 0}^{m-1, n-1} (\exp(\dfrac{2k\pi i}{m}) + \exp(\dfrac{2l\pi i}{n})) = \prod_{k=0}^{m-1} (\exp(\dfrac{2k\pi i}{m}) + 1) = \\\prod\limits_{k=0}^{\dfrac{m-1}{2}}(w^k + 1)\prod\limits_{k=0}^{\dfrac{m-1}{2}}(w^{-k} + 1)$

por simetría de un polígono regular de lados impares centrado en el origen de $\Bbb{C}$ cuyos vértices son las raíces $m$-ésimas de la unidad.

Pero las reglas de la conjugación compleja implican que $(w^k + 1)^* = (w^{k*} + 1) = w^{-k} + 1$. Así que tenemos $zz^*$ y eso siempre es real. Por lo tanto, para el caso $n=1, m\geq 1$ hemos demostrado que la fórmula es al menos un número real.

Un argumento similar usando simetrías de polígonos regulares de lados impares puede aplicarse al caso general donde $n \geq 1, m \geq 1$. Demostrando que la fórmula es al menos un número real.

Veámos que utilizando la misma simetría a través del eje real en $\Bbb{C}$ usada anteriormente, tu fórmula general es igual a: $$ \prod_{k,l=0}^{\dfrac{m-1}{2}, \dfrac{n-1}{2}}(w^{k} + z^l)(w^{-k}+ z^{-l})(w^{k} + z^{-l})(w^{-k} + z^{l}) $$

---

Considera que $0 \leq |w^{\pm k} + z^{\pm l}| \leq 2$. Lo cual también se puede observar al mirar los polígonos unitarios regulares en el plano $\Bbb{C}$.

Dado que tu fórmula es un número real, tenemos que $|\text{fórmula}| = \pm\text{fórmula}$.

Cada vez que en el producto $\dfrac{k}{m} = \dfrac{l}{n}$ obtendrás $|w^{k} + z^{l}| = |w^{-k} + z^{-l}| = 2$. Convéncete de que esto ocurre si y solo si esas dos fracciones son iguales en el producto. ¡Estamos cerca!

$\dfrac{k}{m} = \dfrac{l}{n}, \ k,l = 0, \dots, m-1, n-1 \iff ?$

Realmente no lo sé, así que veamos un ejemplo: $m = 15, n = 9, (m,n) = 3$ $0/15 = 0/9, \ 5/15 = 3/9, \ 10/15 = 6/9$

Y esos fueron los únicos ejemplos que pude pensar, así que parece que queremos demostrar que lo anterior ocurre exactamente $\gcd(m,n)$ veces en general.

Hasta ahora hemos demostrado que $\text{tu fórmula} = \pm 2^{\gcd(m,n)}\prod\limits_{k,l = 0; k/m \neq l/n}^{m-1, n-1} (\dots)$.

Todavía no hemos utilizado la simetría rotacional, así que tal vez la respuesta esté ahí para demostrar que la magnitud de la pieza restante de tu fórmula $=1$. Y con eso me refiero a multiplicar los términos cada uno por el mismo $e^{i\pi j/?}$ de modo que el conjunto resultante de vértices sea igual a tus dos polígonos originales, también conocido como simetría rotacional en un grupo Dihédrico.

Answer 2

Aquí se muestra una prueba "asimétrica". La idea es introducir un indeterminado $X$ y considerar el producto como un polinomio evaluado en $X = 1$. El lema clave es que si $m$ es impar y $\zeta$ es una raíz $m$-ésima de la unidad, entonces las raíces de $p_m(X) := X^m + 1$ son los negativos de las raíces de $X^m - 1$, porque si $z^m = 1$ entonces $(-z)^m = (-1)^m z^m = -1. Por lo tanto, $$p_m(X) = \prod_{k=1}^m (X + \zeta^k).$$ Usaremos esta identidad más abajo para $n$ y también para $m/g$, donde $g = \text{mcd}(m, n)$.

Primero, sean $\zeta$ y $\eta$ raíces primitivas $m$ y $n$-ésimas de la unidad, respectivamente (por ejemplo, $\zeta = e^{2\pi i / m}$). Introducir $X$, y simplificar utilizando el lema:
$$p(X) = \prod_{k=1}^m \prod_{l=1}^n (\zeta^k X + \eta^l) = \prod_{k=1}^m p_n(\zeta^k X)$$ entonces
$$\prod_{k=1}^m \prod_{l=1}^n (e^{2\pi i k/m} + e^{2\pi i l/n}) = p(1) = \prod_{k=1}^m p_n(\zeta^k) = (1+\zeta^n)(1+\zeta^{2n})(1+\zeta^{3n})\dotsb(1+\zeta^{mn}).

Ahora, porque $m$ y $n$ podrían no ser coprimos, este producto puede tener términos repetidos. Pero la repetición es muy regular. El exponencial cae en $\mathbb{Z}/m\mathbb{Z}$ (recuerda, $\zeta$ es una raíz $m$-ésima de la unidad) y el mapa $x \mapsto nx$ tiene núcleo generado por (la clase de equivalencia módulo $m$ de) $m/g$. Para ver esto, obten $s$ y $t$ tales que $ms + nt = g$. Si $nx \equiv 0$ (mod $m$) entonces $ntx = (g - ms)x = gx \equiv 0$ (mod $m$), así que $m$ divide a $gx$. Como $g$ divide a $m$, $m/g$ divide a $x.

Por lo tanto, el producto completo es simplemente $g$ copias de los primeros $m/g$ términos: $$p(1) = [(1+\zeta^n)(1+\zeta^{2n})\dotsb(1+\zeta^{({m/g})n})]^g.$$ Hay $m/g$ de estas $\zeta$s y todas son raíces $(m/g)$-ésimas de la unidad, porque $(\zeta^{kn})^{m/g} = (\zeta^m)^{kn/g} = 1$. Usando de nuevo el lema, $$p(1) = p_{m/g}(1)^g = (1+1)^g$$ y el resultado sigue.