From: MDoerfner@aol.com (M. Doerfner) Subject: Re: Help me about Lucas theorem, thanks!!! Date: 21 Feb 1999 18:49:25 -0500 Newsgroups: sci.math BuddhaSon wrote: >1) Who would like to tell me about "Lucas theorem" ? Well, what exactly is it you want to know about "Lucas' theorem"? Infact, the french mathematician Edouard Lucas proved more than one theorem. Yet there is one that Lucas proved in 1878 that is nowadays referred to as "Lucas' theorem" by some number theorists. This particular theorem provides you with a quite elegant method to calculate binomial coefficients modulo a prime number: Lucas' Theorem Let p be a prime number and n, k positive integers. If (a_m ... a_0)_p is the p-adic representation of n and (b_m ... b_0)_p is the p - adic representation of k, then n a_m a_(m - 1) a_0 ( ) MOD p = ( ) ( ) ... ( ) MOD p. k b_m b_(m - 1) b_0 You can find a short and highly comprehensible proof of this result in David Singmaster, "Notes on binomial coefficients - A generalization of Lucas' congruence", J. London Math. Soc. (2), 8, pp. 545-548, (1974) >2) How does one test a "large integer" is a prime or not ? This definitly IS a never-ending story. For an introduction see any textbook on number theory and the bibliographies in there. There are also a whole variety of web sites dealing with this problem. If you are interested enough do some research on it. Hope this helps, M. Doerfner ============================================================================== From: Kurt Foster Subject: Re: (k^2+1)k | binomial(k^2+1,k) Date: Tue, 16 Nov 1999 16:55:44 GMT Newsgroups: sci.math In , Leroy Quet said: . (k^2+1)k divides binomial(k^2+1,k) for k= positive integer <=100. . It looks as if it should be easy to show for all positive integers k, . but I've given up. [snip] It's always true. You can prove it using the formula for the power of a prime dividing N! . Applying it to binomial coefficients gives the following well-known result: Let p be a prime number, N and m =< N positive integers. Then the power of p which divides binomial(N, m) is equal to the number of carries in the base-p addition, m + (N-m) = N. Consider the cases p|k and p|(k^2 + 1) separately.