Equation using modular inverse

Question

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.

Answer 1

Use the extended Euclidean algorithm to find integers $a$ and $b$ such that $$ 2017a + 65535b = 1 . $$

Then $2017$ is the inverse of $a$.

Answer 2

$$ \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. $$