中等难度题目

[（ヅ）]

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

[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).

[（ヅ）]

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]"

[YWY]

有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].

[（ヅ）]

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}

[YWY]

分析的很好

我想的是,因为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}

赞！