math - 2つの整数の最大の合同係数を見つけますか？

Question

2つの整数が与えられた場合、それらの最大の合同係数を見つける簡単な方法はありますか？つまり、a％n == b％n、またはそれらすべてを列挙することさえできますか？明らかに、私はそれらよりも小さいすべての値を試すことができましたが、もっと簡単な方法があるはずです。

私はgcdsで何かをしようとしましたが、％n == b％n == 0であることがわかります。これは、私が望んでいたほどクールではありません。これは必ずしも最大のn。

何か案は？

Answer 1

a と b が数値の場合、次のように考えます。

a = nx + r
b = ny + r

ここで、n は求めたいモジュラス、r は共通剰余です。そう、

a - b = n(x - y)

最大 n は x - y = 1 で達成されます。したがって、

n = a - b

（私が質問を正しく理解していれば。）