Why isn't $(x+1)^p \equiv_q x^p + 1$ if $q$ is a prime factor of $p$?

Question

Using the Binomial Theorem $(x+1)^p$ can be written out as $$ (x+1)^p = \sum_{k=0}^p \binom{p}{k} x^k\,. $$ All that's left to show then is that, if $q$ is a proper prime factor of $p$, then one of $\binom{p}{1}, \dots, \binom{p}{p-1}$ isn't divisible by $q$. For that consider $\binom{p}{q^t}$ where $q^t$ is the biggest power of $q$ that occurs in $p$. This coefficient is $$ \binom{p}{q^t} = \frac{p(p-1) \cdots (p-q^t+1)}{q^t(q^t-1) \cdots 1} = q \bigg(q^{t-1}k\frac{(p-1) \cdots (p - q^t + 1)}{q^t(q^t-1) \cdots 1} \bigg) $$ for some integer $k$. So, if we can just show that this big parenthesis doesn't work out to an integer, we're done. And I feel like there ought to be a quick way to finish the argument. But the only way I see to proceed is to painstakingly count the number of occurrences of $q$ in both the numerator and denominator and show that there aren't enough in the numerator to fully cancel the denominator. That's quite messy. Is there a more elegant maneuver?

Answer 1

In general it may actually be the case that indeed $(x+1)^p\equiv_q x^p+1$. As an example, take $q=3,p=9$.

In fact we can classify exactly which $p$ do this; it turns out that $(x+1)^p\equiv_q x^p+1$ for all $x$ if and only if $p=q(qk-k+1)$ for some $k$.

To see why this is true, let $g$ be a primitive generator of $\mathbb{F}_q^*$, i.e., $g^n=1$ iff ${q-1}|n$. Suppose $(x+1)^p\equiv_qx^p+1$. By plugging in $x=1$ and using induction, this would imply that $x^p\equiv_q x$ for all $x$, so $x^{p-1}\equiv_q 1$. In particular, $g^{p-1}\equiv_q 1$, so by definition $q-1|p-1$.

Writing out $p=q\cdot m$, this means there exists some $n$ such that $n(q-1)=mq-1$. Then $(n+(q-1))(q-1) = (m+(q-2))q$. Since $q$ cannot divide $q-1$ and $q$ is prime, this means $q|n+q-1$, so $q|n-1$. Thus we can write $n=qk+1$, which gives $mq-1 = (qk+1)(q-1)$, so expanding out the terms gives $m=qk-k+1$.

Conversely, if $p$ can be written in this form, then since every element $x\in\mathbb{F}_q^*$ has order dividing $q-1$, we get $x^p=x^{q(qk-k+1)}\equiv_q x^{k}x^{-k}x\equiv_q x$, from which the stated equality immediately holds.

---

EDIT. To answer your other question of whether it is true that $\binom{p}{q^t}\not\equiv_q 0$ where $q^{t}\mid p$ but $q^{t+1}\nmid p$: This can be proven as follows.

Let $m,n$ be arbitrary integers, and consider $\binom{mn}{m}=\frac{(mn)(mn-1)\cdots\left(mn-(m-1)\right)}{m!}$. We can remove a factor of $m$ from the top and bottom and are left with $\binom{mn}{m}=\frac{n(mn-1)\cdots\left(mn-(m-1)\right)}{(m-1)!}$. Now if $k$ is any factor of $m$ that divides $mn-j$ for some $j$, then $k$ must also divide $j$. Thus we can remove factors from the top and bottom until we're left with $\binom{mn}{m}=\frac{np}{q}$ where $m\nmid p$. Thus if $m$ divides $\binom{mn}{m}$ it must also divide $n$.

Now substituting $m=q^t$ and $mn=p$ immediately gives the desired result, since $q^t\mid\binom{p}{q^t}\implies q^t\mid\frac{p}{q^t}\implies q^{2t}\mid p$, contradicting maximality of $t$.