home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / math / 18582 < prev    next >
Encoding:
Internet Message Format  |  1993-01-21  |  2.1 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!ub!penny!mary.cs.fredonia.edu!kwong
  2. From: kwong@mary.cs.fredonia.edu (Harris Kwong)
  3. Newsgroups: sci.math
  4. Subject: Re: Binomial coefficient modulo prime power-- looking for a reference.
  5. Message-ID: <1993Jan21.152802.12029@penny.cs.fredonia.edu>
  6. Date: 21 Jan 93 15:28:02 GMT
  7. References: <1993Jan20.215654.20548@midway.uchicago.edu>
  8. Sender: news@penny.cs.fredonia.edu (News Administrator)
  9. Organization: Math / CS, State Univ. of N. Y. College at Fredonia
  10. Lines: 41
  11. X-Newsreader: Tin 1.1 PL3
  12.  
  13. tsai@cs.uchicago.edu (Shi-Chun Tsai) writes:
  14. : Define an integer function f(i) = i \choose k  mod p^a, where
  15. : i ranges over non-negative integers, k and a are any positive integers,
  16. : and p is a prime number.  Then it is not hard to prove that f is a
  17. : periodic function with period p^{\lfloor log_p k \rfloor + a}.
  18. : 
  19. : Actually, it can be generalized for modulo any composite number by using
  20. : the Chinese Remainder Theorem.  I believe this has been proved for a while,
  21. : but I couldn't find a reference for it.  Could anyone show me a pointer?
  22. : Thanks in advance.
  23. : 
  24. : Shi-Chun
  25.  
  26. It is indeed quite well-known.  Zabek [5] was probably the first one who
  27. published the result.  Applying Vandermonde's convolution, Trench [4]
  28. obtained identical period.  Fray [1] extended the result to q-binomial
  29. coefficients.  Recently, Kwong [2,3] obtained the same results by
  30. studying generating functions. 
  31.  
  32. 1. R.D. Fray, Congruence properties of ordinary and q-binomial
  33.    coefficients, Duke Math. J. 34 (1967), 467--480.
  34.  
  35. 2. Y.H.H. Kwong, Minimum periods of binomial coefficients modulo M,
  36.    Fibonacci Quarterly 27 (1989), 348--351.
  37.  
  38. 3. Y.H.H. Kwong, Periodicities of a class of infinite integer sequences
  39.    modulo M, J. Number Theory 31 (1989), 64--79.
  40.  
  41. 4. W.F. Trench, On the periodicities of certain sequence of residues,
  42.    Amer. Math. Monthly 67 (1960), 652--656.
  43.  
  44. 5. S. Zabek, Sur la p\'eriodicit\'e modulo m des suites de nombres
  45.    {n\choose k}, Ann. Univ. Mariae Curie-Sklodowska A10 (1956), 37--47.
  46.  
  47. --
  48. Harris Kwong
  49.  
  50. Dept. of Math. & Comp. Sci.
  51. SUNY College at Fredonia
  52. Fredonia,  NY   14063
  53. Email: kwong@mary.cs.fredonia.edu
  54.