1
$\begingroup$

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$

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

2 Answers 2

2
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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.

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

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.