# Divisibility by a prime number and multiplicity

We want to determine the number of times a prime number $p$ divides a number $n$ or, in other words, determine the greatest integer $k$ such that $p^k\ |\ n$.

Is there a better method than trying naive division successively?

• Do ask about actual numerical computation for large ingers? Here the repeated division can very time-consuming. MP libraries use a strategy with increasing powers of $p$, see e.g. the Gnu MP function mpz_remove (remove.c) Sep 14, 2017 at 13:57
• @gammatester Thanks for your comment, but is "computing successive powers of $p$ and testing division for each power" really less time consuming than "simply testing successive division by $p$"? Sep 14, 2017 at 14:39
• I did not say "computing successive powers of p". Actually the simple idea is something like this: From $i=0$ keep on dividing by ascending powers $p^{2^i}$ until a non-zero remainder is found (while storing these powers, note that the next power is just a squaring), then divide by the stored descending powers giving a zero remainder. Sep 14, 2017 at 15:18
• @gammatester Sorry, you are right that was obvious. Thank you. Sep 15, 2017 at 9:27

In general, there are several integer factorization algorithms, which are sometimes better than just naive division. See also this MSE-question. For some integers, there is an explicit formula for the multiplicity, e.g., for $n=N!$. In fact, the highest power of a prime $p$ dividing $N!$ is given by
$$\nu_p(N!) = \left \lfloor \frac{N}{p} \right \rfloor + \left \lfloor \frac{N}{p^2} \right \rfloor + \left \lfloor \frac{N}{p^3} \right \rfloor + \cdots$$
The main difficulty often is to find any prime dividing our integer $n$. For example, which prime divides $n=1167984798111281975972139931059274579165801700195500732513291383783133049$ $58815197564537037428785261488414688806744251221941374876801065757257538498$ $6457405973985247465176041951676954461208131403777$
Once you have discovered that $$p=2^{127}-1$$ is a prime divisor, it is easy to see that $p^2$ does not divide $n$.
• Thank you for your answer. In fact, my $n$ is an arbitrary number, and not the factorial of a number. What do you mean by MSE? Thank you again Sep 14, 2017 at 14:43