# Appendix A

## Introduction

This appendix to the elementary arithmetic course provides proofs, additional explanations and derivations of some of the statements, theorems and rules used in the course.

## Why a negative times a negative is a positive

$−1 × 0 = 0 ⇔ −1 × (1 + −1) = 0 ⇔ (−1 × 1)+(−1 × −1)=0 ⇔ −1 + (−1 × −1) = 0 ⇔ −1 = −(−1 × −1) ⇔ 1 = −1 × −1 ☐.$

In the second line, 0 in the left side of the equation is replaced by (1+ −1). The distributive rule applied to the second line result in the third line. Subtracting (−1 × −1) from both sides of the equation in the fourth line result in the fifth line. Finally, negating both sides result in what was to be demonstrated: −1 × −1 = 1.

## Proof that the set of prime numbers is infinite

We use a proof by contradiction. The set of prime numbers is either finite or infinite. Let's assume it is finite and try to show that this assumption leads to a contradiction, which proves that it must be infinite.

So, let the finite number of primes all be collected in set $P = {p1, p2, p3, ... , pn}$ and let number $N = p1 × p2 × p3 × ... × pn + 1$.

Now, N is either prime, in which case we have a new prime number other than the original ones, which contradicts our assumption, or N is composite, in which case $N = q1 × q2 × q3 × ... × qm$, where $q1, q2, q3, ... , qm$ are N's prime factors. But no q can be a prime number from the original set P, because dividing N by any original prime or product of original primes leaves a remainder of 1 (N = p1 × p2 × p3 × ... × pn + 1). Thus $q1, q2, q3, ... , qm$ are new primes, other than the original ones, which also contradicts our start assumption. So, the set of prime numbers cannot be a finite; it must be infinite ☐.

## Why the divisibility rules work

### Divisibility by 2 or 5

$4578 = (4 × 1000) + (5 × 100) + (7 × 10) + 8$

Powers of 10 i.e. 10, 100, 1000, etc. are always divisible by 2. So, if and only if the last digit, the ones digit, is divisible by 2, the whole number is divisible by 2. Divisibility by 5 works the same.

### Divisibility by 3

$4578 = (4 × (999+1)) + (5 × (99+1)) + (7 × (9+1)) + 8 = (4 × 999) + 4 + (5 × 99) + 5 + (7 × 9) + 7 + 8 = (4 × 999)+ (5 × 99) + (7 × 9) + 4 + 5 + 7 + 8.$

9, 99, 999, etc. are always divisible by 9 and thus also by 3. So, if and only if the addition of all digits is divisible by 3, the whole number is divisible by 3.

### Divisibility by 7

$4578 = (457 × 10) + 8$

If 4578 is divisible by 7, then 2 × 4578 is as well, and vice versa:

$2 × 4578 = 457 × 20 + (2 × 8) = 457 × (21 - 1) + (2 × 8) = (457 × 21) - 457 + (2 × 8).$

(457 × 21) is divisible by 7 (because 21 is divisible by 7). If $−457 + (2 × 8)$ is divisible by 7, then $457 - (2 × 8)$ is divisible by 7 and 4578 is divisible by 7 (and vice versa).

So, a number is divisible by 7 if and only if the subtraction of 2 times the last digit from the number formed by the rest of the digits is divisible by 7.

### Divisibility by 11

$4578 = 457 × (11 - 1) + 8 = (457 × 11) - 457 + 8.$

If 4578 is divisible by 11, then −457 + 8 is divisible by 11, then 457 − 8 is divisible by 11 (and vice versa).

So, a number is divisible by 11 if and only if the subtraction of the last digit from the number formed by the rest of the digits is divisible by 11.

Or:

$4578 = (4 × (999+1)) + (5 × (99+1)) + (7 × (9+1)) + 8 = (4 × 999) + 4 + (5 × 99) + 5 + (7 × 9) + 7 + 8 = (4 × 999)+ (5 × 99) + (7 × 9) + 4 + 5 + 7 + 8.$

If and only if the alternating subtraction and addition of all digits is divisible by 11, the whole number is divisible by 11.

### Divisibility by 13

$9 × 4578 = 457 × 90 + (9 × 8) = 457 × (91 - 1) + (9 × 8) = (457 × 91) - 457 + (9 × 8).$

If and only if the subtraction of 9 times the last digit from the number formed by the rest of the digits is divisible by 13, the whole number is divisible by 13.

## Derivation of some of the arithmetic rules for fractions

$(0/ a) = 0 × (1/a) = 0$

$(a/ b) = 1 × (a/ b) = (c/c) × (a/ b) = (a×c)/(b×c)$

$(a/ b) ± (c/ b) = a×(1/ b) ± c×(1/ b) = (1/ b)×(a±c) = (a±c)/b$

$(a/ b) ± (c/d) = (a×d)/(b×d) ± (c×b)/(b×d) = (a×d ± c×b)/(b×d)$

$(a/ b) / (c/d) = ((a/ b)×(d/c)) / ((c/d)×(d/c)) = ((a/ b)×(d/c)) / 1 = (a/ b) × (d/c)$

$−(a/ b) = −1 × (a/ b) = (-1 × a)/ b = (-a/ b) = (-1/-1) × (-a/ b) = (-1 × -a)/(-a × b) = a/−b$

## Why does the Euclidean algorithm work?

Let:

• $gcd(a=px,b=py) = p, a > b, b > 0$, a > b, b > 0,
• t be any positive integer,
• qk be a quotient and rk be a remainder:

$a-tb = px-tpy = p(x-ty)$

Thus,

$gcd(a,b) = gcd(a,b,a-tb)$

$a/b = q_0 + (r_0/b) = (bq_0)/b + (r_0/b).$

$a/b = (bq_0 + r_0)/b ⇔ a = bq_0 + r_0 ⇔ a - bq_0 = r_0$

Thus,

$gcd(a,b) = gcd(b,a-bq_0) = gcd(b,r_0), (b>r_0)$

$\begin{array}{lr}\mathrm{gcd}\left(a,b\right)=\mathrm{gcd}\left(b,{r}_{0}\right)& b>{r}_{0}\\ \mathrm{gcd}\left(b,{r}_{0}\right)=\mathrm{gcd}\left({r}_{0},{r}_{1}\right)& {r}_{0}>{r}_{1}\\ \mathrm{gcd}\left({r}_{0},{r}_{1}\right)=\mathrm{gcd}\left({r}_{1},{r}_{2}\right)& {r}_{1}>{r}_{2}\\ \mathrm{\dots }& \\ \mathrm{gcd}\left({r}_{k},{r}_{k-1}\right)=\mathrm{gcd}\left({r}_{n},{r}_{n-1}\right)& {r}_{n-1}>{r}_{n}\end{array}$

The remainder rk (always an integer) is always smaller than the remainder in the step before. So, the remainder must finally be: $r_n = 0$. Thus we can write:

$gcd(a,b) = gcd(r_k,r_(k-1)) = gcd(0,r_(n-1)) = r_(n-1)$