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!(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 $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^{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
- $I_n=n$ in $\mathbb{N}$
- The Fibonacci numbers $F_n$ in $\mathbb{N}$
- $I_n=u^n-v^n$ in $\mathbb{Z}[u,v]$
- $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.
Let's use the notation $\{ x\}$ for the fractional part of a number $x$.
Assume $u, v$, and $u/v$ are all irrational.
Then, $\{un\}$ and $\{vn\}$ behave as independent uniform random variables. (This is proved by Fourier analysis, vindicating James Cranch's suggestion) $s_{n+1}-s_n$ depends on $\{un\}$ and $\{vn\}$:
It is $\lfloor u \rfloor + \lfloor v \rfloor$ if $\{un\} < 1- \{u\}$ and $\{vn\} < 1 - \{v\}$
$\lceil u \rceil + \lceil v \rceil$ if $\{un\} \geq 1- \{u\}$ and $\{vn \} \geq 1- \{ v\}$
and the integer intermediate between those two otherwise.
So by measuring the frequencies with which these $s_{n+1}-s_n$ takes its maximal value, its minimal value, or the intermediate one, we can determine $\{u\} \{v\}$ and $(1-\{u\})(1-\{v\})$, hence by solving the equation $\{u\}$ and $\{v\}$. Then clearly how we distribute the integer part between $u$ and $v$ does not affect $\lfloor un \rfloor + \lfloor vn \rfloor$, so we can choose any values of $u$ and $v$ with the correct fractional part and sum and plug them in to see if they fit our sequence.
In fact the same thing works if just $u/v$ is irrational, because they are independent non-uniform random variables, and the probability that $\{un\}$ and $\{vn\}$ is in the range to increase by a larger amount is still $\{u\}$ or $\{v\}$ just because the average increase of $\lfloor un\rfloor$ or $\lfloor vn \rfloor$ must be $u$ and $v$ respectively.
Does this still work even if the ratio $u/v$ is rational?
Best Answer
I will give a complete answer when $1,1/r$ and $1/s$ are linearly independent over $\mathbb Q$ and a recipe to compute your $t$ otherwise. First of all, notice that $n$ lies in a Beatty sequence $\lfloor m\alpha\rfloor$, where $\alpha>1$ if and only if $\{n/\alpha\}>1-\frac{1}{\alpha}$. Indeed, if $n=\lfloor m\alpha \rfloor$, then $$ \frac{n}{\alpha}=\frac{m\alpha-\{m\alpha\}}{\alpha}=m-\frac{\{m\alpha\}}{\alpha}, \text{ so }\{n/\alpha\}>1-\frac{1}{\alpha}. $$ On the other hand, if $\{n/\alpha\}>1-\frac{1}{\alpha}$, then one can set $m=\lfloor n/\alpha \rfloor+1=n/\alpha+1-\{n/\alpha\}$ and get $$ m\alpha=n+\alpha\left(1-\{n/\alpha\}\right), $$ so $\lfloor m\alpha \rfloor=n$, as needed. Now, Case 1: $1,1/r$ and $1/s$ are linearly independent over $\mathbb Q$. In this case, it is known (say, by Weyl's criterion), that the points $$ t_n=(n/r \mod 1, n/s \mod 1)\in \mathbb R^2 \diagup \mathbb Z^2 $$ are uniformly distributed on the torus. This means that for $N\to +\infty$ the proportion of $n\leq N$ with $$ \{n/r\}>1-\frac{1}{r}\text{ and }\{n/s\}>1-\frac{1}{s} $$ is equal to the measure of the set $(x,y) \in \mathbb R^2\diagup \mathbb Z^2$ with $x>1-\frac{1}{r}, y>1-\frac{1}{s}$, hence the inverse $t$ of this limiting proportion is equal to $rs$. For example, for $\pi$ and $e$ we get $\pi e\approx 8.5397$ and for $\sqrt{3}$ and $\sqrt{5}$ we get $\sqrt{15}\approx 3.873$.
Case 1.5 is when both $r$ and $s$ are rational. In this case, your problem reduces to enumeration of certain congruence classes $\mod \mathrm{num}(r)\mathrm{num}(s)$.
Finally, Case 2 is when $1/r$ is irrational, but for some $a,p,q\in \mathbb Z$ we have $1/s=p/q\cdot1/r+a/q$. Without loss of generality one can assume that $p,q>0$, $a\geq 0$. Next, let us divide $\mathbb N$ into congruence classes $\mod q$ and evaluate the (relative) density $\delta_b$ of all $n\equiv b\pmod q$ such that $$ \{n/r\}>1-\frac{1}{r}\text{ and }\{n/s\}>1-\frac{1}{s}. $$ In this case, the answer would be $$ t=\frac{q}{\delta_0+\delta_1+\ldots+\delta_{q-1}}. $$ Fix $b$. The congruence $n\equiv b\pmod q$ means that $n=qm+b$. Now, we need $$ \{qm/r+b/r\}>1-\frac{1}{r}\text{ and }\{pm/r+b/s\}>1-1/s. $$ Since $1/r$ is irrational, $\{m/r\}$ is equidistributed $\mod 1$. This means that our relative density $\delta_b$ is equal to the measure of all $x\in [0,1]$ such that $$ \{qx+b/r\}>1-\frac{1}{r}\text{ and }\{px+b/s\}>1-1/s. $$ (By relative density I mean the density of corresponding $n$ in the residue class, i.e. the actual density of your $n$ with $n\equiv b\pmod q$ is $\delta_b/q$)