# Nice problem - Pascal's triangle

David113
Posers and Puzzles 12 Jan '10 22:50
1. 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.
2. ua41
Sharp Edge
12 Jan '10 23:53
I'm not as fluent in mathematics, but could one use the Euclidean algorithm to do such a thing?
3. 13 Jan '10 13:47
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.
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?
4. TheMaster37
Kupikupopo!
17 Jan '10 17:12
Here'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.