Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!decvax!decuac!cvl!bhaskar
From: bhaskar@cvl.UUCP
Newsgroups: net.math
Subject: Re: Nifty math problem
Message-ID: <1317@cvl.UUCP>
Date: Fri, 21-Mar-86 16:09:14 EST
Article-I.D.: cvl.1317
Posted: Fri Mar 21 16:09:14 1986
Date-Received: Sun, 30-Mar-86 08:19:35 EST
References: <2222@jhunix.UUCP> <779@harvard.UUCP>
Distribution: net
Organization: Center for Automation Research, Univ. of Md.
Lines: 57
Summary: Messy proof to a Number Theory problem.

In article <779@harvard.UUCP>, greg@harvard.UUCP writes:
> 
> Let C(a,b) = a!/(b!*(a-b)!), and let p>3 be a prime number.
> Show that:
> 
> C(p*a,p*b) = C(a,b) mod p^3
> -- 
> gregregreg


I have a proof, but it is rather messy. Rather than use the most general 
notation, I have used examples to clarify a point. If a simpler proof is 
available, I would like to see it (by mail).

For e.g.
Consider C(5*3,5*2)   15.14.13.12.11.10.9.8.7.6
                    = -------------------------
                      10. 9. 8. 7. 6. 5.4.3.2.1
                   
                       ( 15.10 ) (14.13.12.11.9.8.7.6)
                    =   -------  --------------------
                       ( 10.5 )  ( 9. 8. 7. 6.4.3.2.1)

                    = C(3,2) * Mess 

 Thus in general, we consider messes of the form :

   [kp+p-1][kp+p-2]...[kp+1] [(k-1)p+p-1].[(k-1)p+1]...

divided by similar factors in the denominator.

If S(n,k) denotes the Stirling number of the 1'st kind then

   [kp+p-1] [kp+p-2] . [kp+1]

        = Sigma{ 0 <= i <= p-1 , (kp)^i * (-1)^(p-1+i) * S(p,i+1) }
        
        = S(p,1) - S(p,2) * (kp) + S(p,3) * (kp)^2    (mod p^3) .

Now, p * S(p,2) = p * (p-1)! * H(p-1) , where H(n) is the n'th harmonic no.
              
But (p-1)! * H(p-1) = 0  (mod p^2)   (* Wolstenholme's thm. *)

Therefore p * (p-1)! * H(p-1) = 0  (mod p^3) .

Also, S(p,k) = 0 (mod p)  (* easily proven *)

Therefore p^2 * S(p,k) = 0  (mod p^3) .

Thus [kp+p-1] ... [kp+1] = S(p,1)   (mod p^3) 

                         = (p-1)!   (mod p^3)

Since the numerator and denominator have the same number of factors of the
form [kp+p-1]...[kp+1] and since each is (p-1)! (mod p^3), the Mess
simplifies to 1  (mod p^3) and we are left with C(a,b).