Prev: Mathematical Convention
Next: Project Euler problem 140
From: Rob Johnson on 19 Apr 2010 14:51
In article <560716a1-74f3-4dd7-8a24-5a686895ec01(a)u31g2000yqb.googlegroups.com>,
recoder <kurtulmehtap(a)gmail.com> wrote:
>On 19 Nisan, 18:56, Chip Eastham <hardm...(a)gmail.com> wrote:
>> On Apr 19, 10:24 am, recoder <kurtulmeh...(a)gmail.com> wrote:
>>
>> > I observed that
>> > C(n-1,k) mod n = (-1)^k for all k between 0 and n-1
>> > where
>> > C(n-1,k) is a binomial coefficient C(n-1,k)= (n-1)! / ((k!)(n-
>> > k)!) .
>>
>> > I tried to verify it for large numbers by using a big number online
>> > calculator athttp://world.std.com/~reinhold/BigNumCalc.html
>> > I tried to calculate C(2046,1023) mod 2047 but it doesnt produce 1.
>>
>> > Is my observation wrong or do I need a better calculator?
>>
>> Maybe I'm not understanding the conjecture,
>> but consider n = 6:
>>
>> C(5,0) = 1 okay, (-1)^0 mod 6
>> C(5,1) = 5 okay, (-1)^1 mod 6
>> C(5,2) = 10 =C2 ??? not (-1)^2 mod 6
>>
>> regards, chip
>
>Sorry, n has o be an odd integer

Then C(8,3) = 56 == 2 mod 9

However if n is prime, then each k from 1 to n-1 has an inverse
modulo n. Thus, n/k = n(1/k) = 0 mod n for each k from 1 to n-1.
Therefore

n-k
--- = 0-1 = -1 mod n
k

Next, show that
n-k
C(n-1,k) = C(n-1,k-1) ---
k

These two facts imply that C(n-1,k) = (-1)^k mod n.

Rob Johnson <rob(a)trash.whim.org>
take out the trash before replying
to view any ASCII art, display article in a monospaced font
First  |  Prev  | 
Pages: 1 2
Prev: Mathematical Convention
Next: Project Euler problem 140