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

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!

• Primality of $x$ plays no role. The factors $\,x,\,x-1,\,x-2,\ldots, 2\,$ are all smaller than the prime $y$ so coprime to it, hence so to is their product (by Euclid's Lemma) – Bill Dubuque Mar 3 at 3:16
• Note that this argument works for any integer $y$ whose least prime factor is $> x.\$ – Bill Dubuque Mar 3 at 3:27
• +1 for the concept of "foolproof full proof". – darij grinberg Mar 3 at 19:45

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.

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$$.