一个质数相关的问题

[Raven316]

假如一个质数 p，一个整数 n 小于 p，那么 0,1,2,3,...,n-1 分别乘以 p 对 n 取模，是不是还是得到 0,1,2,3,..,n-1，只是顺序不同了。

比如：0,7,14,21,28 对 5 取模，0,2,4,1,3.

我觉得是正确的，就是不知道怎么证明

[Raven316]

顶下。。。

[lvybupt]

对的。 简单证明一下， 如果 不是 n-1 个不同数，有 a，b 相同。那么有 ap - bp = qn。st. (a-b)p = qn 显然 a-b<n，若 a-b/=0 那么 n 的分解中，含有 p 的因子，与 p 是素数矛盾。

[lvybupt]

随便打的，文字不严谨，意思自己参考一下哈。

[Raven316]

若 a-b/=0 那么 n 的分解中，含有 p 的因子，与 p 是素数矛盾。

这一点还是没明白

[lvybupt]

p = q n /（ a-b ）与 p 是素数矛盾。这次呢？

[PonysDad]

线性同余问题

[PonysDad]

列个线性同余方程就解就可以了

[msg7086]

反证法。
任取 a 和 b，令 Ya = a * p mod n ； Yb = b * p mod n ；假设 a < b && Ya = Yb。

因为 p 和 n 没有公因数，所以
Ya = a * p mod n
= (a * p + x * n) mod n （ x 是整数）

因为 Ya = Yb，所以有
a * p + x * n = b * p
x = (b - a) / p

因为 x 是整数，所以 b - a 是 p 的倍数，因为 a < b 所以 b >= a + p。所以若 a、b 取值小于 p，就不可能得到 Ya = Yb，也就不可能重复。

（瞎打的，不太严谨，但是过程应该没错。）