Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What is the most efficient (in time complexity) algorithm known nowadays for the Divisibity Decision Problem: given two integers, say $a$ and $b$, does $a$ divide $b$? Let it be clear that what I ask for is not (necessarily) an algorithm for Remainder Calculation. I just want to know whether $a$ divides $b$ or not.

Thanks and regards, Leandro

share|cite|improve this question
How are your integers stored? – Phira Dec 18 '12 at 16:05
mpz_divisible_p – Hurkyl Dec 18 '12 at 16:51
Phira, my integers are stored like binary strings. – Leandro Zatesko Dec 18 '12 at 18:09
Thanks, Hurkyl, but it's not clear for me, reading the gmp documentation, what algorithm they use, nor it's clear its time complexity. My question is whether exists or not some recent algorithm for Divisibility with time complexity less than $O(m\log m\log\log m)$, where $m$ is the number of bits of $\max\{a,b\}$. – Leandro Zatesko Dec 18 '12 at 18:32

Your Answer


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

Browse other questions tagged or ask your own question.