Maths Olympiad Prep

Library / /303 of 520

Number theory Difficulty 6.2 National olympiad Prove it

5. Let pp be a prime, k⩾1k \geqslant 1. Prove
1k+2k+⋯+(p−1)k≡{0( mod p),p−1∤k−1( mod p),p−1∣k1^{k}+2^{k}+\cdots+(p-1)^{k} \equiv\left\{\begin{array}{ll} 0(\bmod p), & p-1 \nmid k \\ -1(\bmod p), & p-1 \mid k \end{array}\right.

Solution

5. Let gg be a primitive root modulo pp. 1k+⋯+(p−1)k≡∑j=1p−1gjk( mod p)1^{k}+\cdots+(p-1)^{k} \equiv \sum_{j=1}^{p-1} g^{j k}(\bmod p), and from this, along with gk≢1( mod p)g^{k} \not \equiv 1(\bmod p) when p−1∤kp-1 \nmid k; gk≡1( mod p)g^{k} \equiv 1(\bmod p) when p−1∣kp-1 \mid k, we can derive the desired conclusion.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.