# Proof involving GCD of numbers

• Apr 10th 2008, 03:05 AM
p vs np
Proof involving GCD of numbers
I would like to know of the line of approach one needs to take in the following (and similar problems involving elementary concepts of GCD of numbers)problem.

The problem is-

For any 2 integers a,b, prove that the (a+b,a-b)>=(a,b)
where (x,y) represents the GCD of the numbers x,y.
• Apr 10th 2008, 04:49 AM
CaptainBlack
Quote:

Originally Posted by p vs np
I would like to know of the line of approach one needs to take in the following (and similar problems involving elementary concepts of GCD of numbers)problem.

The problem is-

For any 2 integers a,b, prove that the (a+b,a-b)>=(a,b)
where (x,y) represents the GCD of the numbers x,y.

Any common divisor of a and b is a divisor of a+b and a-b, hence the greatest
common divisor of a and b is a divisor of both a+b and a-b, and so less than
or equal to the gcd of a+b and a-b.

RonL
• Apr 15th 2008, 09:42 PM
p vs np
Quote:

Originally Posted by CaptainBlack
Any common divisor of a and b is a divisor of a+b and a-b, hence the greatest
common divisor of a and b is a divisor of both a+b and a-b, and so less than
or equal to the gcd of a+b and a-b.

RonL

My apologies for the late response.
Can you prove the statement "Any common divisor of a and b is a divisor of a+b and a-b", because at face value, it seems to be quite logical.
But is there a mathematical treatment this statement can be given?
• Apr 15th 2008, 11:07 PM
CaptainBlack
Quote:

Originally Posted by p vs np
My apologies for the late response.
Can you prove the statement "Any common divisor of a and b is a divisor of a+b and a-b", because at face value, it seems to be quite logical.
But is there a mathematical treatment this statement can be given?

$\displaystyle c \in \mathbb{Z}$ is a common divisor of $\displaystyle a \in \mathbb{Z}$ and $\displaystyle b \in \mathbb{Z}$ if (and only if) there exists $\displaystyle u$ and $\displaystyle v$ in $\displaystyle \mathbb{Z}$ such that:

$\displaystyle a=uc,\ b=vc$

Now:

$\displaystyle a+b=uc+vc=(u+v)c$

but $\displaystyle (u+v) \in \mathbb{Z}$, so $\displaystyle c$ is a divisor of $\displaystyle (a+b)$.

Same type of argument for $\displaystyle (a-b)$ applies.

RonL
• Apr 17th 2008, 03:35 AM
p vs np
Oh...after the solution has been provided, it looks rather elementary(as in every case).
Thanks for the solution.