Skip to main content
3 of 7
Reworked the answer
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

Define $a_n=\Phi(n)$ except $a_1=1$ These values are uniquely determined by $$n=\prod_{d \mid n}a_d.$$ From this it would be quick to get $a_n=c_n$ but , as requested, we won't. An important step is to observe that $gcd(a_m,a_n)=1$ if $\gcd(m,n)=c \lt m \lt n.$ This follows from $\gcd(\frac{m}{c},\frac{n}{c})=1$ by writing $m,n,c$ as products of the $a_i$ and simplifying.

If follows that $$n!=\prod_{k=1}^nk^{\lfloor n/k\rfloor}$$ and $$\binom{n}{m}=\frac{n!}{m!(n-m)!}=\prod_{k \le n}a_k^{e_{n,m,k}}$$ where the exponent $$e_{n,m,k}=\lfloor n/k \rfloor-\lfloor m/k \rfloor-\lfloor (n-m)/k \rfloor$$ Note that $0 \le e_{n,m,k} \le 1$ and $e_{n,m,k}=0$ if $k \mid m$ and $k \mid n.$

We hope to show that $$\gcd{\Large (}\binom{n}{1},\binom{n}{2},\cdots,\binom{n}{n-1}{\Large )}=a_n.$$ We certainly know that $a_n$ divides each of these binomial coefficients. We will now see that it is sufficient to consider just $\binom{n}{1}$ and the various $\binom{n}{n/p}$ as $p$ ranges over the prime divisors of $n.$

Let $n=q_1q_2\cdots q_j$ where the $q_j=p_j^{e_j}$ are powers of distinct primes and define $G_0=\binom{n}{1}$ and $G_i=\gcd(G_{i-1},\binom{n}{n/p_i})$ for $1 \le i \le j.$ Then $G_i$ is the product of the $a_k$ with $q_1q_2\cdots q_i \mid k \mid n.$ and $G_j=a_n$

I will illustrate with the example of $n=900=2^23^25^2$. So $G_0=\binom{900}{1}$, $G_1=\gcd(G_0,\binom{900}{900/2})$, $G_2=\gcd(G1,\binom{900}{900/3})$ and $G_3=\gcd(G_2,\binom{900}{900/5}).$ I claim that $G_3=a_{900}.$

$G_0=\binom{900}{1}$ is the product of the $26$ $a_k$ with $1 \lt k \mid 900.$ Of these, the $9$ which are multiples of $2^2$, namely $a_4,a_{12},a_{20},a_{36},a_{60},a_{100},a_{180},a_{300}$ and $a_{900}$ also divide $\binom{900}{900/2}=\binom{900}{450}$, the other $17$ have $e_{900,450,k}=0.$ There are many other $a_k$ with $e_{900,450,k}=1$ but all of them are relatively prime to $G_0$ by the important step above. Hence $G_1$ is exactly the product of the $9$ $a_k$ with $4 \mid k \mid 900$. Now $G_2=\gcd(G_1,\binom{900}{300})=a_{36}a_{180}a_{900}$ because the only other $a_k$ dividing $\binom{900}{300}$ are such that $k$ neither divides nor is a multiple of $4,12,20,60,100,300$ and hence all are relatively prime to $G_1$ by the important step. Finally $G_3=\gcd(G_2,\binom{900}{180})=a_{900}$ because the only other $a_k$ with $e_{900,180,k}=1$ are relatively prime to both $a_{36}$ and $a_{180}$.

I believe this does what was requested.


It may be helpful to look at a more abstract setting where essentially the same proof goes through. The idea is to replace each integer $n$ by a generalized integer $I_n$, replace $a_n$ by some appropriate $A_n$, define a generalized factorial $[I_n]!=I_1I_2\cdots I_n$ and then a generalized binomial coefficient $${n \brack m}=\frac{[I_n]!}{[I_m]![I_{n-m}]!},$$ and deduce that $\gcd\left( {n \brack 1},{n \brack 2},\cdots,{n \brack {n-1}}\right)=A_n$. What is meant by $\gcd$ needs to specified in some cases.

Suppose that we have a commutative ring $\mathcal{R}$ and within it a sequence of elements $I_1,I_2,I_3,\cdots$ with the property

$$\gcd(I_m,I_n)=I_{\gcd(m,n)} \tag{**}$$

or perhaps merely the weaker property

$I_d \mid I_n$ when $d\mid n$ $(*)$

Based just on $(*)$ we have that there are elements $A_1,A_2,\cdots$ uniquely defined by $I_n=\prod_{d\mid n}A_d.$ (Although we will not need it, it then follows that $I_n=\prod_{d\mid n}A_n^{\mu(n/d)}$ where $\mu$ is the classic Mobius function.)

A familiar and obvious choice with (**) is $I_n=1+X+\cdots+X^{n-1}.$ Then we have the cyclotomic polynomials $A_n=\Phi_n(X)$ defined by $$I_n=\prod_{d\mid n}A_d.$$ (Except that $A_1=1$.)

Examples with (*) include

  1. $I_n=n$ in $\mathbb{N}$
  2. The Fibonacci numbers $F_n$ in $\mathbb{N}$
  3. $I_n=u^n-v^n$ in $\mathbb{Z}[u,v]$
  4. $I_n=\frac{u^n-v^n}{u-v}=\Sigma_{k=0}^{n-1}u^{n-k-1}v^{k}$ in $\mathbb{Z}[u,v]$

Asides: We will always be able, if desired, to assume $A_1=I_1=1$ by replacing $I_n$ with $\frac{I_n}{I_1}$ as in 4. Example 1 is the case $u=v=1$ of 4 while example 2 is the case $u,v=(1\pm \sqrt{5})/2$ with the convenient feature $uv=-1$. The obvious choice above is example 4 with $u=X,v=1.$

In any case, given just (*) we can define a generalized factorial $$[I_n]!=I_1I_2I_3\cdots I_n$$ and it follows that $$[I_n]!=\prod_{k=1}^nA_k^{\lfloor n/k\rfloor}$$ as in the integer case.

We can also define a generalized binomial coefficient by

$${n \brack m}=\frac{[I_n]!}{[I_m]![I_{n-m}]!}=\prod_{k \le n}A_k^{e_{n,m,k}}$$

The argument above becomes $\gcd\left( {n \brack 1},{n \brack 2},\cdots,{n \brack {n-1}}\right)=A_n$ provided we do have the stronger condition $(**)$. This requires knowng what is meant by $\gcd$ and that it behaves as expected. I don't think (**) holds for example 4, but it does when $v=1$. The fact that it hold in the case of example 2 is perhaps due to the extra relation $uv=-1$.

In a ring $\mathcal{R}$ I will take as the definition of $\gcd(U,V)=W$ ($W$ is a gcd of $U$ and $V$) to be

$W \mid U$ and $W \mid V$ and $US+VT=W$ for some $S,T \in \mathcal{R}$.

Note that we do not assume that every pair $U,V$ have a $\gcd$. In $\mathbb{Z}[X]$ We do not have a $\gcd$ for $U=\Phi_4=X^2+1$ and $V=\Phi_2=X+1$. We can get $US+VT=2$ but not $1$.

Actually finding the the explicit cofactors might be impractical.

The fact that they exist follows (in certain of the examples above) from

  • $1n-1m=n-m$
  • $| F_{m+1}F_n-F_{n+1}F_m |= F_{n-m}$
  • $1\frac{X^n-1}{X-1}-X^{n-m}\frac{X^m-1}{X-1}=\frac{X^{n-m}-1}{X-1}$

but even in the first case we don't have a simple way to explicitly find $s,t$ with $ns+mt=\gcd(n,m)$, even in the case that the right-hand side is $1.$ Furthermore, the claim that this $\gcd$ behaves appropriately depends on iterated application of facts such as:

Given (in some ring) that $\gcd(U,V)=\gcd(U,V')=1$ in the sense that there are $S,T,S',T'$ with $US+TV=1$ and $U'S'+T'V'=1$, it follows that $\gcd(U,VV')=1$ since $$U{\LARGE(}USS'+ST'V'+S'TV{\LARGE)}+VV'(TT')=1.$$

It is something I have asked about before, although not very clearly.

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104