How do I solve this equation over integers: $1=91p+74q$ Like in title. I need to solve this equation: $$1=91p+74q$$ with $p, q$ being integers. I brute forced the solution to be $(p,q)=(-13,16)$, but I'd love to know how to solve it without just mashing keys on the calculator, hoping for the best.
 A: Use the extended Euclidean algorithm.
$91=1\cdot74+17$
$74=4\cdot17+6$
$17=2\cdot6+5$
$6=1\cdot5+1$.
Therefore,
$1=6-1\cdot5=6-1(17-2\cdot6)=3\cdot6-17=3(74-4\cdot17)-17=3\cdot74-13\cdot17$
$=3\cdot74-13(91-74)=16\cdot74-13\cdot91$.
A: Use the forward version of the Extended Euclidean Algorithm:
$$\begin{array}{ccl} & 91 & 74\\
--- & --- & --- & ----\\
 91 & 1 & 0 & (1) \\
74 & 0 & 1 & (2) \\ 
17 & 1 &  -1 & (3) = (1)-(2)\\
6 & -4 & 5 & (4) = (2)-4\times(3)\\
-1 & 13 & - 16 & (5) = (3)-3\times(4) \end{array}$$
Therefore $-1 = 13(91)-16(74) \implies 1=(-13)\times 91+16\times (74)$
Note: when I did regular EEA it's very easy to make calculation mistake because of its backward substitution nature. With this forward method it almost never happened. And when it does, you can track each line easily to find where you made a mistake. For example,
Line $(1): 91 = 1\times 91 + 0 \times 74$
Line $(4): 6 = -4 \times 91 + 5 \times 74$
etc.
A: I see that others have mentioned the Euclidean Algorithm. That would surely work. I would like nominate an approach I constantly use.
So we first look at $91$ and $74$. They are coprime, which means that such $p,q$ exist. What we want to do is to write $1$ as a linear combination of $91$ and $74$ with integer coefficients. We have $91-74=17$, so $17$ can be written as a linear combination of $91$ and $74$ with integer coefficients (which are $1$ and $-1$). Next we want to find a even smaller number that can also be written as a linear combination. We have $91-5\cdot 17=6$. Now we have $91-15\cdot 6=1$, i.e.,
$$1=91-15\cdot 6=91-15\cdot(91-5\cdot 17)=91-15\cdot(91-5\cdot(91-74))\\=91-15\cdot(5\cdot 74-4\cdot 91)=61\cdot 91-75\cdot 74$$
A: I am going to tell you a very beautiful approach to solve these types of problems note that general solution is x=-13+74t  and y=16-91t where t is a nonnegative integer now I tell you how I get that I assume that you know a little bit about continued fractions since I will apply it here now just  write  91/74 as a continued fraction now look at the second last convergent say p(n-1) /q(n-1) now use cassini identity which says that p(n) q(n-1) -q(n) p(n-1) =${-1}^n$ by using this I got general solution I hope it helps
