# Equation using modular inverse

In the search for the private key of a Merkle–Hellman knapsack cryptosystem. I have encountered the following relationship: $$b=a^{-1}\pmod m$$ I have found $b=2017$ and $m=65535$ and the modular inverse equation can be written as: $$2017=a^{-1}\pmod {65535}$$ I want to find $a$, but came only with a brute force solution and I have troubles understanding this type of equation.

Use the extended Euclidean algorithm to find integers $a$ and $b$ such that $$2017a + 65535b = 1 .$$
Then $2017$ is the inverse of $a$.
$$\gcd( 65535, 2017 ) = ???$$
$$\frac{ 65535 }{ 2017 } = 32 + \frac{ 991 }{ 2017 }$$ $$\frac{ 2017 }{ 991 } = 2 + \frac{ 35 }{ 991 }$$ $$\frac{ 991 }{ 35 } = 28 + \frac{ 11 }{ 35 }$$ $$\frac{ 35 }{ 11 } = 3 + \frac{ 2 }{ 11 }$$ $$\frac{ 11 }{ 2 } = 5 + \frac{ 1 }{ 2 }$$ $$\frac{ 2 }{ 1 } = 2 + \frac{ 0 }{ 1 }$$ Simple continued fraction tableau:
$$\begin{array}{cccccccccccccc} & & 32 & & 2 & & 28 & & 3 & & 5 & & 2 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 32 }{ 1 } & & \frac{ 65 }{ 2 } & & \frac{ 1852 }{ 57 } & & \frac{ 5621 }{ 173 } & & \frac{ 29957 }{ 922 } & & \frac{ 65535 }{ 2017 } \end{array}$$  $$\begin{array}{ccc} \frac{ 1 }{ 0 } & \mbox{digit} & 32 \\ \frac{ 32 }{ 1 } & \mbox{digit} & 2 \\ \frac{ 65 }{ 2 } & \mbox{digit} & 28 \\ \frac{ 1852 }{ 57 } & \mbox{digit} & 3 \\ \frac{ 5621 }{ 173 } & \mbox{digit} & 5 \\ \frac{ 29957 }{ 922 } & \mbox{digit} & 2 \\ \frac{ 65535 }{ 2017 } & \mbox{digit} & 0 \\ \end{array}$$
So, you see, by the main property of continued fraction convergents, which is that the little 2 by 2 determinants of consecutive convergents are $\pm 1,$ such as $32 \cdot 2 - 65 \cdot 1 = -1,$ or $65 \cdot 57 - 1852 \cdot 2 = 1,$ at the end
$$65535 \cdot 922 - 2017 \cdot 29957 = 1.$$ Or, $$65535 \cdot 922 + 2017 \cdot (-29957) = 1.$$ If preferred, we can carefully adjust the 922 by -2017, adjust the -29957 by +65535, for $$65535 \cdot (-1095) + 2017 \cdot 35578 = 1.$$