addmat - additional material

Additional Material for Chapter 2

Primes and divisors of zero

The collection N0 has no divisors of zero. But the integers J_n mod n may or may not have divisors of zero. The following [AM01] shows when there are not such divisors:

[AM01](*) If p is a (positive) prime then the system J_p of integers mod p has no divisors of zero.

Let u and v be any non-zero numbers in J_p. Looking at the complete factorization of u, v and the product uv, p cannot be a factor of u and p cannot be a factor of v then p cannot be a factor of the product uv. Therefore uv cannot be equivalent to zero.

If n is a natural number and is not a prime then it is composite and there is a product hk = n. Then in J_n the numbers h and k are divisors of zero. In particular in J₆, 3 and 2 are divisors of zero, because 3 x 2 = 6 which is equivalent to 0 (mod 6).

Lemma1

The following statement will be used in the supporting argument for the division algorithm below.

(Lemma1) Let n be any natural number. The only non-negative integer h satisfying nh < n is h=0.

PART A:
First n0 = 0 < n. So h=0 is a solution for nh < n.

PART B: (Intuitive argument) nh < n is false for all natural number values for h
For h=1, n1 < n is false.
Suppose h>1. Then nh = n + n + ... + n, where n appears h times. But a sum of natural numbers is larger than any of those natural numbers.
Therefore nh > n.
Hence for all natural number values for h, nh < n is false.

PART B': (Using math induction) nh < n is false for all natural number values for h
Trivially, for h=1, nh = n. So nh < n is false for h=1.
Suppose nh < n is false for some h>1. This means that nh>n
Recall the theorem that says that the sum of two natural numbers is larger than either number.
So nh + n > n.
Therefore, n(h+1) = nh + n > n + n >n. This means that n(h+1) > n.
So n(h+1) < n is false.

Division Algorithm

VERSION A. Division has not been defined for the system of non-negative integers. It can be defined for the ratio 20/4 because some multiple of 4 is equal to 20. A few multiples of 4 are: 4(0)=4, 4(1)=4, 4(2)=8, 4(3)=12, 4(4) = 16, 4(5)=20, 4(6)=24. Among them is a unique multiple equal to 20: 4(5)=20. Therefore, ratio 20/4 = 5.

Not all ratios of non-negative integers can be calculated using only non-negative integers.

Example1: ratio 20/6 is not equal to any non-negative integer. The multiples of 6 less than 20 are:

6(0)=0, 6(1)=6, 6(2)=12, 6(3)=18 All the other multiples 6(4)=24, 6(5)=30, 6(6)=36, ... are too big. The multiple closest to 20 that is not too big is 6(3)=18. It misses 20 by 2. Therefore, 20 = 6(3) + 2. Example2: 31/4 is not equal to any non-negative integer. The multiples of 4 less than 31 are: 4(0)=0, 4(1)=4, 4(2)=8, 4(3)=12, 4(4)=16, 4(5)=20, 4(6)=24, 4(7)=28 The multiple 4(8)=32 is too big. Since 28 is 3 less than 31, 31 = 4(7) + 3.

It is important to notice that the multiple must be the largest of all the multiples less than or equal to the given number (20 and 31).

The form 20 = 6(3) + 2 is the form of the division algorithm for the ratio 20/6. Similarly, 33 = 4(7) + 5 is the form of the division algorithm for the ratio 33/7.
The form of the division algorithm for the ratio 20/4 is 20 = 4(5) + 0. The + 0 is not needed.
For the ratio 598/0 there is no form of the division algorithm, because there is no multiple of 0 near or equal to 598. For no ratio with zero denominator is there a form of the division algorithm.

(Division algorithm) For any pair of non-negative integers m,n (but n >0) the form of the division algorithm for the ratio m/n is the equation m = nq + r, where q and r are non-negative integers and 0 < r < n.
m is called the numeraator of the ratio, n is the denominator of the ratio. Also q is the quotient and r is the remainder of the form of the division algorithm.

The remainder is always a non negative integer less than the denominator.
The reaminder may equal zero. In that case, the quotient is a factor of the numerator and the ratio is actually a non-negative integer
The remainder is always less than the denominator. This is a guarantee that the minimum nearness of the multiple of the bottom number to the top number of the ratio. But this also means that the denominator cannot be zero itself.

[**] (Division algorithm) For any non-negative integer m and natural number n, there exist non-negative integers q and r satisfying

the equation m = n(q) + r and the inequality 0 < r < n

-----

VERSION B. Given two non-negative integers it is possible to produce two more non-negative integers from them using the two operations of addition and multiplication of the two numbers: m + n and and mn. The division algorithm, to be discussed here, provides another way to produce the two non-negative integers. It is based on an attempt to divide the second number into the first, using only non-negative integers. But division by zero is not allowed. So the second number must be a natural number. It may be helpful to write the division as (non-negative integer)/(natural number) even though a discussion of fractions is delayed until Chapter 4. For that reason here it is called a ratio Then the non-negative integer becomes the numerator and the natural number becomes the denominator of the ratio. (Some people prefer to use the notation non-negative integer : natural number as the symbol for ratio.
Suppose the two given numbers are 13 and 3. The ratio is the symbol 13/3. Long division has the form

The two numbers produced by the division algorithm are quotient = 4 and remainder = 1. The long division process continues until the remainder is a non-negative integer less than the natural number (denominator).
Notice that it would be impossible to do the division if the natural number were replaced by zero.

(Division algorithm - informal definition) For any non-negative integer and any natural number ,

non-negative integer = (natural number)(quotient) + remainder where remainder the quotient is a non-negative integer computed by long division shown above, and remainder is a non-negative integer less than the &nbasp; natural number Notation: if m is any non-zero integer, and if n is any natural number, then there exist non-zero integers q and r such that m = n(q) + r where 0 < r < n

Examples:
For 13 and 3, 13 = 3(4) + 1.
For 19 and 5, 19 = 5(3) + 4.
For 3 and 5, 3 = 5(0) + 3.
For 8 and 4, 8 = 4(2) + 0.

The remainder r = 0 if and only if the natural number n is a factor of the non-negative integer m.

Examples of the Division Algorithm

The reader can verify the following:
        m/n     quotient   remainder        verification: m = (quotient)n + remainder
       47/5           9                 2            verification: 47 = (9) x 5 + 2
       200/55       3                35
       43/10         4                3
       30/6          5                 0            6 is a factor of 30
       16/28        0                28
       13/0          cannot compute

Arguments supporting the Division Algorithm

Given non-negative integer m, and natural number n. To determine quotient q and ramainder r so that m = n(q) + r and the inequality 0 < r < n

Part A: Supporting argument for the division algorithm excluding uniqueness of quotient and remainder.

The geometric interpretation of the division algorithm shows m to lie between two multiples of n, or a multiple of n is equal to m. The set of multiples of n are

{0, n, 2n, 3n, ...., } If some multiple is equal to m, then m = nq and r = 0.
Sukppose that no multiple is equal to m. The differences between the multiples and m are {m, m-n, m-2n, m-3n, ...} Some of these are natural numbers. But the well ordering principle for natural numbers N says that any non-empty subset of N has a smallest natural number. So there is a smallest difference, say m - qn. Let r = that difference. This produces the quotient q and remainder r.

-----

Part B: Supporting argument for the uniqueness of quotient and remainder. (Negative integers are needed.)

Suppose there are possibly two quotients, q₁, q₂ and possibly two remainders r₁, r₂. Arrange the notation so that r₂ > r₁. Then there are possibly two equations for the division algorithm with the same given numbers m and n:

m = nq₁ + r₁ where 0 < r₁ < n, m = nq₂ + r₂ where 0 < r₂ < n Subtract the second equation from the first to get 0 = n(q₂ - q₁) + (r₂ - r₁). But since r₂ is possibly the larger, r₂ - r₁ > 0.