2
$\begingroup$

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!

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

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\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.