math - 证明 - 一个素数 p 乘以另一个互素数的余数集

Question

我已经解决了 usaco 上的问题掘金。我到了需要证明这一点的地步：

如果我们有一个S包含数字的集合，(0,1,2,3,...P-1)其中P是质数。如果我们将这个集合相乘，* X [where X and P are co-primes (relative primes)]我们将得到相同的集合S，也许有不同的排列，但我们会得到相同的元素。乘法后，我们将取mod P集合中的每个元素。

这是任何定理，还是可以证明与此有关？

Answer 1

假设，有i和j其中(0,1,2,3,...P-1)产生相同的值lambda a: (a*x)%p。

然后

i*x = j*x mod p
=> i*x - j*x = 0 mod p
=> (i - j)*x = 0 mod p

如此p划分(i-j)*x。现在p和x互质，所以p不除x。所以p | i - j

现在注意，i两者j都小于p。所以i - j也小于p。所以p不能除i - j，除非，它是zero。所以i - j = 0 => i = j。

因此，如果i和j产生相同，i = j。所以当i != j,i和j产生不同的整数。所以对于每个iin (0,1,2,3,...P-1)，lambda a: (a*x)%p产生不同的整数。所以如果你在一个集合中收集整数，这个集合必须有p元素。但所有整数都必须小于p。因此该集合包含来自 的每个元素(0,1,2,...P-1)。

---

备注：p不一定需要是素数。一切都需要，p并x成为共同的。