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 4578 = ( 4×999 ) + 4 + ( 5×99 ) + 5 + ( 7×9 ) + 7 + 8 4578 = ( 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 ) 2×4578 = 457× ( 211 ) + ( 2×8 ) 2×4578 = ( 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× ( 111 ) + 8 4578 = ( 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× ( 10011 ) ) + ( 5× ( 99+1 ) ) + ( 7× ( 111 ) ) + 8 4578 = ( 4×91×11 ) 4 + ( 5×9×11 ) + 5 + ( 7×11 ) 7 + 8 4578 = ( 4×91×11 ) + ( 5×9×11 ) + ( 7×11 ) 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 ) 9×4578 = 457× ( 911 ) + ( 9×8 ) 9×4578 = ( 457×91 ) 457 + ( 9×8 ) 9×4578 = ( 457×7×13 ) 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 a b ± c b = 1 b × ( a ± c ) a b ± c b = a±c b

a b ± c d = a×d b×d ± b×c b×d a b ± c 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 c d = a b × d c

a b = 1 × a b = 1 × a b a b = a b a b = 1 1 × a b = 1 × a 1 × b a b = a b

Why does the Euclidean algorithm work?

Let:

atb = px tpy = p xty

Thus,

gcd a b = gcd a b atb

a b = q0 + r0 b = q0b b + r0 b

a b = r0 + q0b b a = r0 + q0b a q0b = r0

Thus,

gcd a b = gcd b a q0b gcd a b = gcd b r0 b> r0

gcd a b = gcd b r0 b> r0 gcd b r0 = gcd r0 r1 r0> r1 gcd r0 r1 = gcd r1 r2 r1> r2 gcd rk rk1 = gcd rn rn1 rn1> rn

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

gcd a b = gcd rk rk1 gcd a b = gcd 0 rn1 gcd a b = rn1