0
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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) $\endgroup$ Sep 14, 2017 at 13:57
  • $\begingroup$ @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$"? $\endgroup$
    – Adam54
    Sep 14, 2017 at 14:39
  • $\begingroup$ 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. $\endgroup$ Sep 14, 2017 at 15:18
  • $\begingroup$ @gammatester Sorry, you are right that was obvious. Thank you. $\endgroup$
    – Adam54
    Sep 15, 2017 at 9:27

1 Answer 1

1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – Adam54
    Sep 14, 2017 at 14:43
  • $\begingroup$ MSE is this site here, called Mathematics StackExchange. $\endgroup$ Sep 14, 2017 at 14:44
  • $\begingroup$ Oups sorry :-/ . Thank you. $\endgroup$
    – Adam54
    Sep 14, 2017 at 14:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .