Is $\gcd(x+y, xy)-\gcd(x, y)$ an even or odd number?

Question

Let's say $d=\gcd(x, y)$

I realize that $d$ is a common divisor of $x+y$ and $xy$, and their greatest common divisor would be some multiple of $d$, let's say $kd$. So $$\gcd(x+y, xy)-\gcd(x, y)=kd-d=d(k-1)$$ so since $d$ can be any value it depends on whether $k-1$ is always even or odd so that it would make the whole thing even/odd.

That's where I get lost. I don't have a lot of experience on this subject so I might be way off. And sorry if the formatting is bad I'm struggling on mobile.

Anyway, thank you in advance.

Answer 1

Suppose $x$ and $y$ are both even. Then $\gcd(x+y,xy)$ and $\gcd(x,y)$ are both even as well, and the difference of two even numbers is again even.

Now, suppose that at least one of these is odd. Then one of $x+y$ or $xy$ is odd and it follows that $\gcd(x+y,xy)$ and $\gcd(x,y)$ are both odd as well. The difference of two odd numbers is even.

As such, $\gcd(x+y,xy)-\gcd(x,y)$ is always even.

Answer 2

Welcome on StackExchange.

As you correctly wrote, if $d:=\mathrm{gcd}(x,y)$ and $k:=\frac{\mathrm{gcd}(x+y,xy)}{d} \in \mathbf{N}$, then $$ S:=\mathrm{gcd}(x+y,xy)-\mathrm{gcd}(x,y)=d(k-1). $$ At this point, if $d$ is even then clearly $S$ is even. Hence, our question would be: is $S$ always even?

To find a counterexample, if it exists, you would need that both $d$ and $k-1$ are odd, that is, $d$ odd and $k$ even. Ok, so suppose that $d$ is odd, and make the substitution $x=dX$ and $y=dY$, with $\mathrm{gcd}(X,Y)=1$. It follows that $$ S=d\left(\mathrm{gcd}(X+Y,dXY)-\mathrm{gcd}(X,Y)\right)=d\left(\mathrm{gcd}(X+Y,dXY)-1\right). $$ Now, what is the value of $\mathrm{gcd}(X+Y,dXY)$? $X$ is coprime with $Y$, hence this is equal to $\mathrm{gcd}(X+Y,d)$, hence a divisor of $d$, which is an odd number. To conclude: $$ \textstyle S=d\left(\underbrace{\mathrm{gcd}(X+Y,d)}_{\text{odd}}-1\right) $$ implies that $S$ is always even.

Answer 3

Assume everything relevant is an integer.

$\gcd(even,even) = even$[1]

$\gcd(X, odd) = odd$.[2]

$X\cdot even = even$[3]

$odd \cdot odd = odd$[4]

$odd \pm even = odd$ but $same \pm same = even$.[5]

Those should get you the answer.

$\gcd(even + even, even*even) - \gcd(even,even) = \gcd(even,even)-\gcd(even,even) = even - even = even$.

$\gcd(even+odd, even*odd) -\gcd(even, odd) = \gcd(odd, even)-\gcd(even,odd)=odd-odd = even$.

$\gcd(odd+odd, odd*odd) - \gcd(odd,odd) = \gcd(even, odd)-\gcd(odd,odd)=odd -odd = even$.

So, yes, $\gcd(x+y, xy) -\gcd(x,y)$ is always even.

........

[1] through [5] are obvious, yes?

[1]. Even numbers are divisible by $2$ so their $\gcd$ will be divisible by $2$.

[2]. Odd numbers do not have $2$ as a prime factor so no common factor with an odd number will have $2$ as a prime factor.

[3]. Every multiple of a multiple of $2$ is a multiple of $2$.

[4]. a) euclids lemma says if $2|x,y$ then $2|x$ or $2|y$ so if $x$ and $y$ are both odd $2|xy$ is impossible. (Are we could do the elementary way: $(2k+1)(2j+1) = 2(2kj +k + j) +1$.)

[5]. Hmmm... it'd be fun to come up with the single slimmest line to argue this. Not sure what the slickest argument is, but some not slick ones are obvious.

$X + even = parity\ of \ X$ because $2|even$ so $2|X+even \iff 2|X$. and $X + odd = opposite \ parity \ of \ X$ because $2\not \mid odd$ so $odd \equiv \pm 1 \pmod 2$ and $X+odd \equiv X\pm 1 \equiv \begin{cases}0+1=1\\1-1=0 \end{cases}$.

But that's the exact opposite of slick.

Guess we should go with the inelegant: $same \pm same = (2j+\begin{cases}0\\1\end{cases}) \pm (2k\mp\begin{cases}0\\1\end{cases})= 2(j\pm k)=even$ whereas $odd \pm even = (2k+1) \pm 2j = 2(k\pm j) + 1 = odd$.

Answer 4

It's even: the gcds have equal parity since prime $\!\!\!\!\!\!\!\overbrace{p\mid x\!+\!y,xy \iff p\mid x,y}^{\textstyle x\!+\!y\equiv 0\equiv xy\iff x\equiv 0\equiv y}\!\!\!\!\!\! $ (here $\,p=2)$.

Answer 5

This is not the slickest proof, but illustrates the use of $\gcd (a, b)=\gcd(b, b-a)$ which can come in handy in simplifying problems of this type, and is a technique worth noting.

Note that $\gcd(x+y, xy)= \gcd (xy, xy-x-y)=\gcd (xy, (x-1)(y-1)-1)$ and this is clearly odd unless $x$ and $y$ are both even (one of the two numbers is odd).

If both $x$ and $y$ are even, then both gcds are even. Otherwise, both are odd.

If you believe parity is constant as suggested in the question, setting $x=y=1$ solves it for you.