分页： 1 / 1
中等难度题目
发表于 ： 2023年 1月 26日 16:24
由 （ヅ）
p>=3为质数，4个部分
p1(easy):证明1^p + 2^p +... + (p-1)^p = 0 mod p
p2(easy): k = p-1, 证明1^k + 2^k +... + (p-1)^k = p-1 mod p
p3(easy): k为奇数,证明1^k + 2^k +... + (p-1)^k = 0 mod p
p4(medium): 1 <= k <= p - 3, k为偶数,证明1^k + 2^k +... + (p-1)^k = 0 mod p
Re: 中等难度题目
发表于 ： 2023年 1月 26日 20:57
由 YWY
P4 is true for any integer k that is not a multiple of p-1. Note that, mod p, {1^k, 2^k, ..., (p-1)^k} is a subgroup of {1, 2, ..., (p-1)} under multiplication. Since p-1 does not divide k, the order/cardinality of the subgroup {1^k, 2^k, ..., (p-1)^k} is at least 2. Pick two distinct elements, say i^k and j^k, in {1^k, 2^k, ..., (p-1)^k}. Then, mod p,
i^k [1^k + 2^k +... + (p-1)^k] = j^k [1^k + 2^k +... + (p-1)^k], which implies
(i^k - j^k)[1^k + 2^k +... + (p-1)^k], which implies
1^k + 2^k +... + (p-1)^k = 0 (mod p).
Re: 中等难度题目
发表于 ： 2023年 1月 26日 23:28
由 （ヅ）
YWY 写了： 2023年 1月 26日 20:57
P4 is true for
any integer k that is not a multiple of p-1. Note that, mod p, {1^k, 2^k, ..., (p-1)^k} is a subgroup of {1, 2, ..., (p-1)} under multiplication. Since p-1 does not divide k, the order/cardinality of the subgroup {1^k, 2^k, ..., (p-1)^k} is at least 2. Pick two
distinct elements, say i^k and j^k, in {1^k, 2^k, ..., (p-1)^k}. Then, mod p,
i^k [1^k + 2^k +... + (p-1)^k] = j^k [1^k + 2^k +... + (p-1)^k], which implies
(i^k - j^k)[1^k + 2^k +... + (p-1)^k], which implies
1^k + 2^k +... + (p-1)^k = 0 (mod p).
有2个疑问
“Since p-1 does not divide k, the order/cardinality of the subgroup {1^k, 2^k, ..., (p-1)^k} is at least 2“
"i^k [1^k + 2^k +... + (p-1)^k] = j^k [1^k + 2^k +... + (p-1)^k]"
Re: 中等难度题目
发表于 ： 2023年 1月 27日 00:51
由 YWY
（ヅ） 写了： 2023年 1月 26日 23:28
有2个疑问
“Since p-1 does not divide k, the order/cardinality of the subgroup {1^k, 2^k, ..., (p-1)^k} is at least 2“
"i^k [1^k + 2^k +... + (p-1)^k] = j^k [1^k + 2^k +... + (p-1)^k]"
Let x be a primitive root mod p. Then x^k is not 1 mod p, as p-1 does not divide k. Thus 1^k and x^k are distinct.
We have i^k [1^k + 2^k +... + (p-1)^k] = i^k + (2i)^k + ... + ((p-1)i)^k = 1^k + 2^k +... + (p-1)^k, since the set {i, 2i, ..., (p-1)i} is the same set as {1, 2, ..., p-1} mod p. So i^k [1^k + 2^k +... + (p-1)^k] = j^k [1^k + 2^k +... + (p-1)^k].
Re: 中等难度题目
发表于 ： 2023年 1月 27日 01:06
由 （ヅ）
YWY 写了： 2023年 1月 27日 00:51
Let x be a primitive root mod p. Then x^k is not 1 mod p, as p-1 does not divide k. Thus 1^k and x^k are distinct.
We have i^k [1^k + 2^k +... + (p-1)^k] = i^k + (2i)^k + ... + ((p-1)i)^k = 1^k + 2^k +... + (p-1)^k, since the set {i, 2i, ..., (p-1)i} is the same set as {1, 2, ..., p-1} mod p. So i^k [1^k + 2^k +... + (p-1)^k] = j^k [1^k + 2^k +... + (p-1)^k].
分析的很好
我想的是,因为p是质数，所以Z_p^*里面有primitive root mod p，记为g, g != 1
那么，{g, g^2, ..., g^{p-2}, g^{p-1}=1} = Z_p^* = {1, 2, ..., p-1}
那么可以把1^k + 2^k +.. +(p-1)^k写成
1^k + g^k + g^{2k} + ... + g^{(p-2)k}
考虑 (g^k - 1) (1^k + g^k + g^{2k} + ... + g^{(p-2)k}) = g^{(p-1)k} - 1 = 0 mod p
那么p | (g^k - 1) (1^k + g^k + g^{2k} + ... + g^{(p-2)k})
同时，因为 1 <= k < p -1, g^k != 1 mod p,所以 p 不能整除g^k - 1，同时p为质数，所以
p | 1^k + g^k + g^{2k} + ... + g^{(p-2)k}
Re: 中等难度题目
发表于 ： 2023年 1月 27日 01:24
由 YWY
（ヅ） 写了： 2023年 1月 27日 01:06
分析的很好
我想的是,因为p是质数，所以Z_p^*里面有primitive root mod p，记为g, g != 1
那么，{g, g^2, ..., g^{p-2}, g^{p-1}=1} = Z_p^* = {1, 2, ..., p-1}
那么可以把1^k + 2^k +.. +(p-1)^k写成
1^k + g^k + g^{2k} + ... + g^{(p-2)k}
考虑 (g^k - 1) (1^k + g^k + g^{2k} + ... + g^{(p-2)k}) = g^{(p-1)k} - 1 = 0 mod p
那么p | (g^k - 1) (1^k + g^k + g^{2k} + ... + g^{(p-2)k})
同时，因为 1 <= k < p -1, g^k != 1 mod p,所以 p 不能整除g^k - 1，同时p为质数，所以
p | 1^k + g^k + g^{2k} + ... + g^{(p-2)k}
赞！