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 <kfoster@rmi.net>
Subject: Re: (k^2+1)k | binomial(k^2+1,k)
Date: Tue, 16 Nov 1999 16:55:44 GMT
Newsgroups: sci.math

In <abi5j5yk4v9r@forum.swarthmore.edu>, Leroy Quet <qqquet@hotbot.com>
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.