# (x,y) = (m_1,n_1) is the least positive solution of bx-ay= 1 while performing euclidean algorithm

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.

• 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. – Gerry Myerson Sep 26 '18 at 7:03
• @GerryMyerson now check.. I've attached two screenshots – ChakSayantan Sep 26 '18 at 7:10