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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.