# Thread: GCD Proof

1. ## GCD Proof

My professor proposed a question in class awhile ago and told us to prove it for homework. When he proved it in class the day it was due, he gave a very long and unnecessary proof. My proof was significantly shorter and when I asked my professor if my proof was correct he told me to go away, so, since I have such a helping professor, I have to know if this proof is correct so that I can study for the exam later on using the right information. Here's the statement:

If $\displaystyle a,b > 0$, then $\displaystyle (a,b) = (a + b, [a,b])$

Where (,) is the gcd and [,] is the lcm.

Proof:

Suppose there are two integers s and t s.t.

$\displaystyle p^s || a$ and $\displaystyle p^t || b$

This implies that:

$\displaystyle a = mp^s$

$\displaystyle b = np^t$

Where $\displaystyle p \not | mn$

Without loss of generality, assume $\displaystyle s \leq t$,

$\displaystyle a + b = mp^s + np^t$
$\displaystyle = p^s(m + np^{t -s})$

This implies that $\displaystyle p^s || (a + b)$

We know that $\displaystyle p^{max(s,t)} || [a,b]$ since $\displaystyle p^{max(s,t)}$ is the lcm by definition, and that $\displaystyle max(s,t) = t$

This implies that $\displaystyle p^t || [a,b]$

Therefore

$\displaystyle p^{min(s,t)} || (a + b, [a,b])$, where $\displaystyle p^s || a + b$ and $\displaystyle p^t || [a,b]$

and $\displaystyle p^{min(s,t)} || (a,b)$ by definition. Since they both are exactly divisible by the same power of p, they must be equal.

Thanks for the help.

2. I’m not sure what you are doing in your proof myself – but I have a proof which is even shorter than yours. Use the following result:

If $\displaystyle \gcd(m,n)=1,$ then $\displaystyle \gcd(m+n,mn)=1.$

It’s not difficult to prove it. You might like to try it as an exercise.

So, to the question you are asking.

Let $\displaystyle \gcd(a,b)=d,\ a=a'd,\ b=b'd.$

Then $\displaystyle a+b=(a'+b')d,\ \mathrm{lcm}(a,b)=\frac{ab}d=a'b'd$; also $\displaystyle \gcd(a',\,b')=1.$

$\displaystyle \therefore\ \gcd(a+b,\,\mathrm{lcm}(a,b))$

$\displaystyle =\ \gcd\left((a'+b')d,\,a'b'd\right)$

$\displaystyle =\ d\cdot\gcd(a'+b',a'b')$

$\displaystyle =\ d$

$\displaystyle =\ \gcd(a,\,b)$

3. I did forget two things:

1. p is prime

2. If $\displaystyle p^q | a$ and $\displaystyle p^{q+1} \not | a$, then $\displaystyle p^q$ divides a exactly, denoted $\displaystyle p^q || a$.

We were supposed to prove it using prime numbers. The proof you provided was the one we all wished we could use.