1
$\begingroup$

With p being a prime number, what is the remainder of $$\sum_{k=1}^{p-1} {k^{p-1}}$$ divided by p ?

I know that Fermat's little theorem states that for a prime number p, and a number A that is not divisible by p: $${A^{p-1}}≡ 1\mod p $$

So I'm thinking that the remainder would be 1, what am I missing here?

Any guidance, clues or solutions are much appreciated, thanks!

$\endgroup$
  • 1
    $\begingroup$ Shouldn't the remainder be $-1$? $\endgroup$ – Mostafa Ayaz Aug 25 '19 at 19:06
  • $\begingroup$ Welcome to Mathematics Stack Exchange. You have to sum $1$, $p-1$ times $\endgroup$ – J. W. Tanner Aug 25 '19 at 19:27
  • $\begingroup$ Inves I edited Mike's complete answer just in case you missed that the sum which is $p-1 \equiv -1 (mod p)$, so the remainder you're looking for is $-1$. $\endgroup$ – jacopoburelli Aug 25 '19 at 19:30
1
$\begingroup$

So I'm thinking that the remainder would be 1, what am I missing here?

What you are missing, is the basic rule of $$\underset{p-1 \text{ times}}{\underbrace{1+1+\cdots+1+1}}=p-1$$ still working in modular arithmetic. It simply wraps if it gets too big, which this sum isn't.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thank you, that explains the sum. but how would one solve for the sum p-1 divided by p? would the remainder then be p-1 aswell, since p-1 < p ? $\endgroup$ – Inves Aug 26 '19 at 12:05
  • $\begingroup$ that is correct. $\endgroup$ – user645636 Aug 26 '19 at 12:05
1
$\begingroup$

The logic seems fine, but I don't think your conclusion follows from it. From what you've shown, $$\sum_{k=1}^{p-1}k^{p-1}\equiv\sum_{k=1}^{p-1}1 = p-1 \equiv -1\pmod p$$

I'm pretty sure you don't get $1$ from simplifying that.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ only in the special case of $p=2$ $\endgroup$ – user645636 Aug 25 '19 at 23:28
  • $\begingroup$ -1 is an alternative version of $p-1$ in modular arithmetic. We say they are congruent, or in the same modular congruence class as each other. this happens because their difference is a multiple of $p$ $\endgroup$ – user645636 Aug 26 '19 at 12:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.