# prove that $N$ is divisible by $1,2,\ldots,k$ which $k+1$ is the lowest prime number after $N$

Suppose $n$ is a natural number ($n\ge 5$) and $k+1$ is the lowest prime number that is greater than $n$ prove that $A_i \mid n!$ which $A_i$ are these numbers: $1,2,\ldots,k$

• Is this homework? Jun 3, 2014 at 6:04
• No I'm studying for my exam, i was solving some questions and i saw this one...
– ReZa
Jun 3, 2014 at 6:05

The statement is obvious for $A_i\leq n$. By Bertrand's postulate, $n<A_i\leq k<2n$.

Suppose that $A_i$ doesn't divide $n!$. Let's assume also that $A_i$ is the minimum with this property. Then there exists a prime $p$ and some $\alpha\geq 1$ such that $p^\alpha|A_i$ and $p^\alpha$ doesn't divide $n!$. In fact, $A_i=p^\alpha$.
Indeed, if $A_i$ has other prime factor, say $A_i=mp^\alpha$, then $(m-1)p^\alpha$ divides $n!$ since $A_i$ is the minimum that doesn't. But this is a contradiction since $p^\alpha$ doesn't divide $n!$.

But $p^{\alpha-1}=p^\alpha/p\leq A_i/2<n$, so $n!$ is a multiple of $p^\beta$, where $$\beta=\sum_{r=1}^{\alpha-1} r$$ that is $$\beta=\frac{\alpha(\alpha-1)}2$$

But it must be $\alpha-1\leq\beta<\alpha$, that is, $\beta=\alpha-1$ and $\alpha=2$. (Note that $\alpha>1$ because $A_i$ is composite).

Again by the minimality of $A_i$, if $p\neq 2$, $2p$ divides $n!$ and $p^{\beta+1}=A_i$ divides $n!$ and we arrive at a contradiction. If $p=2$ then $A_i=4$, which contradicts $n\geq 5$.

Hint: $Ai\mid n!, 1\le A_i \le n$ is obvious. Since the next prime is $k+1$, it is obvious that all numbers from $n+1$ to $k$ are composite and have factors less than n, i.e. $A_i = A_jA_k, 1\le j, k \lt i, \forall (n+1)\le A_i\le k$ Also, $n! = 1\cdot2\cdot3\cdots A_j\cdots A_kc\cdots n$, which clearly shows what is required. For numbers that are powers of other numbers, we can use Bertrand's Postualte.

• if one factor is ${A_j}^a$ we know that $A_j | n!$ but how do you say ${A_j}^a | n!$ ?
– ReZa
Jun 3, 2014 at 6:12
• One can use the Bertrand Postulate to fill in the gap. There is undoubtedly a more elementary way. Jun 3, 2014 at 6:17
• No, I'm just factoring $A_i$ into two factors $A_j$ and $A_k$. Jun 3, 2014 at 6:18