# Maximum number if the GCD is known

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?

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$$

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$$