Property of greatest common denominators proof

[skate_nerd]

This problem has been taunting me for days now, and I still have no idea of where to start with it...
Let \(m\) and \(n\) be non-zero integers. We say that \(k\) is a common divisor of \(m\) and \(n\) if \(k|m\) and \(k|n\). The greatest common divisor of \(m\) and \(n\), denoted as \(gcd(m,n)\), is the number positive \(b\) satisfying
(i) \(b\) is a common divisor of \(m\) and \(n\), and
(ii) every common divisor of \(m\) and \(n\) is also a divisor of \(b\).
Now let \(m\), \(n\), and \(j\) be non-zero integers. Prove that \(gcd(jm,jn)=j\cdot{gcd(m,n)}\).
I'm mostly just used to writing proofs about set theory or proving formulas with induction and algebraic manipulation and stuff like that, but I have no idea how to come up with any kind of workable formula out of a proposition like this. Any help with where to start would be very appreciated

 

[Ackbach]

I'm not sure I see the way through to the finish line, but surely starting out as follows would work somehow:

Let $p=\gcd(jm,jn).$ Then

1. $p|jm$ and $p|jn$, and
2. If $k \in \mathbb{Z}$ and $k|jm$ and $k|jn$, then $k|p$.

Let $q=\gcd(m,n)$. Then

1. $q|m$ and $q|n$, and
2. If $k \in \mathbb{Z}$ and $k|m$ and $k|n$ then $k|q$.

Because $q|m$, then $q|jm$. Because $q|n$, then $q|jn$. Therefore, because $p= \gcd(jm,jn)$, under its #2 there, it follows that $q|p$, say, $q \cdot s=p$. You want to show that $s=j$.

 

[skate_nerd]

Okay so I started with a couple of the ideas you provided, if you want to check this for me and see if it doesn't use any kind of fallacious reasoning that would be nice. I'm pretty sure it doesn't...

Let us call the statement gcd(jm,jn)=b. We want to prove that this leads to b=j*gcd(m,n). This latter statement can be rewritten as b/j=gcd(m,n).
We can call k the value of greatest common divisor of m and n, so k=b/j (kℤ). This leads to b=kj, meaning j|b and k|b.
If we know that b=gcd(jm,jn), we also know that b must be a common divisor of jm and jn, or in other words b|jm and b|jn. This can be rewritten as two formulae, b=pjm and b=qjn, for all non-zero p,qℤ.
Now we can deduce that b=kj=pjm=qjn.
Since kj=pjm, then k=pm, and similarly, since kj=qjn, then k=qn. These two statements give us the truths that n|k and m|k, meaning that k is the greatest common divisor of m and n. Backtracking, we know that we defined k=b/j. Because we just proved k=gcd(m,n), we know b/j=gcd(m,n), and therefore, b=jgcd(m,n). Thus, we have arrived at the desired conclusion. Q.E.D.

 

[Ackbach]

Well, I think your proof is going to need a little work before it's good. I'll quote and reply for you:

Let us call the statement gcd(jm,jn)=b. We want to prove that this leads to b=j*gcd(m,n). This latter statement can be rewritten as b/j=gcd(m,n).
We can call k the value of greatest common divisor of m and n, so k=b/j (kℤ).

This is a rather confusing way to word things. If k is the greatest common divisor of m and n, then you want to prove that k=b/j. You don't get to assume it!

This leads to b=kj, meaning j|b and k|b.
If we know that b=gcd(jm,jn), we also know that b must be a common divisor of jm and jn, or in other words b|jm and b|jn. This can be rewritten as two formulae, b=pjm and b=qjn, for all non-zero p,qℤ.

There are two problems with this last statement. First of all, if b|jm, that means that pb = jm, not b = pjm. Second of all, it's definitely NOT true for all non-zero p, q in ℤ. It means that there exists a particular p and q such that pb = jm and bq = jn.

Now we can deduce that b=kj=pjm=qjn.

This is very confusing. Are you assuming that b = kj? As I said before, this is what you are trying to prove. Also, is this statement a header organizing your proof, or are you now claiming (without any further steps) that this statement is true? In context, you appear to be making this claim.

Since kj=pjm, then k=pm, and similarly, since kj=qjn, then k=qn. These two statements give us the truths that n|k and m|k, meaning that k is the greatest common divisor of m and n. Backtracking, we know that we defined k=b/j. Because we just proved k=gcd(m,n), we know b/j=gcd(m,n), and therefore, b=jgcd(m,n). Thus, we have arrived at the desired conclusion.Q.E.D.

All of this block of reasoning depends on b = kj, which is what you are trying to prove. b = kj needs to be at the very end of the proof, and it cannot appear any earlier, by the rules of proofs.

Hopefully, these comments can steer you towards a better solution.

 

[skate_nerd]

Thanks for the pointers. I see what you are saying about the "illegal" assumption I made. I think I could tell that was probably not okay to assume but I wanted to see if I could get through the rest after doing it...
So I just have a couple questions:
To make a proof about a greatest common denominator will I therefore be forced to use some kind of proof utilizing inequalities?
And second, when I am proving an equality like this, is it similar to proving an if and only if statement? In that I would need to start from each side of the equation and deduce the other side, making the proof split into two parts?

 

[Ackbach]

Thanks for the pointers. I see what you are saying about the "illegal" assumption I made. I think I could tell that was probably not okay to assume but I wanted to see if I could get through the rest after doing it...

That can be a valid method of proof, actually, so long as every step in the proof is reversible. That is, for every step in the proof, both the step and its converse are true. I don't get that feeling with this proof, however.

So I just have a couple questions:
To make a proof about a greatest common denominator will I therefore be forced to use some kind of proof utilizing inequalities?

Not necessarily. Some greatest-common-divisor proofs utilize inequalities, since if $a|b$, that always implies that $a \le b$. And you're talking about the greatest common divisor. You could, equivalently, define the greatest common divisor this way: $b = \gcd(m,n)$ if $b|m$ and $b|n$, and if $a$ is any other integer that divides both $m$ and $n$, then $b \ge a$.

And second, when I am proving an equality like this, is it similar to proving an if and only if statement? In that I would need to start from each side of the equation and deduce the other side, making the proof split into two parts?

This theorem is a purely if-then type of theorem. You get to assume the assumptions of the theorem:

1. $m$ and $n$ and $j$ are non-zero integers
2. The definition of the gcd.

Then you need to prove, using these assumptions, that $\gcd(jm,jn)=j \cdot \gcd(m,n)$.

An if-and-only-if theorem will always explicitly state it as such (or use words like "the following are all equivalent").

 

[skate_nerd]

I really appreciate all the help Ackbach. Also you could maybe tell but I keep saying greatest common denominator by accident instead of greatest common divisor. I think its just something stuck in my brain since years ago in those early algebra classes...

 

[johng1]

Hi skatenerd,
Whenever I have a problem that involves gcd, one of my first thoughts is the fact that there are integers x and y such that ax + by = gcd(a,b). So here's an alternate proof using this fact:

Let k = gcd(a,b). "Clearly" dk divides both da and db. Let x and y be integers with ax + by = k. Then dax + dby = dk. If e divides both da and db, then e divides dax + dby =dk. Thus gcd(da,db) = dk.

If you're interested, the attachment has more discussion about ax + by = gcd(a,b):

View attachment 1570