Let $\Phi_n$ be the $n$'th cyclotomic polynomial, and put \begin{align*} a_n &= \Phi_n(1) \\ b_n &= \gcd\left(\left(\begin{array}{c} n \\ 1\end{array}\right),\dotsc,\left(\begin{array}{c} n \\ n1\end{array}\right)\right) \\ c_n &= \begin{cases} p & \text{ if } n = p^k \text{ for some prime } p \text{ and } k>0 \\ 1 & \text{ otherwise. } \end{cases} \end{align*} It is wellknown that $a_n=b_n=c_n$. Indeed, there are a bunch of ways to prove that $a_n=c_n$, and a bunch of ways to prove that $b_n=c_n$. I ask: is there a more direct proof that $a_n=b_n$? A good answer might give a tidier approach to some fundamental results in formal group theory. Ideally I'd like a proof that expresses $a_n$ as a $\mathbb{Z}$linear combination of binomial coefficients as in $b_n$.

$\begingroup$ What you write requires $n > 1$. At $n = 1$ it breaks down, since $\Phi_1(1) = 0$ and $b_0$ is not really defined. $\endgroup$ – KConrad May 22 '14 at 21:58

3$\begingroup$ This reminds me of the fact that when $f(x) = \sum_{k =0}^n d_k\binom{x}{k}$ with integers $d_k$, we have $\gcd(d_0,d_1,\dots,d_n) = \gcd_{m \in \mathbf Z} f(m)$. $\endgroup$ – KConrad May 22 '14 at 22:00

9$\begingroup$ <troll> In the divisibility poset $0$ is maximal, so surely it's appropriate to say it's the greatest common divisor of an empty set? </troll> $\endgroup$ – Tom Lovering May 23 '14 at 0:44

2$\begingroup$ Every proof that I tried goes through $c_n$... $\endgroup$ – i707107 May 23 '14 at 0:58

$\begingroup$ Your `ideal' situation provides only $b_n\mid a_n$. Is it enough for you? $\endgroup$ – Ilya Bogdanov May 23 '14 at 12:56
Define $a_n=\Phi_n(1)$ 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}^na_k^{\lfloor n/k\rfloor}$$ and $$\binom{n}{m}=\frac{n!}{m!(nm)!}=\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 (nm)/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}{n1}{\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_{i1},\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_{nm}]!},$$ and deduce that $\gcd\left( {n \brack 1},{n \brack 2},\cdots,{n \brack {n1}}\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 $A_n=\prod_{d\mid n}I_n^{\mu(n/d)}$ where $\mu$ is the classic Mobius function.)
A familiar and obvious choice with (**) is $I_n=1+X+\cdots+X^{n1}.$ 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
 $I_n=n$ in $\mathbb{N}$
 The Fibonacci numbers $F_n$ in $\mathbb{N}$
 $I_n=u^nv^n$ in $\mathbb{Z}[u,v]$
 $I_n=\frac{u^nv^n}{uv}=\Sigma_{k=0}^{n1}u^{nk1}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_{nm}]!}=\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 {n1}}\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
 $1n1m=nm$
 $ F_{m+1}F_nF_{n+1}F_m = F_{nm}$
 $1\frac{X^n1}{X1}X^{nm}\frac{X^m1}{X1}=\frac{X^{nm}1}{X1}$
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 righthand 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.

1$\begingroup$ Very interesting! Has anyone considered a qanalog of the Lazard ring / universal formal group? $\endgroup$ – მამუკა ჯიბლაძე May 25 '14 at 7:18

3$\begingroup$ Your "obvious choice" $I_n = 1 + X + X^2 + \cdots + X^{n1}$ is wrong if it is to be the product of $d$th cyclotomic polynomials for *all* $d$ dividing $n$. For that you need $I_n = X^n  1$. $\endgroup$ – KConrad May 25 '14 at 7:46

$\begingroup$ I changed things and made more explicit note of this. $\endgroup$ – Aaron Meyerowitz May 27 '14 at 9:11

$\begingroup$ Your commutative ring should be an integral domain, I assume? $\endgroup$ – darij grinberg May 27 '14 at 10:41

3$\begingroup$ Nice construction! As far as I remember, some answers about when cyclotomic polynomials have a gcd in the strong sense in $\mathbb{Z}\left[X\right]$ can be found in G. Dresden, Resultants of Cyclotomic Polynomials, home.wlu.edu/~dresdeng/papers/Res.pdf . $\endgroup$ – darij grinberg May 27 '14 at 10:47
Inspired by the previous answer I am thinking about simplest possible ways to prove $$ gcd\left(\binom n1_q,...,\binom n{n1}_q\right)=\Phi_n(q). $$ One most primitive way to do it is to check that both sides have the same roots. On the left, multiplicity of a primitive root of unity of degree $k$ is $$ \min\left\{\left[\frac nk\right]\left[\frac mk\right]\left[\frac{nm}k\right]\ \ m=1,...,n1\right\} $$ and it must not be difficult to show that this is 0 for $k\ne n$ and 1 for $k=n$.

2$\begingroup$ For $k>n$, its obviously zero and for $k=n$, its obviously $1$. For $k<n$, take $m=k$ to get $0$. $\endgroup$ – David E Speyer May 29 '14 at 16:03

$\begingroup$ Right, thanks. Except it is somehow not totally clear to me whether this after all answers the original question... $\endgroup$ – მამუკა ჯიბლაძე May 29 '14 at 16:05
This answer seemed to be a simplification of arguments given by Aaron Meyerowitz.
As it was mentioned numbers $a_n=\Phi_n(1)$ are uniquely determined by $$n=\prod_{d \mid n}a_d.$$ So it is sufficient to check that numbers $c_n$ satisfy the same equation. But $c_n=e^{\Lambda(n)}$, where $$\Lambda(n)=\begin{cases} \log p & \text{ if }n = p^k, \\ 0 & \text{otherwise}, \end{cases}$$ and verification of identity $n=\prod_{d \mid n}c_d$ is an easy exercise.
We can express $a_n$ as a $\mathbb{Z}$linear combination of binomial coefficients as in $b_n$ in the following way (this construction is taken from the paper Coefficient rings of formal groups).
If $n=p^k$ then $\binom{n}{p^{k1}}\equiv p\pmod{p^2},$ so we can easely find $\lambda_{p^{k1}}$ such that $\lambda_{p^{k1}}\binom{p^k}{p^{k1}}\equiv p\pmod {p^{k}}$. So for some $\lambda_{1}$ $$\lambda_{p^{k1}}\binom{p^k}{p^{k1}}+\lambda_{1}\binom{p^k}{1}=p.$$
Now let $n=p_1^{k_1}\ldots p_s^{k_s}$, where $s>1$. Then by Kummer's theorem $\mathrm{ord}_{p_i}\binom{n}{p_i^{k_i}}=0$ and $\mathrm{ord}_{p_j}\binom{n}{p_i^{k_i}}\ge k_j$ ($j\ne i$). Taking $\lambda_{p_i^{k_i}}\equiv \binom{n}{p_i^{k_i}}^{1}\pmod{p_i^{k_i}}$ we'll have $$\lambda_{p_1^{k_1}}\binom{n}{p_1^{k_1}}+\ldots+\lambda_{p_s^{k_s}}\binom{n}{p_s^{k_s}}\equiv 1\pmod n.$$ So for some $\lambda_1$ $$\lambda_{p_1^{k_1}}\binom{n}{p_1^{k_1}}+\ldots+\lambda_{p_s^{k_s}}\binom{n}{p_s^{k_s}}+\lambda_{1}\binom{n}{1}=1.$$

1$\begingroup$ This does not mention the numbers $b_n$, and so does not answer the question as asked. $\endgroup$ – Neil Strickland Oct 19 '15 at 7:55

$\begingroup$ $b_n=c_n$ by Kummer's theorem en.wikipedia.org/wiki/Kummer%27s_theorem $\endgroup$ – Alexey Ustinov Oct 19 '15 at 7:59

$\begingroup$ Yes, the question says that there are many known proofs that $a_n=c_n$ and that $b_n=c_n$. $\endgroup$ – Neil Strickland Oct 19 '15 at 8:01

1$\begingroup$ Both proofs are almost in one line. It is strange that you insist on simpler arguments. What is hinder you to use these arguments? $\endgroup$ – Alexey Ustinov Oct 19 '15 at 8:20

4$\begingroup$ I did not ask for a simpler proof, I asked for a more direct one. "More direct" means that it should be formulated in terms of the algebra of roots of unity and the combinatorics of subsets of $\{1,\dotsc,n\}$. $\endgroup$ – Neil Strickland Oct 19 '15 at 8:25