Q:

Speed up divisors' calculation by hand

An exercise such the following one has to be solved by hand during an exam. So, knowing that I need to solve it in about ten minutes, I would like to know if there is a rapid technique to do it.

Find the minimum $m$ such that $\gcd(533,299)$ divides $10^4+m$.

I found $\gcd(533,299)=13$ with the Euclidean algorithm and then the unique method I see to determine $m$ is:

loof for a certain interval such that $13 \cdot x < 10^4+m < 13 \cdot y$
notice that $13 \cdot 700 < 10^4+m < 13 \cdot 800$
try by hand with $x>700$ and $y<800$

but I need a lot of time to do these calculations.
Do you know some tricks that would help the solution?
Thanks a lot in advance.

A:

Find the remainder when $10^4$ is divided by 13. Long division gives $10^4=769\cdot 13+3$. Thus the smallest number larger than $10^4$ which is divisible by $13$ is $$769\cdot 13+13=(769\cdot 13+3)+10=10^4+10.$$

