mersenneforum.org Help with exercise questions from Elementary Number Theory
 Register FAQ Search Today's Posts Mark Forums Read

2021-11-27, 16:32   #23
charybdis

Apr 2020

24816 Posts

Quote:
 Originally Posted by R. Gerbicz ...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

2021-11-29, 16:05   #24
Dr Sardonicus

Feb 2017
Nowhere

10100111010102 Posts

Quote:
 Originally Posted by R. Gerbicz Modified your idea, close to a pure combinatorial proof: The k=0 case is trivial, so assume that 0
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

 2021-12-03, 13:29 #25 MattcAnderson     "Matthew Anderson" Dec 2010 Oregon, USA 24·32·7 Posts more of this I am excited about this. *smile*
 2021-12-10, 17:33 #26 bur     Aug 2020 79*6581e-4;3*2539e-3 5×97 Posts 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".

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong Miscellaneous Math 5 2016-04-24 03:40 mart_r Math 10 2009-04-05 07:29 mfgoode Puzzles 18 2007-07-13 18:03 AntonVrba Math 2 2006-09-20 17:20 gbvalor Math 1 2003-09-08 16:05

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

Sat Jan 22 08:14:38 UTC 2022 up 183 days, 2:43, 0 users, load averages: 1.42, 1.16, 1.15
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 4, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://mersenneforum.org/showthread.php?s=da1ab7a6f9b8fcc3dc67f3c83b0d530f&p=594927#post594927", "fetch_time": 1642839278000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2022-05/segments/1642320303779.65/warc/CC-MAIN-20220122073422-20220122103422-00461.warc.gz", "warc_record_offset": 441672295, "warc_record_length": 9942, "token_count": 937, "char_count": 2876, "score": 4.15625, "int_score": 4, "crawl": "CC-MAIN-2022-05", "snapshot_type": "latest", "language": "en", "language_score": 0.8199666142463684, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00035-of-00064.parquet"}