wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Binomial Theorem for Primes
        
(Message started by: Sir Col on Jun 5th, 2004, 9:59am)
Title: Binomial Theorem for Primes
Post by Sir Col on Jun 5th, 2004, 9:59am
Consider the following results,
75 = 16807 [equiv] 2 mod 5
35+45 = 1267 [equiv] 2 mod 5

117 = 19487171 [equiv] 4 mod 7
37+87 = 2099339 [equiv] 4 mod 7


Given that p is prime, and a,b[in][bbn], prove that in general, (a+b)p [equiv] ap+bp mod p.
Title: Re: Binomial Theorem for Primes
Post by Grimbal on Jun 5th, 2004, 6:34pm
;D
Title: Re: Binomial Theorem for Primes
Post by Sir Col on Jun 6th, 2004, 3:02am

on 06/05/04 at 18:34:35, Grimbal wrote:
;D

Eh? I must have missed the lectures on "Proof by Smilies".
Title: Re: Binomial Theorem for Primes
Post by Grimbal on Jun 7th, 2004, 3:00am
It seems to me you are obfuscating a much simpler equation.  My smile says: I know.

::[hide]For p prime, ap [equiv] a mod p.[/hide]::
Title: Re: Binomial Theorem for Primes
Post by Sir Col on Jun 7th, 2004, 4:41am
The problem is not quite that trivial. Fermats Little Theorem only demonstrates that (a+b)p is congruent with a+b modulo p.

However, you are correct, I was partially obfuscating the problem, namely: except for the first and last terms in the expansion of (a+b)n, show that n divides the coefficients of each term iff n is prime.
Title: Re: Binomial Theorem for Primes
Post by towr on Jun 7th, 2004, 5:10am
For the original question
::[hide](a+b)p % p [equiv] (a+b) % p [equiv] [a % p + b % p] % p  [equiv] [ap % p + bp % p] % p [equiv] [ap + bp] % p [/hide]::
?
Title: Re: Binomial Theorem for Primes
Post by Sir Col on Jun 7th, 2004, 12:23pm
Nicely done, towr! I had not anticipated such a simple solution.

Apologies, Grimbal, for doubting your clever insight!  :-[

Okay...
Quote:
Except for the first and last terms in the expansion of (a+b)n, show that n divides the coefficients of each term iff n is prime.

And it is not sufficient to use F.L.T. to demonstrate that the sum of coefficients must be divisible by n; although I hadn't realised that until you clever twosome demonstrated it. Consider the following:
(a+b)2 = a2 + 2ab + b2
(a+b)3 = a3 + 3a2b + 3ab2 + b3
(a+b)4 = a4 + 4a3b + 6a2b2 + 4ab3 + b4

Clearly 2|2, 3|3, and 4|(4+6+4), but 4 does not divide 6.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board