Every fraction has a unique reduced form, and there is a sequence of explicit steps to obtain the reduced form.
This section proves that every fraction has a unique reduced form, i.e., a fraction equal to the original fraction so that its numerator and its denominator have no common factor other than 1, and that there is a sequence of explicit steps to get the reduced form.
The proof of this theorem is as important as the theorem itself because it proves the Euclidean algorithm along the way.
The proof of the latter is, in turn, most interesting because it uncovers the mathematical potential of division-with-remainder, a mundane tool usually taught as a rote skill in TSM.
Why not use LCD in defining addition of fractions?
Why not use the Least Common Denominator to define the addition of fractions? Wu’s discussion of this can be found here (look at both the Pedagogical Comments and the Mathematical Aside that follows):
Divisors, GCD, and the reduced form of a fraction
First, some terms we use when talking about integers and divisibility.
Basic Concepts of Divisibility
Definition. A nonzero integer d is a divisor or factor of an integer a if $a=cd$ for some integer c. (NOTE: A divisor is nonzero by definition!)
- We also say d divides a, written $d | a$.
- We also say a is a multiple of d (in particular, a is an integral multiple of d).
- We call an expression of a as a product, $a=cd$, a factorization of a.
Definition. Consider two whole numbers a and b (not both 0). An integer d is a common divisor of a and b if d divides a and d divides b.
Definition. An integer d is the GCD (greatest common divisor) of whole numbers a and b if d is a common divisor of a and b and, among all common divisors of a and b, d is the greatest. Notation: $d=GCD(a,b)$.
Definition. Two whole numbers a and b are relatively prime if $GCD(a,b)=1$.
Definition. A fraction $\frac{m}{n}$ is said to be the reduced form of a given fraction $\frac{k}{l}$ if $\frac{k}{l}=\frac{m}{n}$ and m and n are relatively prime. We say such an $\frac{m}{n}$ is in lowest terms, or reduced.
NOTE: Is GCD well-defined (that is, is it true that any two whole numbers have a greatest common divisor)? Proof idea – all whole numbers have at least one divisor d=1, and the set of divisors of a is bounded above by a, so there must be a largest number that divides both.
QUESTION: Is $\frac{1147}{899}$ reduced?
NOTE: unless the numerator and denominator are relatively small, it’s not always easy to tell! If classroom instruction focusses on single-digit numerator/denominator, we get the impression we can always tell “just by looking” if a fraction is reduced.
QUESTION: What’s $GCD(12,0)$? The GCD of any nonzero integer and 0 is the nonzero integer itself.
NOTE: In the past (in our own primary and secondary education, for example, as well as in MAT 2571 Intro to Proofs), we simply accepted that every fraction has a reduced form. Now let’s look at “why”.
Reduced form of a fraction
Theorem 3.1. Every nonzero fraction has a unique reduced form. Furthermore, this reduced form can be obtained by an algorithm.
FIRST: Let’s see if we can find a reduced form of a fraction.
Observe: If $\frac{a}{b}$ is a fraction and $c=GCD(a,b)$. Then $a=cm$ and $b=cn$ for some integers m,n, and the reduced form of $\frac{a}{b}$ is $\frac{m}{n}$.
QUESTION: So, how do we find the GCD? (What is an algorithm?)
Division with remainder
Given positive integers $a$ and $d$, the division-with-remainder of $a$ by $d$ is given by the equation:
$a=q d+r \quad$ where $q, r \in \mathbf{N}$ and $0 \leq r<d$.
Where q is the quotient, d is the divisor, a is the dividend, and r is the remainder.
Linear combinations
An integer k is a linear combination of integers a and b if
$$k=am+bn$$
for some integers m and n. (Also called an integral linear combination since m,n are required to be integers).
The Euclidean Algorithm
Theorem 3.2 (Euclidean algorithm). If a and d are positive integers, then $GCD(a, d)$ can be obtained by a finite number of applications of division-with- remainder. Furthermore, $GCD(a, d)$ is a linear combination of a and d.
Some facts about GCD
Lemma. If m is any integer, then $GCD(a, d) = GCD(a + m\cdot d, d)$
LEMMA 3.3. Given whole numbers $a, q, d$, and $r$ so that $a, d \neq 0$ and $a=q d+r$, the following equality holds:
$$GCD(a, d)=GCD(d, r)$$
Example: Find $GCD(897,221)$.
Example: Find $GCD(10049,1190)$ and write the GCD as a linear combination of $10049$ and $1190$.
QUESTION: Does this work for any pair of integers? How do we know the process will eventually terminate?
3.2 The Fundamental Theorem of Arithmetic
Primes
Definition. A proper divisor of a whole number a is an is a divisor of a which is strictly between 1 and a, (that is, a divisor d of a with $1<d<a$).
Definition. A whole number >1 with no proper divisors is called a prime number.
Definition. A whole number >1 that is not prime is called composite.
The following theorem shows that prime numbers are the basic building blocks of whole numbers when it comes to multiplication.
Fundamental theorem of arithmetic
THEOREM 3.6 (Fundamental theorem of arithmetic). Every whole number $n \geq 2$ is the product of a finite number of primes: $n=p_{1} p_{2} \cdots p_{k}$ (the $p_{i}$ ‘s are not necessarily distinct). Moreover, this collection of primes $p_{1}, \ldots, p_{k}$, counting the possible repetitions, is unique.
We call $n=p_{1} p_{2} \cdots p_{k}$ the prime decomposition of n.
NOTE: This theorem has two parts, existence of a prime decomposition and uniqueness of the prime decomposition.
SKETCH of existence: start with n, if it’s prime we are done, if not it is composite so it has at least one prime factor p. Factor out p and repeat with what remains.
For Uniqueness, why do we care so much about uniqueness? Consider non-uniqueness of factorizations without the prime requirement:
$$4410 = 2\times 9\times 45 = 42 \times 105$$
What is it about primes that forces the prime decomposition to be unique??
The Fundamental Theorem of Arithmetic gives us a new perspective which, if we know the prime decompositions of the two numbers, is extremely useful for extracting information from the two numbers..
Example: Consider the numbers 129212216 and 213541888.
- Are they relatively prime?
- Find their Greatest Common Divisor.
- Find their Least Common Multiple.
Example (cont’d): What if we are given the prime factorizations of the two numbers, $129212216=2^3\times7^5\times31^2$ and $213541888=2^10\times7\times31^3$? Does this help us? How?
Finally, I’d like to look at some remarks by Wu on the content of this chapter – in particular, the fact that we present several proofs that would not realistically appear in a secondary school classroom
Leave a Reply