Number is Divisor iff Modulo is Zero

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $x, y \in \R$ be real numbers.

Let $x \bmod y$ denote the modulo operation:

$x \bmod y := \begin{cases} x - y \left \lfloor {\dfrac x y}\right \rfloor & : y \ne 0 \\ x & : y = 0 \end{cases}$

where $\left \lfloor {\dfrac x y}\right \rfloor$ denotes the floor of $\dfrac x y$.


Then $x \bmod y = 0$ if and only if $x$ is an integer multiple of $y$.


Poof

Sufficient Condition

Let $x \bmod y = 0$.

From Number minus Modulo is Integer Multiple:

$x - \left({x \bmod y}\right)$

is an integer multiple of $y$.


As $x \bmod y = 0$ it follows that $x - 0 = x$ is an integer multiple of $y$.

$\Box$


Necessary Condition

If $y = 0$ it follows from Zero Divides Zero that $x = 0$.

Hence the result by definition of the modulo operation:


Otherwise, let $y \ne 0$.

Let $x$ be an integer multiple of $y$.

That is:

$\exists n \in \Z: x = n y$

Hence:

$\dfrac x y = n$

From Quotient of Modulo Operation with Modulus:

$\dfrac x y - \left \lfloor {\dfrac x y}\right \rfloor = \dfrac {x \bmod y} y$

From Real Number is Integer iff equals Floor it follows that:

$\dfrac x y = \left\lfloor{\dfrac x y}\right\rfloor$

Thus:

$\dfrac {x \bmod y} y = 0$

and so multiplying both sides by $y$ the result follows.

$\blacksquare$


Sources