\(O(\log N)\) @4tsuzuru https://zenn.dev/link/comments/29d659a57ead56

exgcd a b returns (g, na, nb) where \(g = a \cdot n_a + b \cdot n_b\).

>>> exgcd 3 5
(1,2,-1)
>>> 1 == 3 * 2 + 5 * (-1)
True

Note that \(n_{a} = a^{-1} \mod b\): \[ \begin{aligned} n_a a + n_b b &= 1 \\ \Rightarrow n_a a &\equiv 1 \mod b \\ \Leftrightarrow n_a &\equiv a^{-1} \mod b \end{aligned} \]

\(O(\log N)\) Example for showing how to use exgcd to calculate the modular multicative inverse.