Question

Prove that (a+b, a-b) ≥ (a,b) for any two integers.​

Answer 1

Answer:

answer

Step-by-step explanation:

Proof:

Without loss of generality, we can assume that a and b are both positive with a≥b>0

Since GCD can be written as linear combination of the two integers,

(a,b)=ax+by

We know that (a,b)≤b≤a Which implies that either x or y is is negative.

We can assume that y is negative. This implies bx−ay≥0. (Conversely if x is negative then ay−bx≥0 )

Now,

ax+by=(a,b)

⇒ax+by+bx−ay≥(a,b)

⇒(a+b)x+(b−a)y≥(a,b)

⇒(a+b)x+(−y)(a−b)≥(a,b)

⇒(a+b,a−b)≥(a,b)

QED.