Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

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

share|improve this answer
    
(i) in my question has already proved validity of the result for the primes. Is there any such formula for the composite number? –  lab bhattacharjee Jul 29 '12 at 11:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.