Maximum number if the GCD is known

Question

if it is known that the GCD(a,2008) = 251, and a<4036 whats the biggest number for a?

a. 3263

b. 4016

c. 2259

d. 3765

e. 3514

i know that the answer is d, after a long math. but does anybody have any other ways to do it?

Answer 1

Since $2008 = 8 \times 251$ you are looking for a multiple of $251$ which has no factor (other than $1$) in common with $8$ - so it can't be even. [$251$ has to be a factor of $2008$ for the question to make sense]

You are therefore looking for the highest odd multiple of $251$ less than $4036$.

Well $4016=251 \times 16$ (twice what you started with, so nice and easy to work with) so you are looking for $251\times 15$

Answer 2

Well, you know it is a multiple of $251$.

$4036 = 16*251+20$ so $a$ is at most $256*16$.

So $a = 251*b$ where $b \le 16$.

$2008 = 8*251$. So $b$ and $8$ can not have any factors in common so $b \ne 16$. (Note: $\gcd(2008, 251*16) = 2008$)

If $b=15$ then $b$ and $8$ don't have any factors in common. ANd if we test it: $\gcd(15*251, 2008)= \gcd(15*251, 8*251) = 251$.

So that's it. $a = 15*251 = 3765$