4
$\begingroup$

I don't really know how to start this exercise. Do I have to use p-adic valuation ?

If it's the case it will give $\nu_p(\binom{k}{p})= \sum \limits_{r=1}^{\infty}\left(\left\lfloor \frac{k}{p^r} \right\rfloor-\left\lfloor \frac{p}{p^r} \right\rfloor -\left\lfloor \frac{k-p}{p^r} \right\rfloor \right)$.

Thanks in advance !

$\endgroup$
  • $\begingroup$ What does $[p]$ mean? If it means the same as "mod $p$", then this is wrong for $k=0$. $\endgroup$ – Wojowu Sep 12 '16 at 20:08
  • $\begingroup$ @wojowu Impossible because $p$ is at least $3$ $\endgroup$ – Maman Sep 12 '16 at 20:19
  • $\begingroup$ I suppose you also require $k\leq p$. Hint: what is $\lfloor k/p\rfloor$ if $k<p$? $\endgroup$ – Wojowu Sep 12 '16 at 20:27
  • $\begingroup$ @Wojowu It gives $0$ and for $k=p$ it's trivial. $\endgroup$ – Maman Sep 12 '16 at 20:40
  • $\begingroup$ One way is to use induction on k; prove it! ;) $\endgroup$ – The Number Theorist Sep 12 '16 at 20:55
1
$\begingroup$

Let $P(x)=x(x-1)\cdots (x-p+1)$. We know that $P(x)=x^p-x+pS(x)$, with $S\in \mathbb{Z}[x]$. Hence we get that $P^{\prime}(x)=px^{p-1}-1+pS^{\prime}(x)$, hence $P^{\prime}(x)=-1\mod{p}$. Now we have $P(x+p)=P(x)+pP^{\prime}(x)\mod{p^2}$, hence $P(x+p)=P(x)-p\mod{p^2}$. Let now be $Q(x)=P(x)/p!$. By the above, we get that for $x\in \mathbb{Z}$, we have $$Q(x+p)=Q(x)-\frac{p}{p!} \mod{p}$$

But $-\frac{p}{p!}=-\frac{1}{(p-1)!}=1\mod{p}$.

Hence we get that for $k\in \mathbb{N}$, we have $$\binom{k+p}{p}=\binom{k}{p}+1\mod{p}$$ And now an induction finish the job.

$\endgroup$
0
$\begingroup$

show that :

  • ${k \choose p} = \frac{k}{k-p}{k-1 \choose p} = (1+\frac{p}{k-p}){k-1 \choose p}$ so if $k \not\equiv 0 \bmod p$ then $k-p \ | {k-1 \choose p}$ and ${k \choose p} \equiv {k-1 \choose p} \bmod p$.

  • ${ap \choose p} \equiv a \bmod p$, since ${ap \choose p} = a {ap-1 \choose p-1}$ and ${ap-1 \choose p-1} = \prod_{m=1}^{p-1} \frac{ap-m}{m} \equiv \left(\prod_{m=1}^{p-1} (p-m) \right)\left(\prod_{m=1}^{p-1}m\right)^{-1}\equiv 1 \bmod p$

$\endgroup$
0
$\begingroup$

Let us define $jp$, with $j$ positive integer, the greatest multiple of $p$ lower than $k$. Now let us consider the definition of $\binom{k}{p}$ as $$\frac {k (k-1)(k-2)(k-3)...[k-(p-1)]}{p!}$$ The numerator is formed by $p$ consecutive numbers and can be expressed as a product of factors that are $\equiv i \pmod p$, where $i$ assumes all integer values between $0$ (this is the case of $jp$) and $p-1$. Because $1 \cdot 2 \cdot 3....\cdot (p-1) \equiv -1 \pmod p$, the whole numerator can be written as the product of $jp$ and a number $\equiv -1 \pmod p$. As a result, dividing the numerator by $p $ we get a number that is $\equiv -j \pmod p$.

On the other hand, the denominator $p!=p(p-1)!$ is the product of $p$ and a quantity $\equiv -1 \pmod p$, so that dividing it by $p$ we get a number that is $\equiv -1 \pmod p$.

Based on the considerations above, $\binom{k}{p}$ is given by a fraction where, simplifying both numerator and denominator by $p$, we are left with a ratio between a number that is $ \equiv -j \pmod p $ and another one that is $ \equiv -1 \pmod p $. It follows that the result of the fraction is $ \equiv j \pmod p $. Because $j=\lfloor k/p \rfloor $, we finally obtain

$$\binom{k}{p} \equiv \left\lfloor \frac{k}{p} \right\rfloor \pmod p$$

EDIT: since a comment asked to better explain the calculations for the numerator, I added an example below.

Let us set, for example, $k=7$ and $p=3$. So we have $jp=6$ and $j=2$. The binomial coefficient is given by the ratio

$$\frac {7 (7-1)(7-2)}{3!} $$

The numerator is formed by $3$ consecutive numbers and can be expressed as a product of factors that are $\equiv i \pmod 3$, where $i$ assumes all integer values between $0$ and $p-1=2$. In fact, the numerator can be written as $6(6+1)(3+2) $. The product of these factors, not considering $jp=6$, is $$(p-1)! \mod p = (3-1)! \pmod 3=2 \pmod 3$$ (note that we can also consider this last number as $-1 \pmod p $, although it is not necessary). Then, the numerator can be written as the product of $jp=6$ and a number $\equiv 2 \pmod 3$, i.e. it is $\equiv jp (p-1)! \pmod p=\equiv (6 \cdot 2) \pmod 3$.

The denominator is $3! $ and then can be written as the product of $p=3$ and $(p-1)!=2$, where this last number is $\equiv (p-1)! \pmod p = \equiv 2 \pmod 3$.

Then the initial binomial coefficient is the ratio of a quantity $ \equiv (6 \cdot 2) \pmod 3$ and another quantity that is $ \equiv (3 \cdot 2) \pmod 3$. Their ratio is then a number $\equiv 2 \pmod 3$, where the number $2$ simply reflects the initial value of $j$, which in turn is equal to $ \left\lfloor \frac{7}{3} \right\rfloor$. We then conclude that

$$\binom{7}{3} \equiv \left\lfloor \frac{7}{3} \right\rfloor \pmod 3$$

$\endgroup$
  • $\begingroup$ you don't need that $(p-1)! \equiv -1 \bmod p$, apart the $\frac{jp }{p}$ factors, the numerator is $\equiv (p-1)!$ and the denominator too $\endgroup$ – reuns Sep 12 '16 at 22:22
  • $\begingroup$ Thank you for your comment. The numerator is not simply $(p-1)!$. It is formed by a product of $p$ factors of the form $ap+i$, or $(a-1)p +i $, with $i$ ranging from $0$ to $p-1$. So the quantity $(p-1)! $ is not present in the numerator, but rather represents the product of the $i$ terms of the factors of the numerator. $\endgroup$ – Anatoly Sep 12 '16 at 22:41
  • $\begingroup$ that's what I meant $\frac{ k!}{jp (k-p)!} \equiv (p-1)! \bmod p$ $\endgroup$ – reuns Sep 12 '16 at 22:46
  • $\begingroup$ Sure. You're right. $\endgroup$ – Anatoly Sep 12 '16 at 22:58
  • $\begingroup$ I don't understand your operations on the numerator $\endgroup$ – Maman Sep 12 '16 at 23:13
0
$\begingroup$

I try to explain better my previous comment on induction's argument:

let's suppose $\binom{k}{p}=n$, so that $np\leq k <np+p$;

it's easy to prove $\binom{k+1}{p}=\frac{k+1}{k+1-p}\binom{k}{p}\equiv 1\left\lfloor \frac{k}{p} \right\rfloor\pmod{p}$, if $k+1\not\equiv 0\pmod p$, and in this case we are done since $k+1<pn+p$ and so $\left\lfloor \frac{k+1}{p} \right\rfloor=\left\lfloor \frac{k}{p} \right\rfloor$.

If otherwise $k+1=p^{r}a,a\not\equiv 0\pmod p$ then $\left\lfloor \frac{k+1}{p} \right\rfloor=p^{r-1}a$ and $\binom{k+1}{p}=\frac{p^{r-1}a}{p^{r-1}a-1}\binom{k}{p}$;

Now if $r\geq 2$ then $\binom{k+1}{p}\equiv 0\pmod p$ and similarly for $\left\lfloor \frac{k+1}{p} \right\rfloor=p^{r-1}a$;

if $r=1$ then $\binom{k+1}{p}=\frac{a}{a-1}\binom{k}{p}$ and its easy to see that $a=n+1$ so that $\binom{k+1}{p}=\frac{n+1}{n}\binom{k}{p}$;

But now if $n\not \equiv 0 \pmod p$ since $n=\left\lfloor \frac{k}{p} \right\rfloor$ and $n+1=\left\lfloor \frac{k+1}{p} \right\rfloor$ we get $\binom{k+1}{p}=\frac{n+1}{n}\binom{k}{p}\equiv \left\lfloor \frac{k+1}{p} \right\rfloor\pmod p$.

Finally if $n=p^{c}m$ with $m\not\equiv 0\pmod p$ then $\left\lfloor \frac{k+1}{p} \right\rfloor\equiv 1\pmod p$ and $\binom{k}{p}=\binom{p^{c+1}m+p-1}{p}=\frac{(p^{c+1}m+p-1)...(p^{c+1}m)}{p(p-1)!}=p^{c}mw$, with $w\equiv 1\pmod p$

and we get the desired equivalence, since $\binom{k+1}{p}=\frac{p^{c}m+1}{p^{c}m}\binom{k}{p}=(p^{c}m+1)w\equiv 1\pmod p$.

$\endgroup$

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.