Series representation of GCD(x, y) While playing around with WolframAlpha, I discovered that apparently the GCD of any integers x, y is equal to the following sum:
$$
x + y - xy + 2\sum_{k = 1}^{x-1} \lfloor \frac{ky}{x}\rfloor
$$
I've personally verified that this formula works.
My question is: where does this even come from??? I've searched everywhere and found absolutely nothing. Is there a proof somewhere? Or at least a sketch so I can start thinking about it?
 A: Let $x,y \in \mathbb{N}_0$, and let $d= \gcd(x,y)$. Let also $\displaystyle{S = \sum_{k = 1}^{x-1} \left\lfloor \frac{ky}{x}\right\rfloor}$.
Then one has
\begin{align*} S = \sum_{k = 1}^{x-1} \left\lfloor \frac{ky}{x}\right\rfloor & = \sum_{k = 1}^{x-1} \left\lfloor \frac{(x-k)y}{x}\right\rfloor\\
 & = \sum_{k = 1}^{x-1} \left\lfloor y - \frac{ky}{x}\right\rfloor\\ 
 & = \sum_{k = 1}^{x-1} y +\left\lfloor -\frac{ky}{x}\right\rfloor\\\end{align*}
so you get
$$ S=\sum_{k = 1}^{x-1} \left\lfloor \frac{ky}{x}\right\rfloor = y(x-1) + \sum_{k = 1}^{x-1} \left\lfloor -\frac{ky}{x}\right\rfloor \quad \quad \quad (*)$$
Now notice that for every $k$, one has
$$\left\lfloor -\frac{ky}{x}\right\rfloor =\left\lbrace\begin{array} $-1-\left\lfloor \dfrac{ky}{x}\right\rfloor & \text{if } x \not\mid ky\\ -\left\lfloor \dfrac{ky}{x}\right\rfloor & \text{if } x \mid ky\end{array}\right.$$
But for $k \in \lbrace 1, ..., x-1 \rbrace$, one has
$$ x \mid ky  \quad \Longleftrightarrow \quad\frac{x}{d} \mid k\frac{y}{d} \quad\Longleftrightarrow \quad\frac{x}{d} \mid k\quad\Longleftrightarrow \quad k \in \left\lbrace \dfrac{x}{d}, \dfrac{2x}{d}, ..., \dfrac{(d-1)x}{d} \right\rbrace$$
So $\mathrm{Card} \lbrace k \in \lbrace 1, ..., x-1 \rbrace \text{ such that }x \mid ky \rbrace = d-1$, so one deduce that
$$\sum_{k = 1}^{x-1} \left\lfloor -\frac{ky}{x}\right\rfloor  = \left(\sum_{k = 1}^{x-1} -1-\left\lfloor \frac{ky}{x}\right\rfloor\right) + d-1 = -x-S+d$$
Using $(*)$, you get finally that
$$S = y(x-1)-x-S+d = yx-y-x - S + d$$
so $$\boxed{\gcd(x,y)=x+y-xy+2\sum_{k = 1}^{x-1} \left\lfloor \frac{ky}{x}\right\rfloor}$$
