Formula for the greatest common divisor of two odd numbers 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}}}.$$
 A: 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.
A: 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.
