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?

  • $\begingroup$ $\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$. $\endgroup$ – user647486 Mar 20 at 19:53
  • $\begingroup$ I'm sorry. I should've added that $q$ is one of at least two distinct prime factors. $\endgroup$ – Sebastian Oberhoff Mar 20 at 21:03
  • $\begingroup$ @SebastianOberhoff my answer shows this can be true even when $p$ has distinct factors. For instance, try $q=5$, $p=5\cdot49$. $\endgroup$ – Ethan MacBrough Mar 20 at 21:13
  • $\begingroup$ @SebastianOberhoff $3$ is one of the exactly two prime factors of $6$ and $3$ doesn't divide $\binom{6}{3}=20$. $\endgroup$ – user647486 Mar 20 at 21:21
  • 1
    $\begingroup$ 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$. $\endgroup$ – 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$.


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.