7
$\begingroup$

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!

$\endgroup$
  • 4
    $\begingroup$ 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) $\endgroup$ – Bill Dubuque Mar 3 at 3:16
  • 1
    $\begingroup$ Note that this argument works for any integer $y$ whose least prime factor is $> x.\ $ $\endgroup$ – Bill Dubuque Mar 3 at 3:27
  • 1
    $\begingroup$ +1 for the concept of "foolproof full proof". $\endgroup$ – darij grinberg Mar 3 at 19:45
6
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.