5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ First of all, $p$ is didisible by $p$, so we only have to check whether $\frac{n!}{2}$ is divisible by $p$ $\endgroup$ – Peter Apr 5 '18 at 17:59
  • $\begingroup$ If $p$ is an odd prime, the smallest number doing the job is $n=p$. For $p=2$, we need $n=4$ $\endgroup$ – Peter Apr 5 '18 at 18:00
  • $\begingroup$ This isn't true. Take $n=3$ and $p=2$. $\endgroup$ – Joe Apr 5 '18 at 18:00
  • 1
    $\begingroup$ "This also seems to be true for values of n that are not prime, actually." How can it be? No number $a$ is first divisible by a composite number $b$, as $a$ would then also be divisible by each of the prime factors of $b$. $\endgroup$ – Arthur Apr 5 '18 at 18:01
  • 1
    $\begingroup$ Well if $p<n$ then $n! = 1*2*3.....*(p-1)*p*.....*n$ is divisible by $p$. And if $p$ isn't $2$ then $n!/2$ is divisible by $p$ so $p $ factors out of $\frac {n!}2 - p = p(\frac {n!}{2p} - 1)$. $p$ doesn't have to be prime. And if $n \ge 4$ then $p$ can be equal $2$. The only exception is $p=2$ and $n=3$ and otherwise it has nothing to do with primes. $\endgroup$ – fleablood Apr 5 '18 at 18:33
6
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ Nice Tex, my dude. upvoted $\endgroup$ – Robbie Apr 5 '18 at 22:58
  • 4
    $\begingroup$ Thanks. Just a little heads up: you need to have \require{cancel} before being able to use \cancel{x} here on Math.SE. It's a little different on your own TeX document on your local computer. $\endgroup$ – Mr. Brooks Apr 5 '18 at 23:08
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

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