Quotient And Remainder

Quotient Remainder

Suppose that

a, b \in ℤ

, but that

b \neq 0

, then there exists unique integers

q, r

such that

a = b \cdot q + r

where

0 \leq r < | b |

Let $a, b \in ℤ$ and assume $b \neq 0$ . Define $S = {x \in ℤ : x \geq 0 and x = a + | b | \cdot k where k \in ℤ} \subseteq ℕ_{0}$ , we'll show that $S$ is non-empty. We can think of $S$ as taking $a$ and then either adding muliples of $| b |$ or subtracting them to $a$ , each time leaving some remainder, thinking ahead we can guess that the smallest value of this set should be the smallest remainder and possibly the $r$ we are looking for.

If $a \geq 0$ then when $k = 0$ we have $a + | b | \cdot k = a \geq 0$ thus $a \in S$ , on the other hand if $a < 0$ , then observe that since $0 \leq r < | b |$ , then $1 \leq | b | ⟺ 0 \leq | b | - 1$ and also $- a > 0$ , then we have $0 \leq (| b | - 1) \cdot (- a)$ . But also we can see that $(| b | - 1) \cdot (- a) = | b | \cdot (- a) + a$ so it's of the form of an element in $S$ and since it's non-negative, it must be an element of $S$ . Therefore this paragraph shows us that $S$ has at least one element, no matter the value of $a$ .

Due to this and since $S \subseteq ℕ_{0}$ , then by the well ordering principle there is some smallest element $s \in S$ , we know that this value satisfies $s = a - | b | \cdot k$ . Now we will show that $0 \leq s < | b |$ .

$s \in S$ so therefore $s \geq 0$ , if we were to assume that $s \geq | b |$ then $s - | b | \geq 0$ . By recalling the equality that $s$ satisifies we can write $s - | b | = (a - | b | \cdot k) - | b | = a - | b | (k + 1)$ , therefore $s - | b | \in S$ but since $| b | > 1$ then $s - | b | < s$ which is a contradiction because we assumed that $s$ was the smallest element in $S$ , thus we must have that $s <; | b |$

At this point we have $a = | b | \cdot k + s$ where $0 \leq s < | b |$ so take $q = sgn (b) \cdot k$ and $r = s$ . If $b \geq 0$ , then $| b | = b$ and $sgn (b) = 1$ , so we obtain $a = b \cdot k + s$ , if $b <; 0$ , then $| b | = - b$ and $sgn (b) = - 1$ so again we have $a = (- b) \cdot (- 1) k + s$ . We'll finish the proof by showing that these values are unique.

Assume we have another pair $q, r$ satisfying $a = b \cdot q + r$ with $0 \leq r \leq | b |$ but $q \neq q$ and $r \neq r$ , therefore we have $b \cdot q + r = b q + r ⟺ r - r = b \cdot (q - q)$ .

Without loss of generality assume $r > r$ , then $r - r > 0$ and since $0 \leq r < | b |$ then $0 \leq r - r \leq r < | b |$ , recalling that $r - r = | b | \cdot (q - q)$ , we can re-write our last inequality as $0 \leq | b | \cdot (q - q) < | b |$ and since $b \neq 0$ we can divide by $| b |$ to get $0 < q - q < 1$ but since $q, q \in ℤ$ this force $q = q$ , which then shows $r = r$ by previous equalities, therefore assuming we have another solution, it turns out it must be our original one, and thus our solution is unique.

Note that the requirement that $b$ be non-zero is important, because if it were zero we'd be asking "how many times do you have to multiply $0$ and add $r$ to get $a$ " which in itself doesn't intuitively make sense, formally since we require $0 \leq r < | b |$ then if $b = 0$ no such $r$ could ever exist.

Remainder Function

Given two integers

a, b \in ℤ

such that

b \neq 0

, then we get some

q, r \in ℤ

with

0 \leq r < | b |

such that

a = b \cdot q + r

and we define

a % b : = r

Quotient Function

Given two integers

a, b \in ℤ

such that

b \neq 0

, then we get some

q, r \in ℤ

with

0 \leq r < | b |

such that

a = b \cdot q + r

and we define

a / / b : = q

Quotient Remainder using Quotient and Remainder Function

For any

a, b \in ℤ

such that

b \neq 0

then

a = b (a / / b) + a % b

Specific Value of the Divisor Function

We note that

a / / b = ⌊ \frac{b}{a} ⌋

Specific Value of the Remainder Function

We note that

a % b = b - ⌊ \frac{b}{a} ⌋ a

Quotient Remainder on Positive Integer has Positive Divisor

Suppose that

a, b \in ℕ_{1}

such that

a \geq b

then

a / / b \geq 1

For brevity define $q = a / / b$ , we know that $a = b \cdot q + r$ with $0 \leq r < b$ , thus far we know that $q \in ℤ$ , though if $q <; 0$ , then we know that $b \cdot q <; r \cdot q \leq 0$ , therefore $a = b \cdot q + r <; r \cdot q + r = r (q + 1)$

For a contradiction assume that $q < 1 ⟺ q \leq 0$ , therefore $r (q + 1) \leq r (0 + 1) = r$ , which shows that $a < r$ , since $0 \leq r < b$ , then we have $a < b$ which is a contradiction because we know that $a \geq b$ .

Since by assuming $q < 1$ , we have a contradiction, so therefore $q \geq 1$ , which is the same as $a / / b \geq 1$ .

Divides iff Zero Remainder

For any

a, b \in ℤ

a | b ⟺ a % b = 0

Note that

a | b

iff

b = k a = k a + 0

iff

a / / b = k

and

a % b = 0

. The last iff comes from the fact that there are unique integers that satisfy the equation laid out by the quotient remainder theorem.

Every integer is either Odd or Even

For any

z \in ℤ

, it is even or it is odd

Let

z \in ℤ

and then we know that

z % 2 \in {0, 1}

, if

z % 2 = 1

then there is some

q \in ℤ

such that

z = q \cdot 2 + 1

, and thus odd, if

z % 2 = 0

, then we have some

q \in ℤ

such that

z = q \cdot 2 + 0

and is thus even

Exactly one of any two Consecutive Numbers is Even

For any

n \in ℤ

exactly one of

n, n + 1

is even (and the other odd)

n

is even, we are done, if

n

is odd, then there is a

k \in ℤ

such that

n = 2 k + 1

therefore

n + 1 = 2 (k + 1)

which is even as needed.

When the Remainder Function does Nothing

Suppose that

m \in ℕ_{1}

and that

a \in [0, \dots, m - 1]

then

a % m = a

Remainder of Sum Less Than First Summand When Sum Exceeds Modulus

Suppose that

n \in ℕ_{1}

and

a, b \in [0, \dots, n - 1]

such that

a + b \geq n

, then

(a + b) % n < a

Since $a \leq n - 1$ and $b \leq n - 1$ we have $a + b \leq 2 n - 2$ , combined with our assumption that $a + b \geq n$ we obtain $n \leq a + b \leq 2 n - 2$ and therefore $0 \leq a + b - n \leq n - 2 < n$ succinctly: $0 \leq a + b - n < n$ and since we know $a + b = n + (a + b - n)$ then by quotient remainder we conclude $(a + b) % n = a + b - n$

Another way of seeing the above is that $(a + b) % n = a - (n - b)$ , and this is a better form because if we knew that $n - b > = 1$ then we could conclude that $(a + b) % n < a$ , but we did know that $b \in [0, \dots, n - 1]$ therefore $b \leq n - 1$ which yields $n - b \geq 1$ as needed.

Repeated Application of the Remainder Function does Nothing

Suppose that

a, m \in ℤ

such that

m \neq 0

then

a % m = (a % m) % m

Quotient Remainder and Addition

Suppose that

a, b, m \in ℤ

then

(a + b) % m = ((a % m) + (b % m)) % m

and

(a + b) / / m = a / / m + b / / m + (a % m + a % b) / / m

We know

a = m (a / / m) + a % m and b = m (b / / m) + b % m

therefore

a + b = m ((a / / m) + b / / m) + (a % m + b % m)

Let

x = (a % m + b % m)

, and so by the quotient remainder theorem we get some

q_{x}, r_{x}

such that

x = m q_{x} + r_{x}

so that

a + b = m ((a / / m) + (b / / m) + q_{x}) + r_{x}

therefore

(a + b) % m = r_{x}

and

(a + b) / / m = (a / / m) + (b / / m) + q_{x}

. Finally note that

r_{x} = (a % m + b % m) % m

and

q_{x} = (a % m + b % m) / / m

as needed.

If a Number Divides a Sum and Already Divides one of the Summands it Must Divide the Other

Suppose that

d | a + b

and

d | a

then

d | b

We know that

(a + b) % d = 0

and that

a % d = 0

since

\begin{matrix} 0 & a m p; = (a + b) % d \\ a m p; = (a % b + b % d) % d \\ a m p; = (0 + b % d) % d \\ a m p; = b % d \end{matrix}

therefore

d | b

Adding Multiples of the Divisor Never changes the Remainder

Let

m \in ℤ^{\neq 0}

and

a, k \in ℤ

then

a % m = (a + k m) % m

n Factorial Plus or Minus One Restricts Factors

Suppose

n \in ℕ_{1}

then for every

m \in [2, \dots, n]

m ∤ n! \pm 1

Recall that

m | n!

therefore

n! % m = 0

. But then

\begin{matrix} (n! \pm 1) % m & a m p; = (n! % m \pm 1 % m) % m \\ a m p; = (\pm 1 % m) % m \\ a m p; = \pm 1 % m \end{matrix}

Note that in going from the second to the third line we used this fact.

if $\pm = +$ then we have $(n! + 1) % m = 1$ otherwise we have $(n! + 1) % m = - 1 % m = m - 1$ and since $m \neq 1$ then $m - 1 \neq 0$ therefore in both cases we see that $(n! + 1) % m \neq 0$ therefore $m ∤ (n! + 1)$ as needed.

Every Perfect Square has Remainder Zero or One Upon Division by Four

For any

n \in ℤ

we have

n^{2} % 4 \in {0, 1}

We know that

n

is either odd or even and therefore in the case that

n = 2 k

then

n^{2} = 4 k^{2} = 2 (2 k^{2}) + 0

n^{2} % 4 = 0

, on the other hand if

n = 2 k + 1

then

n^{2} = 4 k^{2} + 4 k + 1 = 2 (2 k^{2} + 2 k) + 1

therefore

n^{2} % 4 = 1

as needed.

Note that we also see that every odd perfect square has remainder 1 mod 8 as an intermediate stage in the above proof.

Every Odd Perfect Square has Remainder 1 mod 8

As per title.

Suppose that

n^{2} = 2 k + 1

it's impossible for

n

to be even, because then

n^{2}

would be, since every number is either even or odd, then

n

must have been even, therefore there is a

j \in ℤ

such that

n = 2 j + 1

therefore

n^{2} = 4 j^{2} + 4 j + 1 = 4 (j (j + 1)) + 1

. Recall that at least one of

j, j + 1

is even , therfore

j (j + 1)

is even and therefore

4 (j (j + 1))

is divisible by

8

in other words we have some

m \in ℤ

such that

n^{2} = 8 m + 1

as needed.

composite number

A number

n \in ℕ_{1}

is said to be composite, when it has a positive divisor other than

1

and itself

multiplicative function

an arithmetic function is said to be multiplicative when

f (m) \cdot f (n) = f (m \cdot n)

for all coprime positive integers

m, n

Suppose that

d (n)

is the number of divisors of

n

, then

d

is a multiplicative function.

Let $m, n \in ℤ^{+}$ and assume that $\gcd (m, n) = 1$ , we'd like to prove that $d (m) \cdot d (n) = d (m \cdot n)$

Suppose that the divisors of $m$ are $P = {p_{1}, \dots, p_{j}}$ and the divisors of $n$ are $Q = {q_{1}, \dots, q_{k}}$

Claim that the set $P \cdot Q = {p_{x} \cdot q_{y} : x \in [j], y \in [k]}$ is exactly equal to the divisors of $m \cdot n$