Speed up divisors' calculation by hand

Question

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:

1. loof for a certain interval such that $13 \cdot x < 10^4+m < 13 \cdot y$

2. notice that $13 \cdot 700 < 10^4+m < 13 \cdot 800$

3. 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.

Answer 1

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

Answer 2

$\!\bmod 13\!:\ m\!+\!10^4\equiv 0\iff m \equiv -10^4\equiv -(-3)^4\equiv -(-4)^2\equiv -3\equiv 10$

Alternatively $\ 13\mid 1001\,\Rightarrow\ 13\mid 10(1001) = 10^4 + 10$