mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2021-11-27, 16:32   #23
charybdis
 
charybdis's Avatar
 
Apr 2020

22116 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
...furthermore: k*binomial(p,k)=p*binomial(p-1,k-1) is also true...
And we can do this combinatorially too: both are the way of choosing k elements from a set of p elements, where we label one of those k elements as "special".
We get k*binomial(p,k) by choosing the set of k elements and then picking the special element, and p*binomial(p-1,k-1) by first picking the special element and then choosing the other k-1 elements from the remaining p-1 elements of our set.

More famously, binomial(p-1,k-1)+binomial(p-1,k)=binomial(p,k) is easiest to see combinatorially: we partition the binomial(p,k) choices of k elements from the numbers {1,...,p} into two, depending on whether they contain 1 or not. binomial(p-1,k-1) is the number of choices containing 1, and binomial(p-1,k) is the number of choices not containing 1.

Last fiddled with by charybdis on 2021-11-27 at 16:35
charybdis is offline   Reply With Quote
Old 2021-11-29, 16:05   #24
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

210×5 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
Modified your idea, close to a pure combinatorial proof:

The k=0 case is trivial, so assume that 0<k<p,
it is known: binomial(p-1,k-1)+binomial(p-1,k)=binomial(p,k) [for here you don't need that p is prime]
<snip>
Of course! And for 0 < k < p, \frac{p!}{k!(p-k)!} clearly is divisible by p because the denominator is composed of factors less than p.

The result can be extended slightly. Since p divides binomial(p,k) for 0 < k < p when p is prime, we have the "freshman's dream" polynomial identity in Fp[x,y]

(x\;+\;y)^{p}\;=\;x^{p}\;+\;y^{p}

Repeatedly raising to the pth power, we see that in Fp[x,y] for any positive integer n,

(x\;+\;y)^{p^{n}}\;=\;x^{p^{n}}\;+\;y^{p^{n}}

which shows that binomial(pn,k) is divisible by p for 0 < k < pn.

Then the above argument shows that for p prime and any positive integer n,

{p^{n}-1\choose k}\equiv -1^k \;\pmod p

Last fiddled with by Dr Sardonicus on 2021-11-29 at 17:39 Reason: Omit repeated word
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
k*b^n+/-c where b is an integer greater than 2 and c is an integer from 1 to b-1 jasong Miscellaneous Math 5 2016-04-24 03:40
Sum of reciprocals of prime k-tuplets mart_r Math 10 2009-04-05 07:29
Always an integer. mfgoode Puzzles 18 2007-07-13 18:03
Sum of all integer digits of all primes between 1 an n AntonVrba Math 2 2006-09-20 17:20
Primes for a mersenne integer DWT FNT gbvalor Math 1 2003-09-08 16:05

All times are UTC. The time now is 07:04.


Tue Nov 30 07:04:43 UTC 2021 up 130 days, 1:33, 0 users, load averages: 0.72, 1.05, 1.10

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.