假如一个质数 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.
我觉得是正确的，就是不知道怎么证明
This topic created in 2422 days ago, the information mentioned may be changed or developed.
 |
1
Raven316 OP 顶下。。。
|
 |
2
lvybupt Oct 31, 2019  1
对的。 简单证明一下， 如果 不是 n-1 个不同数，有 a，b 相同。那么有 ap - bp = qn。st. (a-b)p = qn 显然 a-b<n，若 a-b/=0 那么 n 的分解中，含有 p 的因子，与 p 是素数矛盾。
|
|
3
lvybupt Oct 31, 2019
随便打的，文字不严谨，意思自己参考一下哈。
|
|
4
Raven316 OP 若 a-b/=0 那么 n 的分解中，含有 p 的因子，与 p 是素数矛盾。
这一点还是没明白 |
|
5
lvybupt Oct 31, 2019
p = q n /（ a-b ）与 p 是素数矛盾。这次呢？
|
 |
6
PonysDad Oct 31, 2019
线性同余问题
|
|
7
PonysDad Oct 31, 2019
列个线性同余方程就解就可以了
|
 |
8
msg7086 Nov 1, 2019
反证法。
任取 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