I was reading number theory book by John Stillwell and I am stuck somewhere.

The symbolic Euclidean algorithm is used when solving linear Diophantine equations. Suppose that we run the ordinary Euclidean algorithm on the numbers $b$ and $-a$ until $1$ and $-1$ are produced, and suppose that the corresponding vector pair is $((m_1 , n_1 ), (m_2 ,n_2))$.

It claims that $(x,y) = (m_1,n_1)$ is the least positive solution of $bx-ay= 1$ and that $(x,y)= (m_2,n_2)$ is the least positive solution of $bx-ay=-1$.

It certainly looks like that but I got no clue to solve it. enter image description here enter image description here

  • $\begingroup$ Not everyone has Stillwell's book, and not everyone uses Stillwell's notation. It will be hard to answer your question without knowing what you mean by running the algorithm until 1 and $-1$ are produced, and wothout knowing what your $m_i$ and $n_i$ are supposed to mean. Anyway, you might try searching this site for previous question about Euclid's algorithm. There have been many, and one may hold an answer to your question. $\endgroup$ – Gerry Myerson Sep 26 '18 at 7:03
  • 1
    $\begingroup$ @GerryMyerson now check.. I've attached two screenshots $\endgroup$ – ChakSayantan Sep 26 '18 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.