Show that for $n!/2 - p$, $p$ is the least prime factor if $n > p$

Question

Apparently this isn't clear, so here are some examples:

$$3!/2 - 3$$ $$4!/2 - 3$$ $$5!/2 - 3$$

and $$5!/2 - 5$$ $$6!/2 - 5$$ ...

How would I go about proving this?

I found it from a matrix I generated from looking at error functions.

Answer 1

This is true for all odd $p$, even when $p$ is not a prime. Since $p$ divides $p$ we only have to show that $p$ divides $\frac{n!}{2}$. Since $p <n$, $p$ appears as a factor in $n!$, and is still a factor in $\frac{n!}{2}$ since $p$ is odd (and not canceled by the $2$ ). This may not be true in general if $p$ is even, since $\frac{3!}{2}-2=1$.

---

Regarding your last statement:

$\frac{p!}{2}-p$ is never a prime

This should not come as a huge surprise, since $$\frac{p!}{2}+p=p\left (\frac{(p-1)!}{2}+1\right )$$ This is valid whenever $2$ divides $(p-1)!$, which happens as long as $p\geq 3$.

Answer 2

Let $p,q$ be primes and $n>p>q$. In particular $n\ge $, $p\ge 3$. Then the integer $\frac{n!}2-p$ is a multiple of $p$ because $n!$ is and $p$ is odd.

But $\frac{n!}2-p$ not a multiple of $q$. This is clear for odd $q$ because $n!$ (and so also $\frac{n!}2$) is divisible by $q$ and $p$ is not. For even $q$, note that $n>p>q$ implies $n\ge 4$, so $\frac {n!}2$ is still even (and $p$ is not).

Answer 3

It's a simple matter of remembering what $n!$ is. Namely, given sufficiently large $n$, we have $n! = 1 \times 2 \times 3 \times \ldots \times (n - 1) \times n$. So, given an odd prime $p < n$, $\frac{n!}{2}$ is also divisible by $p$. It's also divisible by other odd primes less than $p$, since $\frac{n!}{2} = 3 \times \ldots \times (n - 1) \times n$.

Then obviously $$\gcd\left(n!, \frac{n!}{2}\right) = \frac{n!}{2}.$$ But $$\gcd\left(n!, \frac{n!}{2} - p\right) = p.$$ This tells us that $\frac{n!}{2} - p$ is not divisible by any primes less than $p$, because $p$ is not divisible by those primes either.

For example, given $p = 7$, we have $8! = 40320$. Half of that is 20160, which is divisible by 7, since indeed $7 \times 2880 = 20160$. But it's also divisible by 3 and 5.

However, subtract 7 from 20160 and we get 20153, which is also divisible by 7, but it's obviously not divisible by 5, and not divisible by 3 either. In fact, $7 \times 2879 = 20153$.

Answer 4

The statement is not true for $p=2$ and $n=3$

If $p$ is an odd prime and $n\ge p$ then $$p|( n!/2)$$ and $$p|p$$ thus $$p|(n!/2-p)$$

On the other hand if $$1<k<p\le n$$ then $$ k| ( n!/2) $$ but $k$ does not divide $p$

Thus $k$ does not divide $(n!/2-p)$ , that is $$n!/2-p$$ first divides $p$

Answer 5

Um,......

$\frac {n!}2 = 3\cdot..... \dot n$ and if $2 < p < n$ then $p$ is a factor of $\frac{n!}2$. And so $\frac {n!}2 = p*K$ for some $K$ and $\frac{n!}2 - p = p(K -1)$.

This can only fail if $p > n$ or is $p=2$ and $n <4$. (i.e. $p =2$ and $n=3$)

====

Oh, I missed the "first divisible" by $p$. Well, since for all $k < p$ then $k|\frac {n!}2$ and $p$ is primes so $k\not \mid p$ so $k \not \mid \frac {n!}2 -p$.

This is the only nescessity that $p$ be prime. If $p= mk$ is not prime then $m,k|\frac {n!}2$ and $m,k|p$ so the term will not be first divisible by $p$ unless $p$ is prime.

Answer 6

So by "first divisible" what you mean is what would more commonly be phrased as "$p$ is the least prime factor."

Clearly $p$ is not the least prime factor of $n!$ if $p > 2$, since $n!$ is divisible by $2$. Nor is it the least prime factor of $n!/2$ if $p \geq 5$ because $n!/2$ is sure to be divisible by $2$ and by $3$.

By subtracting any prime factor of $n!$ from $n!/2$, you obtain a number that is divisible by that prime but not by any of other primes

Answer 7

Not that this question requires any more answers, I figured I would practice writing cancellations in TeX.

Okay, given $n > 5$, $n! = 2 \times 3 \times 4 \times \ldots \times n$. So far nothing you didn't already know, nothing you haven't already been told. Then

$$\require{cancel} \frac{n!}{2} = \frac{\cancel{2} \times 3 \times 4 \times \ldots \times n}{\cancel{2}} = 3 \times 4 \times \ldots \times n.$$

If $p$ is some prime greater than $3$ but less than $n$, that means it appears somewhere in those continuation dots. So then $$\frac{n!}{2} = p \times \frac{3 \times 4 \times \ldots \times \cancel{p} \times \ldots \times n}{\cancel{p}}$$ and therefore $$\frac{n!}{2} - p = p \times \left(\frac{3 \times 4 \times \ldots \times \cancel{p} \times \ldots \times n}{\cancel{p}} - 1 \right).$$ Clearly $$\gcd \left( \frac{3 \times 4 \times \ldots \times \cancel{p} \times \ldots \times n}{\cancel{p}}, \frac{3 \times 4 \times \ldots \times \cancel{p} \times \ldots \times n}{\cancel{p}} - 1 \right) = 1$$ and consequently $$\gcd \left( \frac{n!}{2}, \frac{n!}{2} - p \right) = p$$ and $$\textrm{lpf} \left( \frac{n!}{2} - p \right) = p.$$