Suppose $\gcd(a,y)=s$ and $\gcd(b,y)=t$. Prove that $\gcd(\gcd(a,b),y)=\gcd(s,t)$.

Question

All I have so far is that $$s|a, s|y, t|b, \text{ and } t|y.$$ I also know

$$\gcd(\gcd(a,b),y)=\gcd(a,b,y)=\gcd(a,gcd(b,y))$$

by the associative property of gcd. It would suffice to show $$\gcd(a,b,y)=\gcd(gcd(a,y),\gcd(b,y)).$$ I'm just not sure how to prove it. Thanks for your help.

Answer 1

I would approach it a bit differently. Let $d=\gcd(\gcd(a,b),y)$. Then $d\mid\gcd(a,b)$, and $d\mid y$. Since $d\mid\gcd(a,b)$, we also know that $d\mid a$ and $d\mid b$. Since $d\mid a$ and $d\mid y$, we know that $d\mid s$; similarly, $d\mid t$, so $d\mid\gcd(s,t)$.

Now let $e=\gcd(s,t)$ and make a similar argument to show that $e\mid d$. Since $d,e\ge 1$, $d\mid e$, and $e\mid d$, it must be the case that $d=e$.

Answer 2

It depends on how you define $\gcd$. For instance, one way is to define (or prove from your definition of $\gcd$) $$\gcd(x, y) = \prod_{p \text{ primes}} p^{\min(v_p(x), v_p(y)}$$ where $v_p(n)$ is the maximal exponent $e$ such that $p^e | n$. Then the formula you want to show essentially reduces to $$\min(v_p(a), v_p(b), v_p(y)) = \min(\min(v_p(a), v_p(y)), \min(v_p(b), v_p(y)))$$ which should be trivial to verify.

Answer 3

We have : $\gcd(a,y) = s$. And $\gcd(b,y) = t. $ so : $$\gcd(\gcd(a,b),y)= \gcd(a,b,y,y)$$ $$ =\gcd(\gcd(a,y),\gcd(b,y))$$ Which is the same as : $$=\gcd(s,t)$$