In this section, we connect divisibility and division with remainder to the division and modulus operations found in many programming languages, which enables us to write performant versions of our naive functions.

## division schemes

Since division of an integer (the dividend) by a nonzero integer (the divisor) does not always yield an integer, we need a reliable scheme for producing an integer. This choice of integer division is often paired with a modulus or remainder operator.

We will write `a div b`

for the integer division of $ a $ by $ b $ and `a mod b`

for the corresponding modulus or remainder operation. These two operators are often
defined so that `a == b * (a div b) + (a mod b)`

, which looks very much like the quotient and remainder from the division algorithm.

However, depending on the scheme and the signs of the dividend and divisor, the quotient and remainder may or may not match those from the division algorithm. There are four typical schemes for defining integer division. Many programming languages will implement one or more of these.

- Truncated division is division where the quotient is rounded towards zero. The corresponding
modulus operator will yield a remainder whose sign matches the dividend.

For example, the`47 div 10 ~> 4 47 mod 10 ~> 7 47 div -10 ~> -4 47 mod -10 ~> 7 -47 div 10 ~> -4 -47 mod 10 ~> -7 -47 div -10 ~> 4 -47 mod -10 ~> -7`

`%`

operator in C, Go, Rust, and Swift are based on truncation while the`rem`

operator in Elixir, Haskell, and Lisp are based on truncation. - Floored division is division where the quotient is rounded towards negative
infinity. The corresponding modulus operator will yield a remainder whose sign
matches the divisor.

For example, the`47 div 10 ~> 4 47 mod 10 ~> 7 47 div -10 ~> -5 47 mod -10 ~> -3 -47 div 10 ~> -5 -47 mod 10 ~> 3 -47 div -10 ~> 4 -47 mod -10 ~> -7`

`%`

operator in Python and Ruby are based on floored division while the`mod`

operator in Haskell and Lisp are based on floored division. - Euclidean division is the division defined by the division algorithm from the
previous section. In particular, the quotient and remainder are defined so that
the remainder is always nonnegative.

For example, Rust provides Euclidean division functionality in the standard library via the`47 div 10 ~> 4 47 mod 10 ~> 7 47 div -10 ~> -4 47 mod -10 ~> 7 -47 div 10 ~> -5 -47 mod 10 ~> 3 -47 div -10 ~> 5 -47 mod -10 ~> 3`

`div_euclid()`

and`rem_euclid()`

integer methods. - Rounded division is division where the quotient is rounded to the nearest integer.
The corresponding modulus operator will yield a remainder closer to zero, ie, a
remainder $ r $ such that $ -|b|/2 < r <= |b|/2 $.

This is not as common, but the`47 div 10 ~> 5 47 mod 10 ~> -3 47 div -10 ~> -5 47 mod -10 ~> -3 -47 div 10 ~> -5 -47 mod 10 ~> 3 -47 div -10 ~> 5 -47 mod -10 ~> 3`

`mods`

operator in Maple uses rounded division, for example. There is also functionality based on rounded division in C and Swift, however it is floating point as opposed to integer functionality.

Note also that some languages provide combined division with remainder functionality,
for example `divmod`

in Python and Ruby or `div_rem`

in Rust.

## exercises

- Using your language's modulus operator, write a more performant
`divides`

function that has the same output as the naive version from 1.1. divisibilitySome test values:

`divides(15, 45) ~> true`

`divides(-15, 45) ~> true`

`divides(15, -45) ~> true`

`divides(-15, -45) ~> true`

`divides(10, 45) ~> false`

`divides(-10, 45) ~> false`

`divides(10, -45) ~> false`

`divides(-10, -45) ~> false`

`divides(7, 0) ~> true`

`divides(7, 7) ~> true`

`divides(7, -7) ~> true`

`divides(1, 7) ~> true`

`divides(-1, 7) ~> true`

`divides(0, 7) ~> false`

solution`module NumberTheory::Division def divides(b, a) b != 0 && a % b == 0 end end`

- Use your language's division and modulus operators to write a more performant
`div_rem`

function that has the same output as the naive version from the last section.Some test values:

`div_rem(47, 10) ~> [4, 7]`

`div_rem(47, -10) ~> [-4, 7]`

`div_rem(-47, 10) ~> [-5, 3]`

`div_rem(-47, -10) ~> [5, 3]`

`div_rem(90, 10) ~> [9, 0]`

`div_rem(90, -10) ~> [-9, 0]`

`div_rem(-90, 10) ~> [-9, 0]`

`div_rem(-90, -10) ~> [9, 0]`

`div_rem(10, 47) ~> [0, 10]`

`div_rem(10, -47) ~> [0, 10]`

`div_rem(-10, 47) ~> [-1, 37]`

`div_rem(-10, -47) ~> [1, 37]`

`div_rem(0, 99) ~> [0, 0]`

`div_rem(0, -99) ~> [0, 0]`

solution`module NumberTheory::Division def div_rem(a, b) remainder = a % b remainder += b.abs if remainder < 0 quotient = (a - remainder) / b [quotient, remainder] end end`

- Write a
`div`

function that returns the quotient from the division algorithm, respectively.Some test values:

`div(47, 10) ~> 4`

`div(47, -10) ~> -4`

`div(-47, 10) ~> -5`

`div(-47, -10) ~> 5`

`div(90, 10) ~> 9`

`div(90, -10) ~> -9`

`div(-90, 10) ~> -9`

`div(-90, -10) ~> 9`

`div(10, 47) ~> 0`

`div(10, -47) ~> 0`

`div(-10, 47) ~> -1`

`div(-10, -47) ~> 1`

`div(0, 99) ~> 0`

`div(0, -99) ~> 0`

solution`module NumberTheory::Division def div(a, b) div_rem(a, b).first end end`

- Write a
`rem`

function that returns the quotient from the division algorithm, respectively.Some test values:

`rem(47, 10) ~> 7`

`rem(47, -10) ~> 7`

`rem(-47, 10) ~> 3`

`rem(-47, -10) ~> 3`

`rem(90, 10) ~> 0`

`rem(90, -10) ~> 0`

`rem(-90, 10) ~> 0`

`rem(-90, -10) ~> 0`

`rem(10, 47) ~> 10`

`rem(10, -47) ~> 10`

`rem(-10, 47) ~> 37`

`rem(-10, -47) ~> 37`

`rem(0, 99) ~> 0`

`rem(0, -99) ~> 0`

solution`module NumberTheory::Division def rem(a, b) div_rem(a, b).last end end`