mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Homework Help (https://www.mersenneforum.org/forumdisplay.php?f=78)
-   -   Help with exercise questions from Elementary Number Theory (https://www.mersenneforum.org/showthread.php?t=27067)

 charybdis 2021-11-27 16:32

[QUOTE=R. Gerbicz;594026]...furthermore: k*binomial(p,k)=p*binomial(p-1,k-1) is also true...[/QUOTE]

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.

 Dr Sardonicus 2021-11-29 16:05

[QUOTE=R. Gerbicz;594026]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>[/QUOTE]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 [b]F[/b][sub]p[/sub][x,y]

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

Repeatedly raising to the p[sup]th[/sup] power, we see that in [b]F[/b][sub]p[/sub][x,y] for any positive integer n,

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

which shows that binomial(p[sup]n[/sup],k) is divisible by p for 0 < k < p[sup]n[/sup].

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

[TEX]{p^{n}-1\choose k}\equiv -1^k \;\pmod p[/TEX]

 MattcAnderson 2021-12-03 13:29

more of this

*smile*

 bur 2021-12-10 17:33

Thanks a lot for all the replies, it will take me while to get through all that.

By "reduced" I meant, there would be no smaller integer congruent to them mod p. I forgot about that smaller could also mean "negative".

All times are UTC. The time now is 08:12.