Let $n$ be an integer greater than $6$.Show that if $n+1$ is a prime number,than $\left\lceil \frac{(n-1)!}{n(n+1)}\right \rceil$ is $ODD.$
Problem
Source: Thailand MO 2015
Tags: number theory
bobthesmartypants
28.05.2016 19:42
It's false? Try $n=10$ and you get $3298$ which is even.
trungnghia215
28.05.2016 20:30
It's also false for $n = 12$, i suppose you mean it's even. Then the statement is true not only $n + 1 > 7$ but also $n = 6$.
For convenient, substitute $n + 1$ by $p$ is a prime number which is greater than $7$. And i claim that $\left\lfloor \frac{(p - 2)!}{p(p - 1)}\right\rfloor$ is even.
Quote:
Lemma 1. $(p - 2)! \equiv 1\pmod{p}$
Quote:
Lemma 2. Let $n$ be composite number greater than $4$ then $n\mid (n - 1)!$
Quote:
Lemma 3. For prime number $n + 1$, then $\frac{(n - 1)!}{n}$ is even
ProofIt's equivalent to $v_{2}((n - 1)!) > v_{2}(n)$. Note that $n$ is even, setting $n = 2^{u}.v$ where $v$ is odd number
According to Legendre's formula, we get $v_{2}((n - 1)!) \ge \left\lfloor\frac{n - 1}{2}\right\rfloor = 2^{u - 1}v - 1 \ge 2^{u - 1} - 1 \ge u$ is true forall $u \ge 3$.
So we just consider the case $u = 2$ and $u = 1$, note that $v$ cannot be equal to $1$, then the lemma is true.
According to lemma 2, $p - 1\mid (p - 2)!$ since $p - 1$ is composite number.
From the lemma 1, easily we get that $\frac{(p - 2)!}{p - 1} \equiv -1\pmod{p}$
Thus, $\left\lfloor \frac{(p - 2)!}{p(p - 1)}\right\rfloor = \frac{\dfrac{(p - 2)!}{p - 1} + 1}{p} - 1$
Note that $\frac{(p - 2)!}{p - 1}$ is even, then $\frac{\dfrac{(p - 2)!}{p - 1} + 1}{p} - 1$ is even.
We're done. $\bigstar$
AMN300
28.05.2016 22:25
this is part of 2004 APMO 4, if you replace $\lfloor \frac{(n-1)!}{n(n+1)} \rfloor$ being odd with being even instead
abk2015
28.05.2016 22:58
$\LaTeX$ tip: Note that using:$\left\lfloor \frac{(n-1)!}{n(n+1)}\right \rfloor$ yields $\left\lfloor \frac{(n-1)!}{n(n+1)}\right \rfloor$ which looks better.
v_Enhance
29.05.2016 00:48
Ferid.---. wrote: Let $n$ be an integer greater than $6$.Show that if $n+1$ is a prime number,than $\lfloor \frac{(n-1)!}{n(n+1)} \rfloor$ is odd. It is in fact even for every $n \ge 1$. This is APMO 2004/4, as mentioned above.
Ferid.---.
30.05.2016 21:47
$\boxed{SOLUTION}$ Suppose that $n+1=p$ Then $p-1$ is composite number and $p\geq 7.$Write $p-1=ab$ where $1<a,b<p-2.$ We first show that $(p-1)\mid (p-2)!$ This is clear when $a\not= b$ If $a=b$,then $a=\sqrt{p-1}$ since $p\geq 7$, $0<(p-1)(p-5)=p^2-6p+5$ and hence $4(p-1)<(p-1)^2$. So $2a=2\sqrt{p-1}<p-1$ and thus $a\geq \frac{p-2}{2}<p-2$ So $a^2\mid (p-2)!$ and hence $(p-1)\mid (p-2)!$ Therefore $(p-2)!=kp-1$ for some integer $k.$We show that $k$ is even.Since $p\ge 7$ the set $\{1,2,...,p-2\}$ contain at least two even numbers.Let $l$ be the largest integer such that $2^l\mid (p-1).$There the set $\{1,2,...,(p-2)\}\ \{2^l,\frac{p-1}{2^l}\}$ contains at least by $Wilson's$ theorem.Thus there in an integer m such that $k=mp-1$ since $k$ is even and $m$ is odd.Therefore $\frac{(n-1)!}{n(n+1)}=\frac{(p-1)!}{(p-1)^2p}=\frac{k}{p}=\frac{mp-1}{p}=m-\frac{1}{p}$ $\lceil \frac{(n-1)!}{n(n+1)}\rceil =m$ is odd.