GCD of Sum and Difference

Number Theory Level 1

For any two coprime positive integers $a$ and $b$ , find the maximum value of $\gcd(a+b,a-b)$ .

Notation: $\gcd(\cdot)$ denotes the greatest common divisor function.

The answer is 2.

1 solution

Muhammad Rasel Parvej
Dec 13, 2016

$gcd(a+b,a-b)$

$=gcd(2a,a-b)$ [As $gcd(x,y)=gcd(x+y,y)$ ]

As $a$ and $b$ are coprime, $gcd(a,b)=1$ . That means, no factor of $a$ , other than $1$ , divides $(a-b)$ . So, $gcd(a+b,a-b)=gcd(2a,a-b)= gcd(2,a-b)$ . Hence, $gcd$ is either $1$ or $2$ .

Now $2$ divides $(a-b)$ when both $a$ and $b$ is odd.

So, the maximum possible value of $gcd(a+b, a-b)$ is $\boxed{2}$ .

$Nice solution$ :)

Prokash Shakkhar - 4 years, 6 months ago

GCD of Sum and Difference

The answer is 2.

1 solution

0 pending reports