How to Prove a Congruence Relation for Prime Numbers?

[DaTario]

TL;DR

Hi All, I would like to ask for help in proving the following congruence relation:
Let p be a prime number and let $n$ be a natural such that $p < n < p^2$. Then
$$ {n-1 \choose p-1} {n \choose p-1} \equiv 0 (\mbox{mod p}) $$

Hi,
I would like to prove the following congruence relation:

Let p be a prime number and let $n$ be a natural such that $p < n < p^2$.
Then
$$ {n-1 \choose p-1} {n \choose p-1} \equiv 0 (\mbox{mod p}) .$$

I am expecting it to have a rather trivial proof. Thanks in advance for any contribution, ...

Best Regards,
DaTario

 

[anuttarasammyak]

Write LHS in the form of fraction. Numerator includes p successive multiples, i.e.
n(n-1)...(n-p+1) so we know it must have factor p. Denominator $(p-1)!^2$ cannot have factor p.

 

[DaTario]

But the denominators also have $(n-p)!$ and $(n-p+1)!$.
And now I realize that $n$ need not to have an upper bound.

 

[anuttarasammyak]

Please show me full form of fraction to check your claim.

 

[DaTario]

Ok, now I got it (you showed a part of the numerator and made some simplifications). But I am still not so confident that the whole proposition is demonstrated. Firstly because it seems that you have made the simplification exactly with the factorial of (p-1), which you claim appears in the denominator at the end. Forgive me if I am asking too much. Can we go step by step in this proof?

 

[DaTario]

We have:
$$ \frac{(n-1)!}{(p-1)! (n-p)!}\frac{(n)!}{(p-1)! (n-p+1)!} \equiv 0 (\mbox{mod p}) $$

 

[anuttarasammyak]

So it is written as
\frac{(n-1)(n-2)...(n-p+1)}{(p-1)!}\frac{n(n-1)(n-2)...(n-p+2)}{(p-1)!}=\frac{n(n-1)^2(n-2)^2...(n-p+2)^2(n-p+1)}{(p-1)!^2}
You see n(n-1)(n-2)...(n-p+1) in the numerator.

 

[DaTario]

I see it. Twice, almost (there are $(n-1)!$ and $n!$.)

 

[DaTario]

The formalization of this proof requires one to point out that between $n$ and $(n-p+1)$ there is certainly at least one multiple of $p$, doesn't it?

(I still have the impression that you are simplifying the numerator with the (p-1)! instead of doing so with the factor (n-p)!)

 

[PeroK]

The formalization of this proof requires one to point out that between $n$ and $(n-p+1)$ there is certainly at least one multiple of $p$, doesn't it?

(I still have the impression that you are simplifying the numerator with the (p-1)! instead of doing so with the factor (n-p)!)

An idea:

You could look at the factors of $p$ generally in numbers between $p$ and $p^2$.

PS There is an elementary proof based on that idea. Try with $p = 5$ first, perhaps, then generalise.

 

[anuttarasammyak]

And now I realize that n need not to have an upper bound.

You could look at the factors of p generally in numbers between p and p2.

I would like to know $p^2$ is mentioned in what intention.

 

[PeroK]

I would like to know $p^2$ is mentioned in what intention.

It's generally true for $n > p$.

 

[suremarc]

I think you could prove this using Kummer’s theorem, which expresses the p-adic valuation of ${n\choose m}$ in terms of digit sums. I worked through it partially, and you end up with something like $v_p({n\choose p-1})=1+\frac{s_p(n+1)-s_p(n)}{p-1}$ if $p|n+1$, or otherwise just $1$. Assuming that $n\geq p$.

 

[DaTario]

Thank you very much, suremarc, but could you show, please, more steps of this proposed demonstration?

 

[suremarc]

I changed my mind while writing out my steps, because I made some mistakes and there is a much simpler proof along the lines of what PeroK stated. Mainly, use Wilson’s theorem to show that $v_p((p-1)!)=0$, and then one has $$v_p\Bigg({n\choose p-1}\Bigg)=v_p((n)_{p-1})$$ which is nonzero if and only if there is a multiple of $p$ between $n-(p-1)$ and $n,$ inclusive. ($(n)_k$ is a falling factorial, or just $\frac{n!}{k!}$.)

 

[PeroK]

Thank you very much, suremarc, but could you show, please, more steps of this proposed demonstration?

$$ {n-1 \choose p-1} {n \choose p-1} = \big ( \frac{1}{(p-1)!} \big )^2\big ( \frac{n!}{(n-p)!} \big ) \big (\frac{(n-1)!}{(n-p+1)!} \big ) $$
Now count the factors of $p$. The first term has none, the last term must have at least as many in the numerator as the denominator. And, the middle term must have at least one more factor of $p$ in the numerator. This holds for any $n > p$.

 

[suremarc]

D’oh. Why do I keep bringing in number theory theorems? (p-1)! is obviously not divisible by p, no need for Wilson’s theorem.

 

[DaTario]

Thank you very much, suremarc and PeroK.