# Proof for a congruence relation

• I
• DaTario
So the proof is complete I guess.In summary, the conversation discusses proving a congruence relation involving prime numbers and natural numbers. The proposed proof involves simplifying the fraction in the left-hand side of the equation and using Wilson's theorem to show that the first and last terms must not have a factor of p, while the middle term must have at least one factor of p. This holds true for any n greater than p.

#### DaTario

TL;DR 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

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.

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})$$

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
DaTario said:
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.

DaTario said:
And now I realize that n need not to have an upper bound.
PeroK said:
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.

anuttarasammyak said:
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!}##.)

DaTario said:
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.