GCD formula proof
Eitan Y. Levine
August 10, 2023


Formula:


GCD( {binomial(n,k)}_{k=1..n-1} ) is p if n=p^b for b >= 1 and prime p, otherwise the GCD is 1.


Proof:


The binomial coefficient can be explicitly written as a fraction with numerator
(n!/(n-k)!) and denominator k!.
The numerator (itself written here as a fraction) is the product of the *last* k numbers in the range [1,n], and the denominator is the product of the *first* k numbers in this range.


Notation: m(n) will denote the multiplicity of p as a prime factor in n.


I will leave the proofs of the following statements for the reader:


A. Given any b >= 1 and any prime p, the sequence m(n), n=1..infinity is cyclic with period p^b, except the last number whose multiplicity may be different in every cycle.


B. The last number in the first cycle is p^b, and the last number in the c-th cycle is c*p^b. If c is not divisible by p, then the last numbers in these two cycles have the same multiplicity as well.


C. Within the first cycle, 1..p^b, the multiplicities of p in all numbers except p^b have the following symmetry: m(k)=m(p^b-k).


Now, the original claim has two parts:
1. If n is not a prime power, the GCD of the internal numbers (all except the edge 1's) in the n-th row of Pascal's triangle is 1.
2. If n is a prime power, n=p^b, then the GCD is p.


Proof of 1:


The GCD must be a divisor of binomial(n,1)=n, so its prime factors must be a subset of the prime factors of n.
Let p be a prime factor of n, such that n=c*p^b, where c is greater than 1 and not divisible by p. Consider the coefficient binomial(n,p^b) = (n!/(n-p^b)!) / (p^b)!.
The denominator is the product of all of the numbers in the first p^b cycle and the numerator is the product of all of the numbers in the c-th cycle. Following statements A and B, these two cycles share the same pattern of p-multiplicity, so all powers of p cancel out in the fraction, and the GCD, which must be a divisor of this coefficient, cannot have p as a factor.
This holds for every prime factor of n, and therefore the GCD must be 1.


Proof of 2:


In this case, the GCD must be a power of p, because binomial(n,1)=n=p^b. The lowest multiplicity of p as a prime factor in any of the coefficients in this row will determine the GCD.


The denominator and the numerator now contain the first and last k numbers in the first p^b cycle, respectively. Following statement C, the smaller k-1 numbers in each group have the same p multiplicities (in reverse order), and the powers of p coming from them cancel out in the fraction.


We are left with the p's in p^b and in k, in the numerator and denominator respectively, so the overall multiplicity is b-m(k). Since max_{0<k<p^b}(m(k))=b-1 (e.g. for k=p^(b-1)), the minimal p multiplicity in the internal coefficients is 1 so the GCD is p.