Checking for Integer Divisibility

Suppose that we are not allowed to use the division operator or remainder operator in a programming language such as JavaScript. With this constraint, how can we check whether or not an integer evenly divides another? Consider the following approach.

Definition. Let $a$ and $d$ be integers. We say that $d$ divides $a$ if there exists an integer $q$ such that $a=qd$.

Proposition. Let $a, q, d$ be integers such that $d \neq 0$. If $a = qd$, then $ \lvert a \rvert \geq \lvert q \rvert$.

Proof. Since $ a=qd $ implies that $\lvert a \rvert = \lvert qd \rvert = \lvert q \rvert \cdot \lvert d \rvert \geq \lvert q \rvert $, then $\lvert a \rvert \geq \lvert q \rvert$. Thus, if $a = qd$, then $\lvert a \rvert \geq \lvert q \rvert$. $\blacksquare$

So, in order to check whether $d$ divides $a$, a computer program would just have to search for an integer $q$ between $-a$ and $a$ (inclusive) such that $a = qd$. The following approach has linear time complexity, a function of $a$; I would describe it as being naïve or brute force.

Some thought should be given to numeric overflow when $q$ and $d$ are large numbers.

divides.test.js

const expect = require('chai').expect;
const divides = require('./divides');

describe('divides', () => {
    // negatives
    it('returns true for -14 divides 28', () => {
        const expected = true;
        const actual = divides(-14, 28);
        expect(expected).to.equal(actual);
    });

    it('returns false for -14 divides 13', () => {
        const expected = false;
        const actual = divides(-14, 13);
        expect(expected).to.equal(actual);
    });

    it('returns true for 9 divides -18', () => {
        const expected = true;
        const actual = divides(9, -18);
        expect(expected).to.equal(actual);
    });

    it('returns false for 32 divides -2', () => {
        const expected = false;
        const actual = divides(32, -2);
        expect(expected).to.equal(actual);
    });

    it('returns true for -4 divides -56', () => {
        const expected = true;
        const actual = divides(-4, -56);
        expect(expected).to.equal(actual);
    });

    it('returns false for -5 divides -99', () => {
        const expected = false;
        const actual = divides(-5, -99);
        expect(expected).to.equal(actual);
    });

    // positives
    it('returns false for 15 divides 25', () => {
        const expected = false;
        const actual = divides(15, 25);
        expect(expected).to.equal(actual);
    });

    it('returns true for 9 divides 72', () => {
        const expected = true;
        const actual = divides(9, 72);
        expect(expected).to.equal(actual);
    });

    it('returns false for 27 divides 9', () => {
        const expected = false;
        const actual = divides(27, 9);
        expect(expected).to.equal(actual);
    });

    // zeroes
    it('returns true for 13 divides 0', () => {
        const expected = true;
        const actual = divides(13, 0);
        expect(expected).to.equal(actual);
    });

    it('returns false for 0 divides 42', () => {
        const expected = false;
        const actual = divides(0, 42);
        expect(expected).to.equal(actual);
    });

    it('returns false for 0 divides 0', () => {
        const expected = false;
        const actual = divides(0, 0);
        expect(expected).to.equal(actual);
    });

    // ones
    it('returns true for 1 divides 8', () => {
        const expected = true;
        const actual = divides(1, 8);
        expect(expected).to.equal(actual);
    });

    it('returns false for 13 divides 1', () => {
        const expected = false;
        const actual = divides(13, 1);
        expect(expected).to.equal(actual);
    });

    it('returns true for 1 divides 1', () => {
        const expected = true;
        const actual = divides(1, 1);
        expect(expected).to.equal(actual);
    });
});

divides.js

module.exports = (d, a) => {
    // some edge cases
    if (d == 0) {
        return false;
    }

    if (a == 0 || d == 1) {
        return true;
    }

    if (Math.abs(d) <= Math.abs(a)) {
        let start = -a;
        let end = a;
        if (a < 0) {
            start = a;
            end = -a;
        }
        for (let q = start; q <= end; q++)
            if (a === q * d)
                return true;
    }
    return false;
}