Formula for the greatest common divisor of two odd numbers

Question

I was taking the determinant of the adjacency matrix for a graph and I stumbled across this interesting (apparent) coincidence:

If $m$ and $n$ are odd numbers, then $$ 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).$$

If we take $\log_2$ of both sides, we get an explicit expression describing the greatest common divisor. Would anyone like to attempt a proof of this fact?

Here is some MATLAB code which checks the above formula. (Save it as a *.m file in your MATLAB directory; then use greatcd(m,n) to output the greatest common divisor of your chosen odd numbers $m$ and $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))

It appears that if $g = \textsf{gcd}(m,n)$, then $$\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)$$ and I also think that $$ \prod_{l=1}^{ng^{-1}} \left( 1 + e^{\frac{2l\pi i}{ng^{-1}}}\right) = 2.$$ If I hold $l$ fixed and take the product over $k$, I appear to get $$\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

Here is an "asymmetric" proof. The idea is to introduce an indeterminate $X$ and regard the product as some polynomial evaluated at $X = 1$. The key lemma is that if $m$ is odd and $\zeta$ is an $m$th root of unity then the roots of $p_m(X) := X^m + 1$ are the negatives of the roots of $X^m - 1$, because if $z^m = 1$ then $(-z)^m = (-1)^m z^m = -1$. Therefore, $$p_m(X) = \prod_{k=1}^m (X + \zeta^k).$$ We will use this identity below for $n$ and also for $m/g$, where $g = \text{gcd}(m, n)$.

First, let $\zeta$ and $\eta$ be primitive $m$ and $n$th roots of unity, respectively (e.g. $\zeta = e^{2\pi i / m}$). Introduce $X$, and simplify using the lemma:
$$p(X) = \prod_{k=1}^m \prod_{l=1}^n (\zeta^k X + \eta^l) = \prod_{k=1}^m p_n(\zeta^k X)$$ so
$$\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}).$$

Now because $m$ and $n$ might not be coprime, this product may have repeating terms. But the repetition is very regular. The exponent land is $\mathbb{Z}/m\mathbb{Z}$ (remember, $\zeta$ is an $m$th root of unity) and the map $x \mapsto nx$ has kernel generated by (the equivalence class mod $m$ of) $m/g$. To see this, get $s$ and $t$ such that $ms + nt = g$. If $nx \equiv 0$ (mod $m$) then $ntx = (g - ms)x = gx \equiv 0$ (mod $m$), so $m$ divides $gx$. Since $g$ divides $m$, $m/g$ divides $x$.

Therefore, the whole product is just $g$ copies of the first $m/g$ terms: $$p(1) = [(1+\zeta^n)(1+\zeta^{2n})\dotsb(1+\zeta^{({m/g})n})]^g.$$ There are $m/g$ of these $\zeta$s and they are all $(m/g)$th roots of unity, because $(\zeta^{kn})^{m/g} = (\zeta^m)^{kn/g} = 1$. By the lemma again, $$p(1) = p_{m/g}(1)^g = (1+1)^g$$ and the result follows.

Answer 2

Let $n = 1$ for simplicity.

$\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)$

by symmetry of an odd-sided regular polygon centered at the origin of $\Bbb{C}$ whose vertices are the $m$th roots of unity.

But the rules of complex conjugation yield that $(w^k + 1)^* = (w^{k*} + 1) = w^{-k} + 1$. Thus we have $zz^*$ above and that's always real. Thus for the case $n=1, m\geq 1$ we have proved that the formula is at least a real number.

A similar argument using symmetries of odd-sided regular polygons can be applied to the general case where $n \geq 1, m \geq 1$. Showing that your formula is at least a real number.

Find, that using the same symmetry across the real axis in $\Bbb{C}$ used above that, your general formula is the same as: $$ \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}) $$

---

Note that $0 \leq |w^{\pm k} + z^{\pm l}| \leq 2$. Which can also be seen by looking at regular unit polygons in the $\Bbb{C}$ plane.

As your formula is a real number, we have that $|\text{formula}| = \pm\text{formula}$.

For all the times in the product when $\dfrac{k}{m} = \dfrac{l}{n}$ you'll get $|w^{k} + z^{l}| = |w^{-k} + z^{-l}| = 2$. Convince yourself this happens iff those two fractions are equal in the product. We're gettin' close!

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

I don't really know, so let's look at an example: $m = 15, n = 9, (m,n) = 3$ $0/15 = 0/9, \ 5/15 = 3/9, \ 10/15 = 6/9$

And those were the only examples I could think of, so it seems like you want to prove that the above happens exactly $\gcd(m,n)$ times in general.

So we have shown so far that $\text{your formula} = \pm 2^{\gcd(m,n)}\prod\limits_{k,l = 0; k/m \neq l/n}^{m-1, n-1} (\dots)$.

We haven't employed rotational symmetry yet, so maybe the answer lies there to prove that the magnitude of the remaining piece of your formula $=1$. And by that I mean multiplying by the terms each by the same $e^{i\pi j/?}$ such that the resulting set of vertices is the same as your original two polygons, also known as a rotational symmetry in a Dihedral group.