# How to prove that gcd(k! mod m, m) > 1, for every k > $\alpha$

I'm doing some exercises and I've read that, if $\alpha$ is the first prime factor of a number $m \geq 2$, then, for every $k \geq \alpha$, it is true that $gcd(k!\ mod\ m,\ m) > 1$.

I can see that $gcd(k!,\ m) > 1$ is true because $k!$ contains $\alpha$ as one of its factors, but I can't see where that mod m fits in.

• Is $n$ and $m$ the same? – Hagen von Eitzen Apr 9 '14 at 21:35
• Yes, I mistyped it, editing now – Ivan Apr 9 '14 at 21:36

By the division algorithm, $k!=qm+r$ for $q,r\in\mathbb{Z}$ with $0\le r<m$. Since $\alpha|k!$ and $\alpha|qm$, we must have that $\alpha|r$, and hence $\textrm{gcd}(k!\mod m,m)=\textrm{gcd}(r,m)>1$.
By Euclid $\ \gcd(k!\ {\rm mod}\ m,\, m) = \gcd(k!,m),\,$ and $\ \alpha\mid k!,\,m\,\Rightarrow\,\alpha\mid\gcd(k!,m)$