Prove that $\sum^{n-1}_{i=1}i^{(n-1)} \equiv -1$ (mod $n$) for all prime $n\in\mathbb{N}$.

Question

Prove that $\sum^{n-1}_{i=1}i^{(n-1)} \equiv -1$ (mod $n$) for all prime $n\in\mathbb{N}$.

I'm having a difficult time proving this problem. I was able to verify that it works for prime $n$ up to 5000 using Python.

I'm assuming induction would be useful in this case? Would love some help with this problem!

Answer 1

It's an obvious case of Fermat's little theorem, or, as demons like me prefer to call it, Fermat's theorem. Whoever got to your question first would immediately know that's the answer.

If $p$ is prime and $a$ is coprime to $p$, then $a^{p - 1} \equiv 1 \pmod p$, Fermat's theorem tells us.

Then, with $$\sum_{i = 1}^{n - 1} i^{n - 1},$$ if $n$ is prime, we know that all $0 < i < n$ are coprime to $n$, and therefore each $i^{n - 1} \equiv 1 \pmod n$. And since there are $n - 1$ instances of $i$ that we loop through, we find that $$\sum_{i = 1}^{n - 1} i^{n - 1} \equiv n - 1 \pmod n,$$ and $n - 1$ is just another way to write $-1$ in this context.

Edit: Someone attempted to correct one of my mistakes and wondered whether it was intentional or unintentional. Well, let me reassure you, all my mistakes are intentional. For one silly reason, that guy's attempt to correct my mistake was shot down, so I have corrected the mistake myself.

Answer 2

Hint: by Fermat's little theorem, $i^{n-1}\equiv 1$ (mod $n$).

Answer 3

It's good that you can get Python to calculate up to 5000 for you, but sometimes what might really help you is to calculate two or three cases by hand to see if you can spot any patterns.

Let's try $n = 5$:

• $1^4 = 1 \equiv 1 \pmod 5$. Since $1^x = 1$ regardless of what $x$ is, we might as well go ahead and regard 1 as the taxi meter drop in this problem for all $n$.
• $2^4 = 16 \equiv 1 \pmod 5$.
• $3^4 = 81 \equiv 1 \pmod 5$.
• $4^4 = 256 \equiv 1 \pmod 5$.

These add up to 4, which is one less than 5.

Now let's try $n = 6$. I know, that's not prime, but it might still give us an insight.

• 1 is the taxi meter drop.
• $2^5 = 32 \equiv 2 \pmod 6$.
• $3^5 = 243 \equiv 3 \pmod 6$.
• $4^5 = 1024 \equiv 4 \pmod 6$.
• $5^5 = 3125 \equiv 5 \pmod 6$.

These add up to 21, which is $3 \pmod 6$. In some ways, 6 is a little unusual (don't expect $i^{n - 1} \equiv i \pmod n$ whenever $n$ is composite), but we can still learn from this that if $\gcd(i, n) > 1$, then $i^{n - 1} \equiv 1 \pmod n$ is impossible.

In fact, $i^{n - 1} \equiv d \pmod n$ where $d$ is either a nontrivial divisor of $n$ or 0 (which can be considered a divisor in the context of modular arithmetic). For example, for $n = 8$, if $i$ is even, then $i^7 \equiv 0 \pmod 8$. This is because $8 = 2^3$ and $i$ being even means that $i = 2j$. Then $i^7 = 2^7 j$, which is obviously a multiple of 8.

So, if $n$ is prime, then all $i$ from 1 to $n - 1$ are coprime to $n$, which means that it's possible that $i^{n - 1} \equiv 1 \pmod n$ for each $i$. In fact, each $i$ does give $i^{n - 1} \equiv 1 \pmod n$, a fact that Pierre de Fermat noticed.

I don't know if Fermat himself proved this "little theorem," but plenty of other people have, and the proof is easy enough to follow, though I won't repeat it here. Nor will I repeat the Short One's answer, which will now be hopefully easier to understand.

There's only one thing left to address, and that's induction. Many things can be proven with induction, even when it's not the best method of proof. For this particular problem, I think the best method is simply to apply Fermat's little theorem and just let everything fall into place.