math - モジュラス値を別のモジュラス値に変換する

Question

N = A%B が与えられた場合、B > C である A%C の値を見つける方法。N と C の値が与えられますが、A の値は与えられません。

これを見つける方法はありますか？

Answer 1

いいえ。次の点を考慮してください。

A = 19
B = 10
C = 7
==> Given 9, you should get 5.

A = 29
B = 10
C = 7
==> Given 9, you should get 1.

したがって、同じ入力が与えられた場合、複数の答えが存在する可能性があります。

Answer 2

モジュロ演算は一方向です: a mod b = nが与えられた場合、私が言えることは、aは、モジュロbがnに等しい他のすべての整数のセットに由来するということだけです。

B=3、C=2 を取って、これが一般的に不可能であることを示しましょう。

• n = a mod 3 = 1
• => a は整数の集合 {3x + 1} にあります
• x=1
  • 4 mod 3 = 1なので、うまくいきます
  • 4 mod 2 = 0
• ここで x=2 を考えます
  • 7 mod 3 = 1 なので、 nとbだけでは 4 と 7 を区別できません。
  • 7 mod 2 = 1

つまり、b=3とn=1が与えられた場合、 aを知らなくても2 つの異なる答えを得る必要があります。

ただし、ここでbとcが互いに素であり、実際にはどちらも素であるというのは特殊なケースだと考えるかもしれません。b=4やc=2などのいくつかのケースでは、これを簡単に解決できます。

ところで、これに関するさらなる議論はおそらくmathoverflowに適しています