If ab = m(a,b), prove that m = [a,b]

[Ken Miller]

Homework Statement

Let a and b be positive integers, and let m be an integer such that ab = m (a,b). Without using the prime factorization theorem, prove that (a,b) [a,b] = ab by verifying that m satisfies the definition of [a,b], as follows:

Relevant Equations

The notation [a,b] is used for the least common multiple of a and b, where
i: [a,b] is a multiple of both a and b.
ii: Any multiple of both a and b is a multiple of m.
The notation (a, b) is used for the greatest common divisor of a and b.

First, prove that [a,b] is a divisor of both a, b:

By definition, (a,b) | a and (a,b) | b.
So for some integers j and k,
a = (a,b) j and b = (a,b) k.

Multiplying the last two equations yields: ab = (a,b)^2 * jk.
But we are given that ab = m (a,b).
Equating the two expression for ab yields: (a,b)^2 * jk = m (a,b).
Dividing both sides by (a,b) gives: (a,b) jk = m.
Rearranging the factors two different ways:
[(a,b) j ] k = m and [(a,b) k] j = m.
But [(a,b) j ] k = a and [(a,b) k ] j = b.
So
ak = m and bj = m.
But this means that a|m and b|m. So m is a common multiple of a and b. So, I proved the first half of the definition.

Now I want to prove the second half of the definition, namely that any other multiple of a and b is a multiple of m. It seems like it should be trivial, but I can’t seem to come up with the logic. Of course, I can come up with many examples, but no “reason” why it must be so.

 

[fresh_42]

You do not need $j$ and $k$. It is given that $ab=m(a,b)$, which implies $j=k=m$. Are you allowed to apply ring theory?

 

[Ken Miller]

I don't understand. Can you tell me what is wrong with the first three lines of my proof? Namely:

By definition, (a,b) | a and (a,b) | b.
So for some integers j and k,
a = (a,b) j and b = (a,b) k

By definition, m is what I get when I divide ab by (a,b). I'm naming j what I get when I divide a by (a,b) and I'm naming k what I get when I divide b by (a,b). m, j, and k, are generally three different numbers.

Re. what I'm allowed to use: No, no ring theory. I'm just starting to work my way through Beachy and Blair. I'm in section 1.2, and the only things covered so far are:
Well-ordering Principal
Divisibility, including division algorithm
GCD and LCM (including expressing GCD as smallest linear combination)
Euclidean Algorithm
Prime and relatively prime numbers
Fundamental theorem of arithmetic (Prime factorization)
Euclid's theorem
And a few basic propositions, such as
--b|ac => b|(a,b) c
--If b|ac and (a,b) = 1, then b|c
--If b|a and c|a and (b,c) = 1, then bc|a
--(a, bc) = 1 iff (a,b) = 1 and (a,c) = 1

 

[fresh_42]

There is nothing wrong, with these three lines, except in the line ahead of them: $[a,b]$ does not divide $a$ nor $b$, except one of them is $\pm 1$.

I mistakenly read them as $ab=j(ab)$, sorry. The mistake is further down.
We have $m=(a,b)jk$, but how do we get $[(a,b) j ] k = a$ and not $[(a,b) j ] k = ak$?

The shortest proof is probably to use the prime factor decomposition. It allows you to write $[a,b]$ and $(a,b)$ explicitly.

 

[Ken Miller]

The errors you found were due to my typing things very differently than what I intended!
First, where I wrote:
"First, prove that [a,b] is a divisor of both a, b:"
I meant to write:
"First, prove that m is a multiple of both a, b:"

Second, where I wrote:
"But [(a,b) j ] k = a and [(a,b) k ] j = b"
I meant to write:
"But [(a,b) j ] = a and [(a,b) k ] = b"

Is there a way I can perhaps edit/clean up and resubmit the question in a new thread (and perhaps delete this thread)? Or would it be better to redo the proof in one of these replies?

With those corrections, I'm pretty sure that I've proved that m is a common multiple of a and b. It's the next part that I'm having trouble with, namely proving that no other common multiple is smaller than m.

And, no, I'm not allowed to use the prime factorization theorem, per the problem statement.

 

[fresh_42]

How about here? Just start from the beginning. You can copy and paste what you need from the above, but maybe you forget it and try to rephrase it. If possible, use LaTeX (see here for an explanation), or at least type in

 ##

before and after a formula:
# #[a,b](a,b)=a\cdot b # # without the blank between the sharps becomes $[a,b](a,b)=a\cdot b$ and is easier to read.

 

[Ken Miller]

OK, here is the problem from the start, with my corrections of the errors you found.

Problem Statement
Let $a$ and $b$ be positive integers, and let $m$ be an integer such that $ab = m (a,b)$. Without using the prime factorization theorem, prove that $(a,b) [a,b] = ab$ by verifying that $m$ satisfies the definition of $[a,b]$, as follows:

Relevant Equations
$[a,b]$ is the least common multiple of $a$ and $b$, defined as follows:
i: $[a,b]$ is a multiple of both $a$ and $b$.
ii: Any multiple of both $a$ and $b$ is a multiple of $m$.
The notation $(a, b)$ is used for the greatest common divisor of $a$ and $b$.

Attempt at a Proof:
First, I must prove that $m$ is a multiple of both $a$ and $b$:

By definition, $(a,b) | a$ and $(a,b) | b$.
So for some integers $j$ and $k$,
$a = j(a,b)$ and $b = k(a,b)$.

Multiplying the last two equations yields:
$ab = jk (a,b)^2$.
But we are given that $ab = m (a,b)$.
Equating the two expression for $ab$ yields: $jk (a,b)^2 = m (a,b)$.
Dividing both sides by $(a,b)$ gives: $jk (a,b) = m$.
Rearranging the factors two different ways:
$[j (a,b)] k = m$ and $[k (a,b)] j = m$.
But $[j (a,b)] = a$ and $[k(a,b)] = b$.
So
$ak = m$ and $bj = m$.
But this means that $a|m$ and $b|m.$ So $m$ is a common multiple of $a$ and $b$. So, I proved the first half of the definition.

Now I want to prove the second half of the definition, namely that any other multiple of $a$ and $b$ is a multiple of $m$. It seems like it should be trivial, but I can’t seem to come up with the logic. Of course, I can come up with many examples, but no “reason” why it must be so.

Regarding what I'm allowed to use in the proof: not ring theory and not the prime factorization theorem. I'm just starting to work my way through Beachy and Blair. I'm in section 1.2, and the only things covered so far are:
Well-ordering Principal
Divisibility, including division algorithm
GCD (a, b) and LCM [a,b] (including expressing GCD as smallest linear combination)
Euclidean Algorithm
Prime and relatively prime numbers
Fundamental theorem of arithmetic (Prime factorization) (Not allowed to use this)
Euclid's theorem
And a few basic propositions, such as
--$b|ac => b|(a,b) c$
--If $b|ac$ and $(a,b) = 1$, then $b|c$.
--If $b|a$ and $c|a$ and $(b,c) = 1$, then $bc|a$
--$(a, bc) = 1$ iff $(a,b) = 1$ and $(a,c) = 1$

 

[fresh_42]

What do you think about the following simplification:
We have $m(a,b)=ab$. Thus $\hat m:=\dfrac{m}{(a,b)}=\dfrac{a}{(a,b)} \,\cdot\,\dfrac{b}{(a,b)} =:\hat a \hat b$ with coprime numbers $\hat a$ and \hat b##.

 

[Ken Miller]

It seems important that you showed that $\hat a$ and $\hat b$ are coprime, which I hadn't done.
But I'm having trouble using that fact. How does that help?

By the way, I thought I might try a proof-by-contradiction to show that any common multiple of $a$ and $b$ is a multiple of $m$. Let $n$ be any common multiple of $a$ and $b$. Then by definition $n = ra$ for some $r$ and $n = sb$ for some $s$. Assume that $n < m$. $$n<m => ra < a\cdot (b/(a,b)) => r < b/(a,b)$$. And $$n<m => sb < (a/(a,b))\cdot b => s < a/(a,b)$$. But I don't see how to prove that this contains a contradiction.

 

[fresh_42]

It seems important that you showed that $\hat a$ and $\hat b$ are coprime, which I hadn't done.
But I'm having trouble using that fact. How does that help?

By the way, I thought I might try a proof-by-contradiction to show that any common multiple of $a$ and $b$ is a multiple of $m$. Let $n$ be any common multiple of $a$ and $b$. Then by definition $n = ra$ for some $r$ and $n = sb$ for some $s$. Assume that $n < m$. $$n<m => ra < a\cdot (b/(a,b)) => r < b/(a,b)$$. And $$n<m => sb < (a/(a,b))\cdot b => s < a/(a,b)$$. But I don't see how to prove that this contains a contradiction.

The proof definitely needs the defining property of $m$ at some stage, i.e. $m(a,b)=ab$. Such proofs use usually $x|y$ instead of the order $x<y$ and equality is often shown by $x|y \wedge y|x$.

Anyway, my thought was: if we can assume that $a$ and $b$ are coprime, then we know $[a,b]=ab$. So if we can show the statement for $\hat a \, , \,\hat b$, then we only have to replace them again to get the statement for $a\, , \,b$.

 

[Ken Miller]

I was just thinking something along the lines of what you wrote. Does the following work?

Since $\hat a$ and $\hat b$ are coprime, then $[\hat a, \hat b] = \hat a \cdot \hat b$.
Since $(a,b)$ is not a factor of $\hat a$ nor of $\hat b$, then

$[\hat a, \hat b \cdot (a,b)] = \hat a \cdot \hat b \cdot (a,b)$.

But then
$[\hat a \cdot (a,b), \hat b \cdot (a,b)] = \hat a \cdot \hat b \cdot (a,b)$.
That is, multiplying $\hat a$ by $(a,b)$ does not change the [], since (a,b) is already a factor of $\hat b \cdot (a,b)$.

But the left-hand side of the last equation is just $[a,b]$. So we get
$[a,b] = \hat a \cdot \hat b \cdot (a,b)$.

Mulitply both sides by $(a,b)$ =>
$[a,b](a,b) = \hat a \cdot \hat b \cdot (a,b) \cdot (a,b)$.

Now the right-hand side is just $a \cdot b$. So
$[a,b](a,b) = a \cdot b$.

But, we are given that$(a,b) = a \cdot b$. So $m = [a,b]$.I think that the weak part in my argument is that I haven't really "proved" the statements leading up to:
$[a,b] = \hat a \cdot \hat b \cdot (a,b)$.

Is that part so obvious that I don't need to "prove" it?

 

[fresh_42]

I have difficulties to understand this.

I was just thinking something along the lines of what you wrote. Does the following work?

Since $\hat a$ and $\hat b$ are coprime, then $[\hat a, \hat b] = \hat a \cdot \hat b$.
Since $(a,b)$ is not a factor of $\hat a$ nor of $\hat b$, then

Do you use my definitions $\hat a = \dfrac{a}{(a,b)}\, , \,\hat b = \dfrac{b}{(a,b)}$ or arbitrary coprime numbers $\hat a\, , \, \hat b \,$? The second case would require some connection which you did not mention, so I guess you use my definitions of the hats. I should not have to guess. Why don't you say it?

$[\hat a, \hat b \cdot (a,b)] = \hat a \cdot \hat b \cdot (a,b)\quad (*)$.

As I see it, this is exactly what has to be shown! Why is this so? Couldn't it be, that $(a,b)|\hat a\, \wedge \,(a,b) \nmid \hat b$ or that some prime factors of $(a,b)$ are in $\hat a$ and some in $\hat b \,?$

Here is what I mean: We have $[\hat a,\hat b]=\hat a \hat b=m(\hat a,\hat b)=m\cdot 1=m$ for all coprime numbers $\hat a\, , \,\hat b$. That is: the theorem is true for coprimes. For arbitrary $a\, , \,b$ we have $\dfrac{m}{(a,b)}=\dfrac{a}{(a,b)}\dfrac{b}{(a,b)}=\left[\dfrac{a}{(a,b)},\dfrac{b}{(a,b)}\right]\,.$
If we can show $(a,b)\cdot \left[\dfrac{a}{(a,b)},\dfrac{b}{(a,b)}\right] = [a,b]\quad (**)$ we will be done. But why is it the case?

O.k., let us assume $(*)$ is correct and I just don't see it at the moment.

But then
$[\hat a \cdot (a,b), \hat b \cdot (a,b)] = \hat a \cdot \hat b \cdot (a,b)$.
That is, multiplying $\hat a$ by $(a,b)$ does not change the [], since (a,b) is already a factor of $\hat b \cdot (a,b)$.

But the left-hand side of the last equation is just $[a,b]$. So we get
$[a,b] = \hat a \cdot \hat b \cdot (a,b)$.

Mulitply both sides by $(a,b)$ =>
$[a,b](a,b) = \hat a \cdot \hat b \cdot (a,b) \cdot (a,b)$.

Now the right-hand side is just $a \cdot b$. So
$[a,b](a,b) = a \cdot b$.

But, we are given that$(a,b) = a \cdot b$. So $m = [a,b]$.

This is a typo. We are given $m(a,b)=ab$, i.e. with the previous line $[a,b](a,b)=ab=m(a,b)$ or $[a,b]=m\,.$ Done.

I think that the weak part in my argument is that I haven't really "proved" the statements leading up to:
$[a,b] = \hat a \cdot \hat b \cdot (a,b)$.

Is that part so obvious that I don't need to "prove" it?

Now everything depends on either to show $(*)$ or $(**)$.

 

[Ken Miller]

Before I continue, I want to express my appreciation for sticking with me through my confusion!

Yes, I was using your $\hat a$ and $\hat b$. Apologies.
And I see now that the my reasoning leading to the equation you marked $(*)$ is not correct. Yes, you are right that it is possible that $(a,b)| \hat a$ or $(a,b)| \hat b$. For instance, if $a = 4$ and $b= 16$, then $(a,b) = 4$, $\hat a = 1$, $\hat b = 4$, so $(a,b)$ is a factor of $\hat b$.

OK, I need to think some more about this!

 

[fresh_42]

Try the following: $a\cdot b = j\cdot (a,b) \cdot k \cdot (a,b)$ from your first post. Now determine $[a,b]$ in terms of $a,b,j,k$ and calculate $[a,b]\cdot (a,b)$.

 

[Ken Miller]

Well, the only path I can find relies on something that I'm not sure I can legitimately assert.
It seems self-evident that, given any positive integer $x$, $[x, x] = x$. And I'm sure it's true that $[xy, xz] = x[y, z]$, whether or not $y$ and $z$ are coprime, but it doubt I can assert that without proof. But assume for the moment that it is given or proved. Then we have:
$[a,b] = [j(a,b), k(a,b)] = [j, k] (a,b) = jk (a,b)$, since $j$ and $k$ are coprime (they are the same as your $\hat a$ and $\hat b$).
So $[a, b] (a, b) = jk (a,b) (a,b) = ab$. But $m (a,b) = ab$. So $m = [a, b]$.

That all looks nice, but I'm afraid I'm still going around in circles with what I'm relying on.

 

[fresh_42]

Well, the only path I can find relies on something that I'm not sure I can legitimately assert.
It seems self-evident that, given any positive integer $x$, $[x, x] = x$. And I'm sure it's true that $[xy, xz] = x[y, z]$, whether or not $y$ and $z$ are coprime, but it doubt I can assert that without proof. But assume for the moment that it is given or proved.

Let's do it quickly: $x=\prod p_i^{r_i}\; , \;y=\prod p_j^{s_j}\; , \;z=\prod p_k^{t_k}\, , \,r_i,s_j,t_k \geq 0$. Then
\begin{align*}
[xy,xz]&=\left[\prod p_i^{r_i}\prod p_i^{s_i},\prod p_i^{r_i}\prod p_i^{t_i}\right]=\left[\prod p_i^{r_i+s_i},\prod p_i^{r_i+t_i}\right]\\&=\prod p_i^{\max\{\,r_i+s_i\, , \,r_i+t_i\,\}}=\prod p_i^{r_i +\max\{\,s_i\, , \,t_i\,\}}=x\cdot [y,z]
\end{align*}

Then we have:
$[a,b] = [j(a,b), k(a,b)] = [j, k] (a,b) = jk (a,b)$, since $j$ and $k$ are coprime (they are the same as your $\hat a$ and $\hat b$).
So $[a, b] (a, b) = jk (a,b) (a,b) = ab$. But $m (a,b) = ab$. So $m = [a, b]$.

That all looks nice, but I'm afraid I'm still going around in circles with what I'm relying on.

And, it also looks correct.

The only question is, whether you want to substitute my primes with a prime free version of $[xy,xz]=x[y,z]$, in which case I would reason with dividers and show that both sides divide each other.

 

[Ken Miller]

OK. :) I think you closed the circle. I'm going to declare this one finished for now. At some point, when I have some distance from it, I'll come back to it and see if I can do it much more concisely. Thanks much for your support and input.