2
$\begingroup$

I'll describe the problem with an example.

Find integers $n$ and $m$ such that $n\cdot13 + m\cdot101 = 1$.

This is the same as solving the equation $n\cdot13 \equiv 1 \pmod {101}$

I'm revising for a maths exam in a few days and it seems like a lot of the questions and examples rely on an ability to solve this type of problem. I can't seem to find a method in my notes, the solutions just get plucked out of thin air!

What is a neat way of doing it on pen and paper with a calculator?

  • 7
    Run Euclid's algorithm. Then reverse it. See here: http://en.wikipedia.org/wiki/Euclidean_algorithm#B.C3.A9zout.27s_identity2012-05-22
  • 3
    In fact, with careful bookkeeping you can keep track of things as you go and not need to run in reverse; this is widely known as the _Extended Euclidean algorithm_ and there are a ton of references for it out on the web (e.g., http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm ).2012-05-22

3 Answers 3