A proof that Gaussian binomial coefficients are integers Recall that the Gaussian binomial coefficients are defined as
$$\binom{m}{n}_q= \dfrac{(q^m-1)(q^m-q)\cdot\ldots\cdot(q^m-q^{n-1})}{(q^n-1)(q^n-q)\cdot\ldots\cdot(q^n-q^{n-1})}.$$
In this post, is explained how to prove that those coefficients are integers using induction.
However, in a question of a French written competitive examination, it is suggested to prove it first when $q=p^i$ is the power of a prime. And then extend the result to any $q$ integer.
I'm able to prove that if $q=p^i$, $$\binom{m}{n}_q$$ is the number of linear subspaces of dimension $n$ in the linear space $\mathbb F_q^m$ where $\mathbb F_{q}$ stands for the finite field of cardinality $q$. $\binom{m}{n}_q$ is, therefore, an integer in that case. But I'm not able to generalize the result for $q$ integer. The fundamental theorem of arithmetic should be at play as well as a way to factor $(r^m s^m -r^j s^j)$.
Any idea?
 A: More generally:

Lemma: If $N(x),D(x)\in \mathbb Z[x]$ with $D$ monic, and $D(q)\mid N(q)$ for infinitely many $q\in \mathbb Z,$ then $D(x)\mid N(x).$

In your case, $N$ and $D$ are the numerator and denominator, respectively.
Proof: Since the $D(x)$ is monic, we can do integer polynomial division and get:
$$N(x)=D(x)Q(x)+R(x)\quad \deg R<\deg D\tag 1$$
with $Q(x),R(x)\in\mathbb Z[x].$
We will show that $R(x)$ is the zero polynomial, by showing that $R(q)=0$ for infinitely many $q\in\mathbb Z.$
For the $q$ such that $D(q)\mid N(q),$ (1) means $D(q)\mid R(q).$
Since $\deg R<\deg D,$ we know there is some $N$ such that if $|q|>N,$ $|R(q)|<|D(q)|.$
But if $|R(q)|<|D(q)|,$ and $D(q)\mid R(q),$ this means $R(q)=0.$
But the assumption that $D(q)\mid N(q)$ for infinitely many $q$  means we have infinitely many such $q$ with $|q|>N,$ and thus infield many $q$ so that $R(q)=0.$
This means $R(x)=0,$ which means $D(x)\mid N(x).$

It’s easy to come up with counterexamples to our lemma with $D$ not monic, like $N(x)=x,D(x)=2.$ Then $D(q)\mid N(q)$ for infinitely many $q\in\mathbb Z,$ but not for all $q,$ and certainly $D(x)\not\mid N(x)$ as integer polynomials.
I haven’t come up with a counterexample with a non-constant denominator, assuming $D$ and $N$ are relatively prime. I don’t think there is a counterexample with $D(x)=2x+1.$
If there is an $N(x)$ for $D(x)=2x+1,$ you can replace $N(x)$ with $N_k(x)=2^kN(x)$ and get exactly the same $q$ such that $2q+1\mid N(x)\iff 2q+1\mid N_k(x).$ But then for $k=\deg N,$ $N_k(x)=P(2x)$ for some integer polynomial $P.$ Then $q+1\mid P(q)$ for infinitely many $q,$ and since $x+1$ is monic, this means, from the Lemma, $x+1\mid P(x)$ and hence, for any $q,$ $2q+1\mid P(2q)=2^kN(q)$ which implies $2q+1\mid N(q)$ for all $q.$
I think the same proof disallows a counterexample for $D(x)=ax+b$ where $\gcd(a,b)=1.$ Then $N_k(x)=a^kN(x).$
You get the same equivalence between $N_k$ and $N$ because $\gcd(aq+b,a^k)=1.$

A more direct proof of the original question uses the factorization:
$$x^r-1=\prod_{d\mid r} \Phi_d(x)$$
where $\Phi_d,$ the cyclotomic polynomials, are integer polynomials and irreducible.
Cancelling out common $q,$ you get your numerator and denominator:
$$N(x)=\prod_{k=m-n+1}^m\left(x^k-1\right)\\D(x)=\prod_{k=1}^n\left(x^k-1\right)$$
Letting $S_n=\{1,\dots,n\}$ and $S_{m,n}=\{m-n+1,\dots,m\}$ So we need to show, for each $d:$
$$\left|\{k\in S_n: d\mid k\}\right|\leq \left|\{k\in S_{m,n}: d\mid k\}\right|\tag{1}$$
This can be seen as “the number of times $\Phi_d$ occurs in the denominator is $\leq$ the number of times $\phi_d$ occurs in the numerator.
Alternatively, (1) can be written as “the number of multiples of $d$ in $n$ consecutive integers is minimized by the case $1,2,\dots,n.$”
That can be proven directly. Basically, there are $\left\lfloor \frac nd\right\rfloor$ multiples of $d$ in $\{1,2,\cdots,n\}$ and you can show there are at least that many in $s+1,\dots,s+n$ for any integer $s.$
It turns out $\Phi_d(x)$ can only end up in the quotient at most once, when the inequality $(1)$ is strict. So this gives us an “explicit” quotient:
$${\binom mn}_q=\prod_d \Phi_d(q)$$ where $d$ runs through all positive integers where $(1)$ is a strict inequality.
This can be rewritten as:
$${\binom mn}_q=\prod_{\substack{d\\(m\bmod d)+\\(n\bmod d)\geq d}} \Phi_d(q)$$
