这是一个创建于 1826 天前的主题，其中的信息可能已经有所发展或是发生改变。
假如一个质数 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.
我觉得是正确的，就是不知道怎么证明
比如：0,7,14,21,28 对 5 取模，0,2,4,1,3.
我觉得是正确的，就是不知道怎么证明
 |
1
Raven316 OP 顶下。。。
|
 |
2
lvybupt 2019-10-31 20:28:35 +08:00  1
对的。 简单证明一下， 如果 不是 n-1 个不同数，有 a，b 相同。那么有 ap - bp = qn。st. (a-b)p = qn 显然 a-b<n，若 a-b/=0 那么 n 的分解中，含有 p 的因子，与 p 是素数矛盾。
|
|
3
lvybupt 2019-10-31 20:29:30 +08:00
随便打的，文字不严谨，意思自己参考一下哈。
|
|
4
Raven316 OP 若 a-b/=0 那么 n 的分解中，含有 p 的因子，与 p 是素数矛盾。
这一点还是没明白 |
|
5
lvybupt 2019-10-31 20:36:14 +08:00
p = q n /（ a-b ）与 p 是素数矛盾。这次呢？
|
 |
6
PonysDad 2019-10-31 20:40:28 +08:00
线性同余问题
|
|
7
PonysDad 2019-10-31 20:42:29 +08:00
列个线性同余方程就解就可以了
|
 |
8
msg7086 2019-11-01 04:54:17 +08:00
反证法。
任取 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，也就不可能重复。 （瞎打的，不太严谨，但是过程应该没错。） |
Select Language