Author |
Topic: Binomial Theorem for Primes (Read 918 times) |
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Binomial Theorem for Primes
« on: Jun 5th, 2004, 9:59am » |
Quote Modify
|
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.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Binomial Theorem for Primes
« Reply #1 on: Jun 5th, 2004, 6:34pm » |
Quote Modify
|
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Binomial Theorem for Primes
« Reply #3 on: Jun 7th, 2004, 3:00am » |
Quote Modify
|
It seems to me you are obfuscating a much simpler equation. My smile says: I know. ::For p prime, ap [equiv] a mod p.::
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Binomial Theorem for Primes
« Reply #4 on: Jun 7th, 2004, 4:41am » |
Quote Modify
|
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.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Binomial Theorem for Primes
« Reply #5 on: Jun 7th, 2004, 5:10am » |
Quote Modify
|
For the original question ::(a+b)p % p [equiv] (a+b) % p [equiv] [a % p + b % p] % p [equiv] [ap % p + bp % p] % p [equiv] [ap + bp] % p :: ?
|
« Last Edit: Jun 7th, 2004, 5:12am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Binomial Theorem for Primes
« Reply #6 on: Jun 7th, 2004, 12:23pm » |
Quote Modify
|
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.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
|