12 Jan '10 22:50

Prove:

If two numbers greater than 1 appear in the same row in Pascal's triangle, then they cannot be coprime.

If two numbers greater than 1 appear in the same row in Pascal's triangle, then they cannot be coprime.

- Joined
- 25 Aug '06
- Moves
- 0

- Joined
- 11 Dec '09
- Moves
- 14434

Dulling my blade- Joined
- 02 Mar '06
- Moves
- 17881

13 Jan '10 13:47

i think i've seen this before and it was a relatively cute problem... don't remember the path towards solution though. maybe using the definition of the "choose" numbers, and seeing that some factor not cancelled in n!/k!(n-k)! must also necessarily be present in n!/(k+i)!(n-[k+i])! for any number i<(n-k)? something to that effect?*Originally posted by David113***Prove:**

If two numbers greater than 1 appear in the same row in Pascal's triangle, then they cannot be coprime.- Joined
- 25 Oct '02
- Moves
- 20443

Out of my mind17 Jan '10 17:12Here's my go at it. Might be wrong though :/

Let A = k!(n-k-1)! and C = GCD(k+1, n-k)

(n over k) = n! / k!(n-k)! = n! / A(n-k)

(n over k+1) = n! / (k+1)!(n-k-1)! = n! / (k+1)A

So the GCD of the two is Cn! / (k+1)(n-k)A = Cn! / (k+1)!(n-k)! = C(n over k) / (k+1)

Since both of the combination-numbers are not equal to 1 we know that k is not 0, n-1 or n.

From that we have that k+1 divides N but also is smaller than n. And thus the GCD > 1.