0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I think you are correct! Thank's friend. $\endgroup$ – Zain Virani Oct 28 '15 at 0:40
  • $\begingroup$ @Zain: You’re welcome. $\endgroup$ – Brian M. Scott Oct 28 '15 at 0:42
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.