I was curious about the following little problem. Suppose $n \in \mathbb{N}$ is some large number and $p$ is a (possibly large) prime, and I want to update $n$ according to

$$n := \begin{cases} n/p, & (n,p) = p; \\ n, & (n,p) = 1.\end{cases}$$

In other words, I want to divide by $p$ if $p$ divides $n$, and not divide by $p$ if $p$ does not divide $n$. Also, I would like to know if a division took place. Of course I could implement this with something like

  n = Quotient[n,p]; 
  Print["A division took place!"];

However, this feels inefficient, since to check divisibility the machine may have already computed $n/p$. Would there be a more efficient way to do this in Mathematica? i.e. A way that uses only $1$ division if $p$ divides $n$ and at most $1$ division if $p$ does not divide $n$?

Also, I'm curious which Mathematica functions would be most suited for these purposes in general. Is there any difference in performance between e.g. Divisible[n,p], Mod[n,p] == 0, IntegerQ[n/p], FractionalPart[n/p] == 0, CoprimeQ[n,p], GCD[n,p] == p?

Thanks in advance.

  • $\begingroup$ Divisible seems to be faster than actually doing the division in my computer. But even if it wasn't, as long as it's slightly faster to check for divisibility than doing the division, saving the result and checking if the remainder was 0, whether this is convenient or not depends on how often you will actually put numbers that divide each other... If they are both random big numbers, I'm guessing not often, so you probably already have an efficient solution (without resorting to compiling) $\endgroup$
    – Rojo
    Mar 18, 2012 at 21:56
  • 3
    $\begingroup$ QuotientRemainder might be useful. $\endgroup$
    – Szabolcs
    Mar 18, 2012 at 22:08
  • 2
    $\begingroup$ If you plan to repeat this until you exhaust powers of p, go with IntegerExponent. $\endgroup$ Mar 19, 2012 at 1:12

1 Answer 1


To stay with your example:

n = 12; p = 4;
   #2 == 0, n= #1;
   Print["A division took place!"]
   ] & @@ QuotientRemainder[n, p]

A division took place!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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