Can the remainder from an Euclidean Division be computed (faster?) without also computing the quotient?

Question

(Was: “Are there any (relatively) easy ways for a computer to test divisibility?”)

Given two distinct arbitrary positive integers:

1. Is there a way to determine if the smaller value is a factor of the larger value, that is computationally better than full-blown division?

2. Is there a way to determine the remainder after dividing the larger value by the smaller value, that is computationally better than full-blown division?

If only (2) is feasible, then (1) can be simulated by testing the result of (2) against zero.

Edit: I want to try Wilson’s Theorem, which uses a divisibility test to check if a number is prime or not. If there’s a way to not have to do an integer mod operation, and if it’s faster, I would want to use it to save time.

Edit 2: I keep getting duplicate flags versus Trick to find multiples mentally. But the two questions are working a different levels.

• That question is working with human intuition, but I’m looking for possibilities that a computer device can do.
• The answers to that question do lend to methods that a computer can handle, but they all use scratch work that involves MUL, DIV, and MOD operations. I’m asking for a MOD-without-DIV operation at the same level of computation as those previous operations, hopefully with less work that the chip’s internal DIV-and-MOD operation uses. That question provides answers that are inherently orders of magnitude more work. (That MOD-without-DIV operation would be part of the chip’s operations too, but we need theories on how MwD could be done before adding it to a chip design.)

Answer 1

This is a more interesting question that it first appears. State-of-the-art division algorithms use Newton's method to reduce division to multiplication. An upper bound on the time complexity of computing both the quotient $q$ and remainder $r$ in $a = bq + r$ is therefore $O(\log a \log \log a \log \log \log a)$ when using the Schönhage–Strassen algorithm, though I suspect that it's possible to do better if you know that $b$ is very small, i.e. $b \in O(\log a)$.

The optimal cost of division is an open problem and it's not obvious to me that computing only $r$ couldn't be done more cheaply than full division. On the other hand I'm not aware of more efficient specialized algorithms for general $a$ and $b$. Obviously there is a lower bound of $O(\log a)$ on both computing division and remainders.