# 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:

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.

• You just want to compute $10^4\pmod {13}$ (it's easy from there). – lulu Jan 23 at 17:12

## 2 Answers

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

• Thank you so much! – Phi_24 Jan 23 at 17:25

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