何名かの方が最大公約数を求めるプログラムを作っていたので、その応用問題です。受験数学とかで見たことあるのでは？
整数 a, b に対して、以下を満たす整数 x, y を求めよ。
ax + by = gcd(a,b)
ベズーの等式(Bézout's identity)、というようです。
でも identity 恒等式でなく equation 方程式なんだけど……解は無限にあるので、1組の $(x,y)$ を求めればよいです
びっくりするくらい簡単なので、せめて５分間だけでもアタマをひねってみてください