# How to prove $\left(\frac{a}{(a,b)}, \frac{b}{(a,b)}\right) = 1$?

I have a number theory question that has me stumped.

Let $a, b, c \in \Bbb Z$ with $a$ and $b$ both not zero. Prove: $(\frac{a}{(a,b)}, \frac{b}{(a,b)}) = 1$.

Any help would be greatly appreciated!

• $(k a, k b) = k (a, b)$ – vonbrand Apr 4 '13 at 0:42
• What do you know? An answer will depend on what stage you’re at in number theory. – Lubin Apr 4 '13 at 0:43
• Please make titles more informative. See what I changed it to, so you can do something similar next time. – Pedro Tamaroff Apr 4 '13 at 0:51
• Where is $c$ used? – Thomas Andrews Apr 4 '13 at 1:03
• It is the speed of light, rounded down... – copper.hat Apr 4 '13 at 1:44

@vonbrand's comment is the most succinct answer. Here is a more verbose approach:

Let $d =\gcd(a,b)$. Let $l = \gcd(\frac{a}{d}, \frac{b}{d})$. Then $l \mid \frac{a}{d}$, $l \mid \frac{b}{d}$, which implies $ld \mid a$, $ld \mid b$. Hence $ld \le d$, from which we get $l \le 1$. Since $1 \mid a$, $1 \mid b$, we have $1 \le l$. So $l=1$.

$$ax+by=(a,b)$$ has a solution. Divide by $(a,b)$.

Bezout's identity will give you the answer immediately: http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity

It tells us that there exist integers $x,y$ such that $$xa+yb=(a,b).$$Divided by $(a,b)$ gives $x\frac{a}{(a,b)}+y\frac{b}{(a,b)}=1$, and note that the GCD of $\frac{a}{(a,b)}$ and $\frac{b}{(a,b)}$ must divide the RHS.

It is simply the special case $\: c = (a,b)\:$ of the $\,$ gcd distributive law $\ (a/c,b/c) = (a,b)/c$

See here for a few proofs of distributivity (by linearity (Bezout); universality; prime factorization).