Let $x$ be a positive integer and $y$ a prime such that $x \lt y$. Prove that the $\operatorname {gcd}(x!,y)=1$.

Question

Let $x$ be a positive integer and $y$ a prime such that $x \lt y$. Prove that $\operatorname{gcd}(x!,y)=1$.

Having a hard time answering this question, every proof I come up with does not leave me satisfied has a foolproof full proof. Anyways, I'll start with what I have right now.

Let $x$ be a positive integer such that $x > 1$. Let $y$ be a prime such that $y > x$.

Then, $x$ is either prime or not prime. In case it's prime, clearly $gcd(x,y)=1$. Since $x! = x*(x-1)...1$ and $ x \ge (x-1) \ge (x-2) ... \ge 1$. So each factor of the factorial is smaller than $y$ and has no common factor with it (for $y$ is prime). Hence, $x!$ has no common divisors with $y$ besides 1, from which follows $gcd(x!,y)=1$.

Assuming $x$ to be not prime. By the Fundamental Theorem of Arithmetic, $x$ can be written as a product of primes $\mathrm{p_1}^{a_1}$ $\mathrm{p_2}^{a_2}$...$\mathrm{p_n}^{a_n}$. We know that any $\mathrm{p_i}^{a_i} \le y$ thus having no common factors with $y$ annd $gcd(x,y)=1$. This having been asserted, by similar reasoning to above it follows $gcd(x!,y)=1$

I'm definitely not satisfied with this because I don't really feel that strong a connection between the premisses and the conclusion. Having said that, I'm also a beginner and have wrapped my head around this for a while and feel a bit lost in it all. Gladly looking for help in this. Thank you!

Answer 1

If $y$ is prime and $y|x!$, then $y$ divides some factor in the product $1 \cdot 2 \cdot 3 \cdots (x-1) \cdot x$, which can’t happen because $y \gt x \Rightarrow y$ is greater than each of those factors.

Answer 2

The fastest way to do this is:

$y$ is prime. Its only factors are $1$ and $y$. So $\gcd(n,y) = 1$ or $y$ (and $\gcd(n,y) = y \iff y|n$). By Euclid's lemma, if $\gcd(x!,y) = y$ and $y$ is prime then $y|k$ for some $k \le x < y$. But that's impossible as $k < y$. So $\gcd(x!, y) =1$.

But probably the more useful and of future benefit is to prove the following lemma:

Lemma: if $\gcd(a,n) = 1$ and $\gcd(b,n) = 1$ then $\gcd(ab, n) = 1$.

Pf: For any prime $p|ab$ either $p|a$ or $p|b$ but as $\gcd(a,n) =1$ and $\gcd(b,n) =1$ we can not have $p|n$. So $ab$ and $n$ have no prime factors in common and are therefore relatively prime.

(... or this is a consequence of $\gcd(ab,n) = \text{lcm}(\gcd(a,n),\gcd(b,n))$ ... which is straightforward enough but not as trivial to prove...)

Corrollary. By induction if $\gcd(a_i,n) = 1$ then $\gcd(\prod a_i, n) = 1$.

Corrollary. If $p$ is prime then $\gcd(a,p) = 1$ for all $a < p$ so for any $k < p$ then $\gcd(k!, p) =1$.