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

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?

• $\binom{6}{3}=20$. But it is not that it is going to be false every time, since $(x+1)^4=x^4 + 4 x^3 + 6 x^2 + 4 x + 1$ which is $x^4+1$ mod $2$. – user647486 Mar 20 at 19:53
• I'm sorry. I should've added that $q$ is one of at least two distinct prime factors. – Sebastian Oberhoff Mar 20 at 21:03
• @SebastianOberhoff my answer shows this can be true even when $p$ has distinct factors. For instance, try $q=5$, $p=5\cdot49$. – Ethan MacBrough Mar 20 at 21:13
• @SebastianOberhoff $3$ is one of the exactly two prime factors of $6$ and $3$ doesn't divide $\binom{6}{3}=20$. – user647486 Mar 20 at 21:21
• Such that you know. The notation $P(x)\equiv_p Q(x)$ without quantifying the values of $x$ is used to denote congruence between polynomials. This is defined term-wise and not by the congruence of their values in, for example $\mathbb{Z}$. They claim that EthanMacBrough made in the comment is only that $(x+1)^{245}-x^{245}-1$ vanishes at all elements of $\mathbb{F}_5$. Not that this is the zero polynomial. Similarly the claim that he makes in the answer is not that for those choices of $p$ and $q$, $(x+1)^p-x^p-1$ is the zero polynomial mod $q$, but that it vanishes on $\mathbb{F}_q$. – user647486 Mar 21 at 0:15

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$$.