3
$\begingroup$

What is the highest power of n in $(n^r-1)!$ where $n$, $r$ are positive integers? The answer supplied is $\frac{n^r-nr+r-1}{n-1}$

  1. The highest power of $n$ in $n^r! = r +$ the highest power of $n$ in $(n^r-1)!$ as $n^r$ contributes $r$ powers.

    So, the highest power of $n$ in $n^r!$ needs to be $\frac{n^r-nr+r-1}{n-1} + r =\sum_{1≤t<r}n^t $.

    This is clearly true if $n$ were prime according to this.

  2. Again, if $r=1$, $\frac{n^r-nr+r-1}{n-1}$ becomes $0$.

    But according to this, the highest power of composite $n$ in $(n-1)! ≥ 1 $.

    So, the answer does not seem to hold for $r=1$ if $n$ is composite.

  3. If $n=\prod p_i^{a_i}$, where $p_i$ are distinct primes, $n^r=\prod p_i^{ra_i}$

    So, the highest power $(q_i)$ of $p_i$ in $n^r!$ is $$\sum_{1≤t<∞}\left\lfloor\frac{n^r}{p_i^t} \right\rfloor =\sum_{1≤t≤ra_i}\frac{n^r}{p_i^t} +\sum_{ra_i+1≤t<∞}\left\lfloor\frac{n^r}{p_i^t} \right\rfloor$$ as $p^t|n^r$ for $t≤ra_i$.

    So, the highest power of $p_i^{a_i}$ in $n^r!$ is $\left\lfloor \frac{q_i}{a_i} \right\rfloor=P_i$(say).

So, the highest power of n=$\prod p_i^{a_i}$ in $n^r!$ is $min(P_i)$

I could not proceed anymore.

$\endgroup$
2
$\begingroup$

If $p$ is prime, the number of factors of $p$ in $n!$ is $\frac{n-\sigma_p(n)}{p-1}$, where $\sigma_p(n)$ is the sum of the digits of $n$ in base $p$. $\sigma_p(p^r-1)=(p-1)r$. Thus, the number of factors of $p$ in $(p^r-1)!$ is $$ \frac{p^r-1-(p-1)r}{p-1} $$ This is the formula for $p$ a prime. For a composite number, the count will be greater because there will be combinations of the factors of $n$ that give extra factors of $n$ in $(n^r-1)!$.

For example, consider the number of factors of $4$ in $(4^2-1)!$ $$ 1\cdot\color{#C00000}{2}\cdot3\cdot\color{#00A000}{4}\cdot5\cdot\color{#C00000}{6}\cdot7\cdot\color{#00A000}{8}\cdot9\cdot\color{#C00000}{10}\cdot11\cdot\color{#00A000}{12}\cdot13\cdot\color{#C00000}{14}\cdot15 $$ The number counted by $\frac{n^r-1-(n-1)r}{n-1}=\frac{16-1-3\cdot2}{4-1}=3$ is the count of the powers of $4$ in the individual factors of $15!$ (shown in $\color{#00A000}{\text{green}}$). However, this does not count the factors of $2$ contributed by the powers of $2$ in other individual factors of $15!$ (shown in $\color{#C00000}{\text{red}}$). There are $4$ powers of $2$ giving an extra $2$ powers of $4$ in $15!$.

A Strategy for Composites

For each prime $p$ that divides $n$, count the number of factors of $p$ that divide $(n^r-1)!$, and from that, compute the greatest power of $n$ that divides $(n^r-1)!$.

In the previous example, count the number of factors of $2$ that divide $15!$: $\frac{15-4}{2-1}=11$. Thus, we get $\lfloor11/2\rfloor=5$ as the power of $4$ that divides $15!$

Let's try another example. The highest power of $12$ that divides $12^3-1$. There are two primes that divide $12$: $2$ and $3$.

For $p=2$: $12^3-1=11010111111_{\text{two}}$ so $\sigma_2(12^3-1)=9$. Therefore, the number of factors of $2$ is $\frac{12^3-1-9}{2-1}=1718$.

For $p=3$: $12^3-1=2100222_{\text{three}}$ so $\sigma_3(12^3-1)=9$. Therefore, the number of factors of $3$ is $\frac{12^3-1-9}{3-1}=859$.

Thus, the highest power of $12$ that divides $(12^3-1)!$ would be $\min\left(\frac{1718}{2},859\right)=859$.

$\endgroup$
  • $\begingroup$ (i) in my question has already proved validity of the result for the primes. Is there any such formula for the composite number? $\endgroup$ – lab bhattacharjee Jul 29 '12 at 11:04

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.