Series representation of GCD(x, y)

Question

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?

Answer 1

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}$$