Minimize $x$ in factorial division

91 Views Asked by At

My question is that how can we find the smallest natural number, $n$, such that some other number, $x$, divides $n!$. What I mean is that what minimum $n$ such that $x\mid n!$ for $x,n\in \mathbb N$.

My thoughts on this were that, we know that when we have divides, there exists some other variable, say $y$, then we have $y(n!) = x$. But how do we minimize the value of $x$?

1

There are 1 best solutions below

4
On

As I said in the comments, we have two cases where the result is clear. They are

  1. If $x=p$ is a prime number, then $n=p$;
  2. If $x=p_1\cdot\ldots\cdot p_n$ is the prime factorization of $x$ with $p_1<\ldots<p_n$, then $n=p_n$.

Now, for the general case, write $x=p_1^{e_1}\cdot\ldots\cdot p_n^{e_n}$ again with $p_1<\ldots<p_n$. Let $p$ and $e$ be the prime number and the exponent, respectively, such that $e\cdot p=\text{max}_i\; e_i\cdot p_i$. If $e<p$, we have that $((e-1)\cdot p)!$ does not divide $x$, because $p$ in the prime factorization of $((e-1)\cdot p)!$ appears only $(e-1)$ times, but we have that $(e\cdot p)!$ clearly, once $e\cdot p=\text{max}_i\; e_i\cdot p_i$. It is not difficult to see that no number $r$ such that $(e-1)p\leq r<ep$ will be such that $x\nmid r!$, because $p$ in $r!$ will not appear $e$ times. Hence, we conclude that $n=e\cdot p$. For example, if $x=25=5^2$, we have that $2\cdot 5=10=n$. If $e\geq p$, then things start getting complicated. Let's take a look at some simple cases.

Consider $p=2$. Below, at the first row, I have listed the first few multiples of $2$, and at the second row, the exponents of $2$ in the prime factorization of the corresponding multiple.

2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40
1,2,1,3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3

Now, let's do the same thing for $p=3$.

3,6,9,12,15,18,21,24,27,30,33,36,39,42,45,48,51,54,57,60
1,1,2, 1, 1, 2, 1, 1, 3, 1, 1, 2, 1, 1, 2, 1, 1, 3, 1, 1

If, for a fixed prime $p$, we call by $\{A_{p,i}\}_{i=1}^{\infty}$ the sequence of the exponents of $p$ appearing in the multiples of $p$, i.e., $A_{p,i}=\{\text{exponent of}\; p\;\text{in the prime factorization of}\; i\cdot p\}$, then, it is not difficult to see that

$$A_{p,k} =\begin{cases} 1, & \quad\text{if}\;k\neq0\,\text{mod}\,p \\ j, & \quad \text{if}\;k=0\,\text{mod}\,p^{j-1}\;\text{but}\;k\neq0\,\text{mod}\,p^{j} \end{cases}$$

For, $p=2$ and $p=3$, the first few terms of $A_{p,i}$ are at the second rows of the above sequences, respectively.

So, back to the question, if $e\geq p$, our $n$ must be such that $n!$ contains exactly (or, to be more precise at least) $e$ times the prime $p$ in its prime factorization. But, note that, if we take $n=e\cdot p$, then the prime $p$ will appear at least $e+1$ times at the prime factorization of $e\cdot p$. For our $n$ to be the least integer such that $x|n!$, we'll have to find the least $N$ such that

$$e\leq\sum_{i=1}^N A_{p,i}$$

and then, finally, our $n$ will be given by $n=N\cdot p$. I suggest you to analyze several cases with small primes such as $2,3,5$ and $7$.