Question

Prove:
\[\gcd(ca,cb)=c\gcd(a,b)\]

Answer 1

\[
\begin{align*}
\gcd(ca,cb)&=cam+cby\\\\
c\gcd(a,b)&|(cam+cby)\\
\gcd(a,b)&|am+by\qquad\text{Clearly true.}
\end{align*}\]

Answer 2

Does \(cd|ce\implies d|e\)?

Answer 3

How about the other way?

Answer 4

\(\gcd(ca,~cb)\) is the "minimum" positive values that can be represented as
\[(ca)x+(cb)y\]

Answer 5

Clearly \(\large \min\{(ca)x+(cb)y\} = c~\min\{ax+by\}\)

Answer 6

But \(\large \min\{ax+by\}\) is the \(\large \gcd(a,b)\) by definition. So we have :

\[\large \gcd(ca,cb) =\min\{(ca)x+(cb)y\} = c~\min\{ax+by\} = c\gcd(a,b)\]

Answer 7

My teacher gave this proof.
\[
g=\gcd(a,b)\\
cg=(ca)m+(cb)n\\
\gcd(ca,cb)|ca\land\gcd(ca,cb)|cb\\
\implies \gcd(ca,cb)|c\gcd(a,b)\\
\gcd(ca,cb)|c\gcd(a,b)\land c\gcd(a,b)|gcd(ca,cb)\\
\implies c\gcd(a,b)=\gcd(ca,cb)
\]

Answer 8

@ganeshie8

Answer 9

that looks good too

Answer 10

I find proofs involving gcd and lcm very messy. So many names for the same thing.

Answer 11

Do you see why below one line proof works ?

\[\large \gcd(ca,cb) =\min\{(ca)x+(cb)y\} = c~\min\{ax+by\} = c\gcd(a,b)\]

Answer 12

If you can factor out a constant in a minimum then yes this proof is very clear.

Answer 13

yes, why do you think you're not allowed to factor out a constant ?

\[\large \min\{k (stuff)\} = k\min\{(stuff)\} \]

you will be using that simple observation in many other proofs in discrete math

Answer 14

look at problem4
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2005/assignments/pset3_soln.pdf

Answer 15

Clearly it works but I need a proof to make sure that teachers don't nitpick on me lol.

Answer 16

I am not sure whether this is provable or not since it seems so trivial.

Answer 17

they wont nitpick on you and im sure you teacher doesn't want you make a proof artificially lengthy just for the sake of making it seem "non trivial" :P

Answer 18

All three proofs in this thread work just fine! but that one line proof outsmarts every other proof because thats simple and gives you more insight into linear combination representation and also it touches the more useful definition of gcd

Answer 19

True. I don't like divisibility proof as it is very hard to get a intuitive grasp on what is going on.

Answer 20

Most of these messy looking divisibility proofs can be made simpile by using congruences

Answer 21

The proof of \(\gcd(a,b)\times\text{lcm}(a,b)=ab\) in my book is absolutely confusing.

Answer 22

does your textbook use prime factorization ?

Answer 23

Nope. It uses a bunch of divisibility nonsense. To prove \(gcd(a,b)\times\text{lcm}(a,b)=ab\) the book uses the variables a,b,d,m,n,S,k,q. How am I suppose to remember all these variables in the proof?

Answer 24

It is a good idea to try to prove it on your own w/o looking at textbook

Answer 25

I read through the proof in the textbook quite a few (>=7) and still have a hard time memorising it. The proof involves to many letters and I still couldn't grasp it intuitively.

Answer 26

I don't like prime factorization in proofs like these but for this particular proof, using prime factorization is simple..

Answer 27

Consider prime factorization of \(a\) and \(b\) :

\[\large a = p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}\]
\[\large b = p_1^{b_1}p_2^{b_2}\cdots p_r^{b_r}\]

Answer 28

do you know how to represent gcd(a,b) and lcm(a,b) using above prime factorization ?

Answer 29

\[\gcd(a,b)=p_1^{\min\{a_1,b_1\}}p_2^{\min\{a_2,b_2\}}\cdots p_r^{\min\{a_r,b_r\}}\\
\text{lcm}(a,b)=p_1^{\max\{a_1,b_1\}}p_2^{\max\{a_2,b_2\}}\cdots p_r^{\max\{a_r,b_r\}}\]
We were taught this way in primary schools.

Answer 30

Yes that still works

Answer 31

multiply them and show that they equal \(ab\)

Answer 32

thats a legit proof

Answer 33

\[
\gcd(a,b)\times\text{lcm}(a,b)=p_1^{\min\{a_1,b_1\}+max\{a_1,b_1\}}p_2^{\min\{a_2,b_2\}+max\{a_2,b_2\}}\cdots p_r^{\min\{a_r,b_r\}+max\{a_r,b_r\}}\\
=p_1^{a_1+b_1}p_2^{a_2+b_2}\cdots p_n^{a_n+b_n}
\]

Answer 34

Looks perfect! as you can see the bad part is that we won't learn anything about divisibility properties

Answer 35

the moment you see \(\gcd(a,b)\), one way to start a proof is by letting \(d = \gcd(a,b)\) so that we have \(a = dr\) and \(b = ds\) for some integers \(r\) and \(s\).

Answer 36

How do you deal with the LCM though?

Answer 37

use the definition :

\(\text{lcm}(a,b)\) is the positive integer \(m\) satisfying
1) \(a|m\) and \(b|m\)
2) If \(a|c\) and \(b|c\), then \(m \le c\).

Answer 38

first part tells us that the lcm(a,b) is divisible by both \(a\) and \(b\)

Answer 39

second part tells us that lcm(a,b)is the least such positive integer