math - 将一个模值转换为另一个

Question

给定 N = A%B，如何找到 A%C 的值，其中 B > 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 =模 3 = 1
• => a 在整数集合 {3x + 1}
• 所以考虑，x=1
  • 4 mod 3 = 1，这样就可以了
  • 4 模 2 = 0
• 现在考虑 x=2
  • 7 mod 3 = 1，所以我们只知道n和b就无法区分 4 和 7
  • 7 模 2 = 1

也就是说，给定b=3和n=1，您必须在不知道a 的情况下得到两个不同的答案。

但是，您可能会认为这里的b和c互质，实际上都是质数是一种特殊情况。在某些情况下，您当然可以轻松解决这个问题，例如b=4和c=2。

顺便说一句，对此的进一步讨论可能更适合mathoverflow