Let $p$ be a prime. Prove that $\displaystyle\sum_{i=0}^{p}\binom pix^i \equiv x + 1 \pmod p$.

i got

\begin{align} & \frac{p!}{i!(p-i)!}(x^0+x^1+x^2+x^3+x^4+\cdots+x^p) \\[4pt] = {} & 1\cdot (x^0 + x^1 + x^2 + x^3 + x^4 +\cdots+x^p) \end{align}

so does $(x^0+x^1+x^2+x^3+x^4+\cdots+x^p) = x + 1 \pmod p$?! am i on the right track here?

  • $\begingroup$ First check whether the sum is right. Do you mean $(a/p)$ or do you mean $(i/p)$? This looks like a Legendre symbol, Is it? It is indeed true that for most $x$ we have $1+x+x^2+\cdots +x^p\equiv x+1\pmod{p}$. $\endgroup$ – André Nicolas May 18 '15 at 2:47
  • $\begingroup$ i meant to write (p/i)! $\endgroup$ – user241340 May 18 '15 at 2:52
  • $\begingroup$ Or did you mean $\binom{p}{i}$, binomial coefficient, no bar? $\endgroup$ – André Nicolas May 18 '15 at 2:56
  • $\begingroup$ yeah, thats what i meant? no bar $\endgroup$ – user241340 May 18 '15 at 2:57
  • 1
    $\begingroup$ And you meant the sum to start at $i=0$, right? $\endgroup$ – André Nicolas May 18 '15 at 2:57

All $\binom{p}{i} \equiv 0$ unless $i =0, p$ so all these terms go away from the sum only the terms that remain are 1 and $x$. Hence the result. Or by using binomial theorem we have $\sum_{i =0}^{p} \binom{p}{i}x^i=(1+x)^p$ so now by Fermat's little theorem we have $(1+x)^p \equiv (1+x)$.


There's a difference between modular arithmetic and equality. Unless you have coded your answer improperly, you've made an error in notation:

The symbol congruence is a relation which has to do with mod n. An equals sign is a more (probably the most ubiquitous and fundamental) general relation.

Equality is reserved for more fundamental answers. Mod n deals with equivalence classes of integers and how we can partition numbers into these equivalence classes.

You probably know all of this, just want to help!


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.