LOGIN/REGISTER
Please Wait...
It is currently Sep 09, 2010, 2:08 am
Post new topic Reply to topic  Page 1 of 1
  [ 6 posts ]  Share: Facebook
Author Message
Peter
Birch & Swinnerton Dyer
User avatar

Posts: 5245
Location: Ghent
Belgium
Post Posted: May 24, 2007, 5:24 pm • # 1 


Let k,m, and n be natural numbers such that m+k+1 is a prime greater than n+1. Let c_{s}=s(s+1). Prove that the product (c_{m+1}-c_{k})(c_{m+2}-c_{k})\cdots (c_{m+n}-c_{k}) is divisible by the product c_{1}c_{2}\cdots c_{n}.
 
 
Peter
Birch & Swinnerton Dyer
User avatar

Posts: 5245
Location: Ghent
Belgium
Post Posted: Jul 21, 2007, 7:24 pm • # 2 


nicetry007 wrote:
The product

(c_{m+1}-c_{k})\; (c_{m+2}-c_{k})\;\cdots\; (c_{m+n}-c_{k})\;

= \left((m+1)(m+2)-k(k+1)\right)\;\left((m+2)(m+3)-k(k+1)\right)\;\cdots \left((m+n)(m+n+1)-k(k+1)\right)

= (m+1-k)(m+k+2)\; (m+2-k)(m+k+3)\;\cdots\;(m+n-k)(m+k+n+1)

= \Pi_{i =1}^{n}(m+i-k) \;\Pi_{i=1}^{n}(m+k+i+1)

The product

c_{1}\;c_{2}\; \cdots \; c_{n}= (1 \cdot 2)\; (2 \cdot 3)\; \cdots \; (n \cdot (n+1))\; = n! (n+1)!

The ratio
\frac{(c_{m+1}-c_{k})\; (c_{m+2}-c_{k})\;\cdots\; (c_{m+n}-c_{k})\;}{c_{1}\;c_{2}\; \cdots \; c_{n}}

= \frac{\Pi_{i =1}^{n}(m+i-k) \;\Pi_{i=1}^{n}(m+k+i+1)}{n! (n+1)!}

= \;^{(m+n-k)}C_{n}\;\cdot \; \left( \frac{1}{m+k+1}\right) \;\cdot \;^{(m+k+n+1)}C_{ n+1}

Since n+1\; < \;m+k+1, the binomial term ^{(m+k+n+1)}C_{ n+1} is divisible by (m+k+1). Hence,

\left( \frac{1}{m+k+1}\right) \;^{(m+k+n+1)}C_{ n+1} is an integer and the product (c_{m+1}-c_{k})\; (c_{m+2}-c_{k})\;\cdots\; (c_{m+n}-c_{k})\; is divisible by c_{1}\;c_{2}\; \cdots \; c_{n}.

_________________
Boo!
 
 
phill
New Member

Posts: 12
Post Posted: Dec 03, 2008, 2:05 pm • # 3 


Could you explain me how you reduced
\frac{\Pi_{i =1}^{n}(m+i-k) \;\Pi_{i=1}^{n}(m+k+i+1)}{n! (n+1)!}
to:
\;^{(m+n-k)}C_{n}\;\cdot \; \left( \frac{1}{m+k+1}\right) \;\cdot \;^{(m+k+n+1)}C_{ n+1}
Thank you.
 
 
Peter
Birch & Swinnerton Dyer
User avatar

Posts: 5245
Location: Ghent
Belgium
Post Posted: Dec 03, 2008, 5:18 pm • # 4 


Yeah, that reduction is wrong indeed.

I also think an extra condition m>k or m+n<k wouldould be necessary, otherwise we have to show 0|c_1\cdots c_n, which is obviously false.

_________________
Boo!
 
 
YeOldeMan
New Member

Posts: 6
Location: Singapore
Singapore
Post Posted: Jan 06, 2009, 12:01 pm • # 5 


Write m + k + 1 =: p (a prime) > n + 1. Note that
c_{1}c_{2} \cdots c_{n} = (1 \cdot 2) (2 \cdot 3) \cdots (n \cdot (n + 1)) = n! (n + 1)! = (n + 1)(n!)^2

whilst
\begin{array}{cl} & (c_{m + 1} - c_{k}) (c_{m + 2} - c_{k})\cdots (c_{m + n} - c_{k})\\ \mbox{ =} & \left(...

Now I am going to show that (n+1) \left| {{p+n} \choose p} \right. i.e. \frac{1}{n+1} {{p+n} \choose p} \in \mathbb{Z} and we are done.
\frac{1}{n+1} {{p+n} \choose p} = \frac{(p+n)!}{(n+1)!p!} = \frac{1}{p}\frac{(p+n)!}{(n+1)!(p-1)!} = \frac{1}{p}{{p+n}\choose...
Note that p | (p+n)! (since p<p+n), but p \not| (n+1)! (since n+1<p) and p \not| (p-1)! (since p-1<p).
So the prime p \left|\frac{(p+n)!}{(n+1)!(p-1)!} \right. \blacklozenge
 
 
nicetry007
Hodge Conjecture

Posts: 81
Post Posted: Jul 25, 2009, 4:25 am • # 6 


Phill and Peter,

The reduction is not wrong. If m+1 \leq k \leq m+n, then the result is trivially true as c_1c_2...c_n|0. If k < m+1, then follow the proof from the second post.
 
 
Display posts from previous:  Sort by  
  Share on Facebook Previous topic | Next topic 

Community » Olympiad Section » Number Theory » PEN » Official PEN problems » Divisibility Theory

All times are UTC - 8 hours [ DST ]
Share: Facebook
Post new topic Reply to topic  Page 1 of 1
  [ 6 posts ] 

Login
Username:   Password:   Log me on automatically each visit  

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Alcumus
Art of Problem Solving's FREE innovative online learning system. Over 3,500 problems and solutions!
For The Win!
LIVE, FREE, online multiplayer math game. A fun way to practice your math skills while competing with other players. Great practice for MATHCOUNTS Countdown Round!