# Proof for a congruence relation

• I
Summary:
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
Gold Member
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.

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
Gold Member

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?

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

anuttarasammyak
Gold Member
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.

Last edited:
I see it. Twice, almost (there are ##(n-1)!## and ##n!##.)

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)!)

anuttarasammyak
PeroK
Homework Helper
Gold Member
2020 Award
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
Gold Member
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
Homework Helper
Gold Member
2020 Award
I would like to know ##p^2## is mentioned in what intention.
It's generally true for ##n > p##.

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

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

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
Homework Helper
Gold Member
2020 Award
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.

Thank you very much, suremarc and PeroK.