Proof for a congruence relation

  • I
  • Thread starter DaTario
  • Start date
  • #1
913
27
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
 

Answers and Replies

  • #2
anuttarasammyak
Gold Member
723
315
Write LHS in the form of fraction. Numerator includes p successive multiples, i.e.
[tex]n(n-1)....(n-p+1)[/tex] so we know it must have factor p. Denominator ##(p-1)!^2## cannot have factor p.
 
  • #3
913
27
But the denominators also have ##(n-p)!## and ##(n-p+1)!##.
And now I realize that ##n## need not to have an upper bound.
 
  • #4
anuttarasammyak
Gold Member
723
315
Please show me full form of fraction to check your claim.
 
  • #5
913
27
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?
 
  • #6
913
27
We have:
$$ \frac{(n-1)!}{(p-1)! (n-p)!}\frac{(n)!}{(p-1)! (n-p+1)!} \equiv 0 (\mbox{mod p}) $$
 
  • #7
anuttarasammyak
Gold Member
723
315
So it is written as
[tex]\frac{(n-1)(n-2)...(n-p+1)}{(p-1)!}\frac{n(n-1)(n-2)...(n-p+2)}{(p-1)!}[/tex][tex]=\frac{n(n-1)^2(n-2)^2...(n-p+2)^2(n-p+1)}{(p-1)!^2}[/tex]
You see n(n-1)(n-2)...(n-p+1) in the numerator.
 
Last edited:
  • #8
913
27
I see it. Twice, almost (there are ##(n-1)!## and ##n!##.)
 
  • #9
913
27
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)!)
 
  • Like
Likes anuttarasammyak
  • #10
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
16,860
8,700
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.
 
  • #11
anuttarasammyak
Gold Member
723
315
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.
 
  • #12
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
16,860
8,700
I would like to know ##p^2## is mentioned in what intention.
It's generally true for ##n > p##.
 
  • #13
142
62
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##.
 
  • #14
913
27
Thank you very much, suremarc, but could you show, please, more steps of this proposed demonstration?
 
  • #15
142
62
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!}##.)
 
  • #16
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
16,860
8,700
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##.
 
  • #17
142
62
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.
 
  • #18
913
27
Thank you very much, suremarc and PeroK.
 

Related Threads on Proof for a congruence relation

Replies
1
Views
2K
  • Last Post
Replies
3
Views
4K
Replies
1
Views
3K
  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
23
Views
4K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
13
Views
2K
Top