Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

Prove that $( \frac{l}{(l,m)},\frac{m}{(l,m)}) = 1$, given that $l, m \in \Bbb{N}$. I had this question on my number theory final that I took earlier today. This was the second part of a 2 part question, where the other piece is asked here.

I would like to go through the solution that I put down and then ask whether or not my version is rigorous enough to be considered a good proof.


Let $l = a_1 a_2 a_3...a_n x$ and $m = b_1 b_2 b_3...b_nx$, where $(l,m) = x$. This means that the common factors

Then if we look at $\frac{l}{(l,m)}$, we get $\frac{l}{(l,m)} = \frac{a_1 a_2 a_3...a_n x}{x} = a_1 a_2 a_3...a_n$. Similarly, looking at $\frac{m}{(l,m)}$, we get $\frac{m}{(l,m)} = \frac{b_1 b_2 b_3...b_nx}{x} = b_1 b_2 b_3...b_n$.

Now if we look at $(\frac{l}{(l,m)},\frac{m}{(l,m)})$, we get $(a_1 a_2 a_3...a_n, b_1 b_2 b_3...b_n)$ and since the common factors of $l$ and $m$ have been divided away and thus the gcd of $(\frac{l}{(l,m)},\frac{m}{(l,m)}) = 1$. $\blacksquare$

share|cite|improve this question

marked as duplicate by Thomas Andrews, Amzoti, lhf, vonbrand, Joe May 2 '13 at 2:05

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

The idea behind your proof is definitely correct. Did your class ever cover Bezout's Identity? That would make for a neater solution imo (less "$\ldots$" flying around.) – Joseph G. May 2 '13 at 0:53

There is no need to have the products $a_1\cdots a_n$ and $b_1\cdots b_n$. They weaken the argument, and raise all sorts of questions, such as are the $a_i$, $b_i$ prime? If so, why are there exactly as many for $l$ as there are for $m$?

I do not know what definition of $\gcd$ you use. There are two common possibilities: (i) $x$ is a gcd of $l$ and $m$ if $x$ divides both and nothing bigger than $x$ does or (ii) $x$ is a gcd of $l$ and $m$ if $x$ divides both and for any common divisor $y$, we have $y|x$. We will assume that definition (i) is being used.

Since $x$ is a gcd of $l$ and $m$, $l=ax$ and $m=bx$ for some integers $a$ and $b$. Moreover, $a$ and $b$ are relatively prime, for if $e\gt 1$ divides both $a$ and $b$, then $ex$ divides both $l$ and $m$, contradicting the fact that $x$ is a greatest common divisor of $a$ and $b$.

Now continue exactly as you did: we have $\frac{l}{(l,m)}=a$ and $\frac{m}{(l,m)}=b$. But we have already observed that $(a,b)=1$.

share|cite|improve this answer

You haven't defined well what are the factors in $l = a_1a_2a_3...a_nx$. Probably, they are primes, not necessary distinct, such that $a_i \ne b_j \forall i,j $. And also, you should have used a diferent letter for the number of factors in $b$. I think define well the things I just mentioned is important for your argument.

Other thing to consider is the definition used for gcd. One interesting is that the gcd of $a$,$b$: $(a,b)$ is the minimum positive number that can be written as $ax+by$, with $x,y \in \mathbb Z$.

Using this definition, you have that $(a,b) | a$, because otherwise $a = q.(a,b)+r$ with $(a,b)>r>0$ and $r = a(1-xq)-bqy$ would be smaller. Analogously, $(a,b) | b$.

To prove what you want, just use the fact that there are numbers $x,y$ such that $xa+yb = (a,b)$. Using these numbers, you have that $ x\frac{a}{(a,b)} + y\frac{b}{(a,b)} = \frac{(a,b)}{(a,b)}=1$, the smaller positive number.

share|cite|improve this answer

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