0
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ Thank you so much! $\endgroup$ – Phi_24 Jan 23 at 17:25
1
$\begingroup$

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

$\endgroup$

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.