Throne
$ S + Kx \equiv 0 \pmod{N} \Leftrightarrow Kx \equiv -S \pmod{N}(★) を満たす整数$ xを求める
→ 最小値は [0, N) に丸めた値 ((x % N) + N) % N
(1)$ Kと$ Nが互いに素、つまり$ \gcd(K, N) = 1のときは拡張ユークリッドの互除法から分かる
【説明】
$ Ku + Nv = 1 = \gcd(K, N)には整数解$ (u, v)が存在する & 拡張ユークリッドの互除法で求められる
$ Nで割った余りを考えると$ Ku \equiv 1 \pmod{N}だから
上で求めた$ uは$ Kの ($ Nを法とする) 掛け算 における逆元$ K^{-1}
(★)$ Kx \equiv -Sの両辺にかけて$ x \equiv K^{-1} \times (-S)
(2)$ \gcd(K, N) = g > 1のときは (1) に帰着させる
(★) が解を持つには$ gが$ Sを割ることが必要
∵$ Kx \equiv -S \pmod{N}を満たす解$ xがあったとする
→ 合同式の定義から$ \exists y, \ Kx + S = Nyなので$ K=gK', N=gN'とすると$ S = g(N'y - K'x)
つまり (対偶を考えて) S % g != 0 ならば (★) が解を持たないので -1 を出力して終了
あとは$ K, N, Sをそれぞれ$ K/g, N/g, S/gに置き換えれば (1) と同じ議論が使える ($ K/g, N/gは互いに素なので)
これらを$ K', N', S'とする
$ K'x' \equiv -S' \pmod{N'}の解$ x'は (★) の解にもなっていることを確認
$ K'x' + S' = N'yと等式にして両辺$ gをかけると$ Kx' + S = Nyより$ Kx' \equiv -S \pmod{N}