{ "cells": [ { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "

\n", "Abstract Algebra: An Interactive Approach, 2e\n", "

\n", "\n", "

\n", "\n", "\n", "\n", "

\n", "Chapter 0
\n", "Preliminaries\n", "

\n", "\n", "

Initialization: This cell MUST be evaluated first:

" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "%display latex\n", "try:\n", " load('absalgtext.sage')\n", "except IOError:\n", " load('/media/sf_sage/absalgtext.sage')" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "The above command should automatically be evaluated as the worksheet is loaded. As long as a blue \"Initialization Done\" message appears at the bottom, we are ready to proceed.

\n", "\n", "The very first time this package is run, it may require additional databases to be downloaded from the internet. This only takes a few minutes, and only has \n", "to be done once. These databases will be available the next time Sage is run. This particular chapter does not use the databases, but make sure you close Sage and \n", "restart it before loading a different chapter.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "

\n", "Integer Factorization
\n", "Functions
\n", "Modular Arithmetic
\n", "Rational and Real Numbers
\n", "Sage Interactive Problems
\n", "\n", "\n", "

Integer Factorization

\n", "\n", "
\n", "In this section we will explore the basic properties of integers stemming from the prime factorizations.\n", "We will denote the set of all integers,\n", "

{ …, −3, −2, −1, 0, 1, 2, 3, … }

\n", "by the stylized letter ℤ, which stands for the German "Zahl" meaning "number." Rather than saying "n is an integer," we \n", "can succintly say "n is in ℤ." Many of the properties of factorizations refer only to positive integers, which are denoted \n", "ℤ⁺. Thus, we can write n ∈ ℤ⁺ to say that n is a positive integer.

\n", "\n", "We begin by defining a divisor of a number.

\n", "\n", "DEFINITION 0.1
\n", "We say that an integer a is a divisor of an integer b, denoted by a | b, if there is some integer c such that b = a c. \n", "Other ways of saying this is that a divides b, or a is a factor of b, or b is a multiple of a.

\n", "\n", "EXPERIMENT:
\n", "Find the divisors of 30. Don't forget that, according to the definition, we can have negative divisors.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "\n", "We can extend the idea of integer divisors to that of finding the quotient q and remainder r of integer division.\n", "\n", "

\n", " \n", "THEOREM 0.1: The Division Algorithm
\n", "Given any x ∈ ℤ, and any y ∈ ℤ⁺, there are unique integers q and r such that\n", "

x = q y + r and 0 ≤ r < y.

\n", "Click here for the proof.\n", "\n", "

\n", "\n", "All of the proofs in these notebooks are in a separate subsection that can be accessed by clicking on the hyperlink. This allows one to hide the proof until after it has been attempted.\n", "There will be a hyperlink at the end of the proof to bring you back.\n", " \n", "This is a constructive proof, since it gives an algorithm for finding q and r. This proof also demonstrates how to prove that a solution is unique. \n", "We assume there is another solution, and prove that the two solutions are in fact the same.

\n", "\n", "EXAMPLE:
\n", "Find integers q and r such that 849 = 31 q + r, with 0 ≤ r < 31.

\n", "\n", "We can use Mathematica as a calculator. To find the numerical approximation of 849/31, enter
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "N(849/31)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "To evaluate this Sage expression, click on it, and press Shift + Enter. If you are not using CoCalc, you could also click on the expression, \n", "then click on the \"Evaluate\" button that appears.

\n", "\n", "Note that the function N( ) gives the numerical approximation. The largest integer less than this value is q = 27. Then we can compute r to be
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "849 - 27*31" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "The notation for finding the greatest integer function used in this algorithm is\n", "

⌊x⌋ = the greatest integer less than or equal to x.

\n", "\n", "
\n", "EXPERIMENT:
\n", "Find integers q and r such that −925 = 28 q + r, with 0 ≤ r < 28. Note that for negative numbers, \n", "rounding down will cause the number to increase in magnitude.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "We define a prime as an integer that has only two positive factors: 1 and itself. This definition actually allows negative numbers, \n", "such as −5, to be prime. Although this may seem to be a non-standard definition, it agrees with the generalized definition of primes defined in chapters 10 and 12.\n", "The numbers 1 and −1 are not considered to be prime. The goal of this section is to prove that any \n", "integer greater than 1 can be uniquely factored into a product of positive primes.

\n", "\n", "We will begin by proving that every large number has at least one prime factor. This requires an\n", "assumption about the set of positive numbers, known as the Well Ordering Axiom.

\n", "\n", "The Well Ordering Axiom:
\n", "Every non-empty subset of ℤ⁺ contains a smallest element.

\n", "\n", "The reason why this is considered to be an axiom is that it cannot be proven using only arithmetic operations. \n", "(Note that this statement is not true for rational numbers, which have the same arithmetic operations.) \n", "So this self-evident statement is assumed to be true, and is used to prove other properties of the integers.\n", "\n", "

\n", " \n", "LEMMA 0.1
\n", "Every number greater than 1 has a prime factor.

\n", "\n", "Click here for the proof.\n", "\n", "

\n", "Not only does the proof of Lemma 0.1 demonstrate how the well ordering axiom is used, it also introduces an important strategy in proofs. Notice that to prove that every number \n", "greater than 1 had a prime factor, we assumed just the opposite. It was as if we admitted defeat from the very beginning! Yet from this we were able to reach a conclusion \n", "that was absurd―a number without a prime factor that did have a prime factor. This strategy is known as reductio ad absurdum, which is Latin \n", "for "reduce to the absurd." We assume what we are trying to prove is actually false, and proceed logically until we reach a contradiction. The only explanation \n", "would be that the assumption was wrong, which proves the original statement.

\n", "\n", "The prime factorizations lead to an important question. Is there a largest prime number? The Greek mathmatican Euclid answered this question using \n", "reductio ad absurdum in the third century B.C. \n", "\n", "

\n", " \n", "THEOREM 0.2: Euclid's Prime Number Theorem

\n", "\n", "There are an infinite number of primes.

\n", "\n", "Click here for the proof.\n", "\n", "

\n", "In order to prove that every integer greater than 1 has a unique prime factorization, we must first prove that every such number can be expressed as a product of primes. \n", "This is easiest to do using the principle of mathematical induction. This principle stems from the Well Ordering Axiom, and is a powerful tool for proving \n", "statements about integers.\n", "\n", "

\n", " \n", "THEOREM 0.3: Principle of Mathematical Induction

\n", "\n", "Let S be a set of integers containing a starting value a. Suppose that S has the property that the integer n will be \n", "in S whenever all integers between a and n are in S.\n", "Then S contains all integers greater than or equal to a.

\n", "\n", "Click here for the proof.\n", "\n", "

\n", "\n", "To use the principle of induction, we first prove a statement is true for a starting point a.\n", "Then we assume that the statement is true for all integers a ≤ k < n. (Often we will be able to get by with just the previous \n", "case k = n − 1.) This gives us extra leverage to prove the statement is true for n. Here is an example of this principle in action.\n", "\n", "

\n", " \n", "LEMMA 0.2

\n", "\n", "Every integer n ≥ 2 can be written as a product of one or more positive primes.

\n", "\n", "Click here for the proof.\n", "\n", "

\n", "\n", "In order to prove that the prime factorization is unique we will first have to \n", "develop the concept of the greatest common divisor.

\n", "\n", "DEFINITION 0.2
\n", "We define the greatest common divisor (GCD) of two numbers to be the largest\n", "integer that divides both of the numbers. If the greatest common divisor is 1, \n", "this means that there are no prime factors in common. We say the numbers are \n", "coprime in this case. We denote the greatest common divisor of x and y by gcd(x, y).

\n", "\n", "\n", "We can use Sage's gcd function to quickly test whether two numbers are\n", "coprime without having to factor them.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "gcd(138153809229555633320990299469, 145730407810127891189961221324529)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "So Sage can quickly see that these two numbers are coprime, even though the numbers are too large to find the prime factorization.

\n", "\n", "The greatest common divisor can be found in another way, as seen in the following theorem. The proof of this theorem is more difficult than \n", "the previous proofs, since it illustrates a new technique. Go ahead and read the proof of this theorem without trying to prove it on your own. It is still important that you understand \n", "the techniques involved.\n", "\n", "

\n", " \n", "THEOREM 0.4: The Greatest Common Divisor Theorem
\n", "Given two non-zero integers x and y, the greatest common divisor of x and y is the smallest positive integer which can be \n", "expressed in the form\n", "

u x + v y

\n", "with u and v being integers.

\n", "\n", "Click here for the proof.\n", "\n", "

\n", "\n", "Unfortunately, this is a non-constructive proof. Although this theorem proves the \n", "existence of the integers u and v, it does not explain how to compute them. Fortunately, there is an algorithm, known as \n", "the Euclidean Algorithm which does compute u and v.

\n", "\n", "We start by assuming that x > y > 0, since we can consider absolute values if x or y are negative. We then repeatedly use the division \n", "algorithm to find q_i and r_i such that\n", "

x = q₁ y + r₁, 0 ≤ r₁ < y,

\n", "

y = q₂ r₁ + r₂, \n", "0 ≤ r₂ < r₁,

\n", "

r₁ = q₃ r₂ + r₃, \n", "0 ≤ r₃ < r₂,

\n", "

r₂ = q₄ r₃ + r₄, \n", "0 ≤ r₄ < r₃, …

\n", "\n", "Because the integer sequence {r₁, r₂, r₃, …} is decreasing, this will reach 0 in a finite number of steps, \n", "say r_m = 0. Then r_m−1 will be gcd(x, y). We can find the \n", "values for u and v by solving the second \n", "to the last equation for r_m−1 in terms of the previous two remainders r_m−2 and \n", "r_m−3, and then using the previous equations recursively to express r_m−1 in terms of the previous remainders. \n", "This will eventually lead to r_m−1 expressed in terms of x and y, which is what we want. \n", "It helps to put the remainders r_i in parenthesis, as well as x and y, since these numbers are treated as variables.

\n", "\n", "EXAMPLE:
\n", "Find integers u and v such that 144 u + 100 v = gcd(144, 100).

\n", "\n", "Using the division algorithm repeatedly, we have

\n", "\n", "(144) = 1·(100) + (44)
\n", "(100) = 2·(44) + (12)
\n", "(44) = 3·(12) + (8)
\n", "(12) = 1·(8) + (4)
\n", "(8) = 2·(4) + (0).

\n", "\n", "Thus, we see that gcd(144, 100) = 4. \n", "Starting from the second to the last equation, we have

\n", "\n", "(4) = (12) − (8)
\n", " = (12) − [(44) − 3·(12)] = 4·(12) − (44)
\n", " = 4·[(100) − 2·(44)] − (44) = 4·(100) − 9·(44)
\n", " = 4·(100) − 9·[(144) − (100)] = 13·(100) − 9·(144).

\n", "\n", "Thus, we have u = −9 and v = 13.

\n", "\n", "We can use Sage to find the numbers u and v from the greatest common divisor theorom (0.4) as follows:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "xgcd(144, 100)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "This returns a ordered triple. The first number is gcd(x, y), and the other two numbers give one possible set of values for u and v\n", "for which u x + v y = gcd(x, y). (There are in fact other posible solutions.) Note that Sage produced the same solution as was obtained via the Euclidean algorithm. This command works for even larger numbers.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "xgcd(138153809229555633320199029, 14573040781012789119612213)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "We can now start to prove some familiar properties of prime numbers.\n", "\n", "

\n", " \n", "LEMMA 0.3: Euclid's Lemma

\n", "\n", "If a prime p divides a product a b, then either p | a or p | b.

\n", "\n", "Click here for the proof.\n", "\n", "

\n", "\n", "This lemma quickly generalizes using the principle of induction.\n", "\n", "

\n", " \n", "LEMMA 0.4

\n", "\n", "If a prime p divides a product a₁ a₂ a₃ ⋯ a_n, then p divides a_i for some i.

\n", "\n", "Click here for the proof.\n", "\n", "

\n", "\n", "With this lemma, we can finally prove that integer factorization is unique.\n", "\n", "

\n", " \n", "THEOREM 0.5: The Fundamental Theorem of Arithmetic

\n", "\n", "Every integer greater than 1 can be factored into a product of one or more positive primes. \n", "Furthermore, this factorization is unique up to the rearrangement of the factors.

\n", "\n", "Click here for the proof.\n", "\n", "

\n", "\n", "We can have Sage compute to prime factorization for us, using the command factor:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "factor(420)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "If we explore how this factorization is stored,
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "list(_)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "the result is rather cryptic, so it takes a bit of interpretation to understand the answer. Sage returns a sequence of ordered pairs, like (2,2). The \n", "first number in the pair is the prime, and the second number represents the number of times that prime occurred.

\n", "\n", "Integer factorization is a fundamentally difficult problem even with modern technology. As a result, one can easily type in a number that neither Sage, nor any \n", "other computer program, will be able to factor in anything short of an astronomical length of time. The amount of time required is proportional to the square root \n", "of the second largest prime in the factorization. As long as the integers are less than about 40 digits long, \n", "Sage should not have any trouble factoring them. Ironically, the difficulty in factorization will later turn to our advantage!

\n", "\n", "On the other hand, determining whether or not a number is prime can be done quickly in Sage, even if the number has over 200 digits! The Sage command \n", "for testing a prime number is is_prime.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "is_prime(10^200 + 357)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "How can Sage know for certain that this number is prime when it cannot begin to test for all possible factors? The answer lies in abstract algebra. \n", "Using the properties we will discover in this book, it is possible to prove whether or not a number is prime without knowing the factorization. This in turn will have many \n", "applications in internet security and cryptology.\n", "\n", "Even though you were not asked to try to prove the theorems in this section, you should open the subsection and study the proofs. Soon you will be writing proofs like these yourself! \n", "

\n", "\n", "\n", "

Functions

\n", "\n", "
\n", "The concept of a function is central to virtually every branch of mathematics. There are in fact various ways to define a function, but the concept remains the same. \n", "Standard functions in calculus map real numbers to real numbers, but we want to consider a more abstract definition for which the input and output can come from any set.

\n", "\n", "DEFINITION 0.3
\n", "Let A and B be two non-empty sets. A function, or mapping, from A to B is a rule that assigns to every element \n", "of A exactly one element of B. The set A is called the domain of the function, and the set B is called the target. If a \n", "function f assigns to a the element b, we write f(a) = b, and say that b \n", "is the image of a under f.

\n", "\n", "We will use the notation f : A → B to indicate that f is a function from the set A to the set B. The range \n", "of f, or the image of f, is the set\n", "

{y | y = f(x) for some x ∈ A}.

\n", "\n", "This set denoted by either f(A) or Im(f), and is a subset of B.

\n", "\n", "EXAMPLE:
\n", "Let A be the set of integers from 0 to 99, and let B be the set of English letters from a to z. Let ϕ map each integer to the first \n", "letter of the English word for that number. For example, ϕ(4) = f. Then the range of ϕ is the set\n", "

{e, f, n, o, s, t, z}.

\n", " \n", "
\n", "There is often different ways to denote the same element of the set A, so we must be careful that the rule for the function does not depend on the way the element is \n", "expressed. Had we extended the last example to include 100, this could be called either "a hundred" or "one hundred." Another example of an ambiguous \n", "definition is if we assign to each rational number a/b the value 1/b. But by this rule, f(1/2) ≠ f(2/4), even though 1/2 = 2/4. \n", "In order to show that a function is well defined, we must show that if x₁ = x₂, \n", "then f(x₁) = f(x₂).

\n", "\n", "EXPERIMENT:
\n", "Consider the function from the set of rational functions (denoted by ℚ) to itself, given by\n", "

f(a/b) = gcd(a, b)/b.

\n", "Show that this function is well defined.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "Many functions possess special properties that we want to explore.

\n", "\n", "DEFINITION 0.4
\n", "We say that a function f : A → B is injective, or one-to-one, if the only way in \n", "which f(x) = f(y) is if x = y.

\n", "\n", "For example, the function in the experiment is not one-to-one, since f(1/3) = f(2/3). In order to prove that a function is one-to-one, \n", "we assume that f(x) = f(y), and try to prove that x = y.

\n", "\n", "EXAMPLE:\n", "Consider the function f : defined by ℤ → ℤ defined by

\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "

f(x) =	⎧	x + 3	if x is even,
	⎨
	⎩	2 x	if x is odd.

\n", "Show that f(x) is one-to-one.

\n", "\n", "We assume that f(x) = f(y), and work to show that x = y. Because of the way that f(x) is defined, \n", "there are several cases to consider.

\n", "\n", "Case 1) Both x and y are even. Then since f(x) = f(y), x + 3 = y + 3, which \n", "implies that x = y.
\n", "\n", "Case 2) Both x and y are odd. Then since f(x) = f(y), 2 x = 2 y, so again x = y.
\n", "\n", "Case 3) x is even, and y is odd. Then f(x) = f(y) implies that x + 3 = 2 y, \n", "or x = 2 y − 3. \n", "But this implies that x is odd, and we started out assuming that x is even. Thus, this case can never happen.
\n", "\n", "Case 4) x is odd, and y is even. This is a mirror image of case 3, so we find that this case also can never happen.

\n", "Thus, we have shown in all cases for which f(x) could equal f(y), then x = y. Hence f is one-to-one.

\n", "\n", "We can also ask whether the range and the target of a given function are the same set.

\n", "\n", "DEFINITION 0.5
\n", "We say that a function f : A → B is surjective, or onto, if for every b ∈ B there is at least \n", "one a ∈ A such that f(a) = b. If a function is both one-to-one and onto, it is called a bijection.

\n", "\n", "EXAMPLE:
\n", "Determine whether the function in the last example is onto.

\n", "\n", "Since f(0) = 3, f(1) = 2, f(2) = 5, f(3)=6, f(4) = 7, f(5) = 10, …, it seems that f(x) is never 4. \n", "Let us suppose that f(x) = 4 and reach a contradiction.

\n", "\n", "Case 1) x is even. Then x + 3 = 4, so x = 1. But this contradicts that x is even.
\n", "Case 2) x is odd. Then 2 x = 4, so x = 2. But this contradicts that x is odd.

\n", "Since all cases reach a contradiction, we see that f(x) ≠ 4, and so the function is not onto.

\n", "\n", "Often our functions will be defined on finite sets. In these cases, it is easy to determine whether or not a function is onto if we have already proven that it is one-to-one.

\n", "\n", "DEFINIITION 0.6
\n", "For a finite set A, we denote the number of elements in the set by |A|. If A is infinite, we write |A| = ∞.

\n", "\n", "

\n", " \n", "LEMMA 0.5

\n", "\n", "Let f : A → B be a function that is both one-to-one and onto, and suppose that A is a finite set. \n", "Then |A| = |B|.

\n", "\n", "Click here for the proof.\n", "\n", "

\n", "\n", "We can now prove an important principle that will help us to show whether a function is onto.\n", "\n", "

\n", " \n", "THEOREM 0.6: The Pigeonhole Principle

\n", "\n", "Let f : A → B be a function from a finite set A to a finite set B. \n", "If |A| = |B| and f is one-to-one, then it is also onto.

\n", "\n", "Click here for the proof.\n", "\n", "

\n", "\n", "We will often need to apply two functions in succession, creating a new function.

\n", "\n", "DEFINITION 0.7
\n", "Let f : B → C and g : A → B be two functions. Then the \n", "mapping (f ∘ g): A → C is defined by\n", "

(f ∘ g)(x) = f(g(x)) for all x ∈ A.

\n", "\n", "Note that in f ∘ g, we apply the g function first, and then f. Some textbooks \n", "have f ∘ g = g(f(x)), so care must be taken when referring to other texts.

\n", "\n", "EXAMPLE:
\n", "Let \n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "

f(x) =	⎧	x + 3	if x is even,	and g(x) =	⎧	3 x	if x is even,
	⎨				⎨
	⎩	2 x	if x is odd,		⎩	x − 1	if x is odd.

\n", "Compute f ∘ g and g ∘ f.

\n", "\n", "For each computation, we need to consider the case x even and x odd separately. To \n", "find (f ∘ g)(x) = f(g(x)):

\n", "Case 1) x is even. Then g(x) = 3x, which will also be even. Thus, f(g(x)) = 3x + 3.
\n", "Case 2) x is odd. Then g(x) = x − 1, which will be even, so f(g(x)) = x + 2. Thus,

\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "

f ∘ g =	⎧	3x + 3	if x is even,
	⎨
	⎩	x + 2	if x is odd.

\n", "To find (g ∘ f)(x), we also have to consider two cases.

\n", "Case 1) x is even. Then f(x) = x + 3, which will be odd. So g(f(x)) = x + 2.
\n", "Case 2) x is odd. Then f(x) = 2x, which will be even. So g(f(x)) = 6x. Thus,

\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "

g ∘ f =	⎧	x + 2	if x is even,
	⎨
	⎩	6 x	if x is odd.

\n", "
\n", "Note that in this case, f ∘ g ≠ g ∘ f. However, if we have three functions, \n", "with f : C → D, g : B → C, and h : A → B, \n", "then (f ∘ g) ∘ h = f ∘ (g ∘ h), since both of these expressions \n", "represent f(g(h(x))).

\n", "\n", "If f(x) is both one-to-one and onto, then we will be able to define the inverse function of f.\n", "\n", "

\n", " \n", "PROPOSITION 0.1
\n", "\n", "Let f : A → B be both one-to-one and onto. Then \n", "there exists a unique function g : B → A such that g(f(x)) = x for all x in A, \n", "and f(g(y)) = y for all y ∈ B.

\n", "\n", "Click here for the proof.\n", "\n", "

\n", "\n", "DEFINITION 0.8
\n", "The unique function in Proposition 0.1 is called the inverse function of f(x), and is denoted by f^-1(y).

\n", "\n", "EXAMPLE:
\n", "Consider the function f : ℤ → ℤ given by\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
f(x) = ⎧ x + 3 if x is even,
⎨
⎩ x − 1 if x is odd.
\n", "Show that this is both one-to-one and onto, and find f^-1(y).

\n", "\n", "If f(x) = f(y), the only interesting case is if x is even, and y is odd. Then x + 3 = y − 1, \n", "or y = x + 4, which would be even, not odd. Likewise, case where x is odd and y is even leads to a contradiction. \n", "Thus, x = y, and f is one-to-one.

\n", "\n", "To show that f is onto, we must show that for every y, there is an x so that f(x) = y. \n", "We break this into two cases.

\n", "Case 1) y is even. Then y + 1 will be odd, so f(y + 1) = (y + 1) − 1 = y.
\n", "Case 2) y is odd. Then y − 3 is even, so f(y − 3) = (y − 3) + 3 = y.

\n", "In both cases, we found an x so that f(x) = y. In the process of determining that f is onto, we computed the inverse.

\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
f^-1(y) = ⎧ y + 1 if y is even,
⎨
⎩ y − 3 if y is odd.
\n", "
\n", "So far we have only considered functions with one input variable. But we could also consider functions with two input variables, f(x, y). \n", "For simplicity we will only consider the cases where x and y come from the same set, which is also the target set.

\n", "\n", "DEFINITION 0.9
\n", "Let A be a non-empty set. A binary operation is a function that assigns to every x and y in A an element z in A.

\n", "\n", "Although we could denote a binary operation as z = f(x, y), we will typically denote the operation by the infix \n", "notation z = x ∗ y. The symbol ∗ does not always mean multiplication, but its definition depends on the binary operation. Often we will use a dot (·) instead of the asterisk, depending on the context.

\n", "\n", "EXAMPLE:
\n", "Define the binary operation x ∗ y defined on the set ℤ by\n", "

x ∗ y = x + y + x y.

\n", "Show that (x ∗ y) ∗ z = x ∗ (y ∗ z).

\n", "\n", "Note that\n", "

(x ∗ y) ∗ z = (x + y + x y) ∗ z = x \n", "+ y + x y + z + (x + y + x y)z
\n", "= x + y + z + x y + x z + y z + x y z.

\n", "

x ∗ (y ∗ z) = x * (y + z + y z) = \n", "x + y + z + y z + x(y + z + y z)
\n", "= x + y + z + x y + x z + y z + x y z.

\n", "\n", "Thus, we see that (x ∗ y) ∗ z = x ∗ (y ∗ z).

\n", "\n", "DEFINITION 0.10
\n", "Let ∗ be a binary operation defined on a set A. We say that a subset B of A is closed with respect to ∗ if whenever \n", "both x and y are in B, then x ∗ y is in B.

\n", "\n", "EXPERIMENT:
\n", "Let ∗ be the binary operation of the last example. Show that the subset of odd integers is closed with respect to ∗.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "\n", "

Modular Arithmetic

\n", "\n", "
\n", "\n", "There is an important operation on the set of integers ℤ that we will use throughout the book, based on the division algorithm. It is an abstraction of a counting method \n", "often used in every day life. For example, using standard 12 hour time, if it is 7:00 now, what time will it be 8 hours from now? The answer is not 15:00, since clock \n", "time "wraps around" every 12 hours, so the correct answer is 3:00. This type of arithmetic that "wraps around" is called modular arithmetic. We formally define \n", "modular arithmetic as follows.

\n", "\n", "DEFINITION 0.11
\n", "Let x, y ∈ ℤ, with y > 0. We define the operator\n", "

x mod y,

\n", "pronounced "x modulo y", to be the unique value r from the division algorithm, which selects q and \n", "0 ≤ r < y such that x = q y + r. The number y is called the modulus.

\n", "\n", "The mod operation is almost, but not quite, a binary operation on ℤ, since it is not defined if y = 0. Since there is a difference of opinion \n", "as to how the operator should be defined for y < 0, we will only use the operator for y > 0.

\n", "\n", "EXAMPLE:
\n", "Compute 8342 mod 43.

\n", "\n", "Since 8342 = 194·43 + 6, we see that 8342 mod 43 = 6.

\n", "\n", "For numbers this large, we will use Sage to help. We use the % symbol for the mod operator.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "743532645703453453463 % 257275073624623" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "Sometimes the modulo operation is very easy to compute. For any positive x, x mod 10 will be the last digit in the decimal \n", "representation of the number. There are other tricks for small values of y.

\n", "\n", "A familiar property of standard arithmetic is that the last digit of the sum and product of two positive numbers x and y can be computed using only the \n", "last digits of x and y. This can be generalized in the following proposition.\n", "\n", "

\n", "\n", "PROPOSITION 0.2
\n", "If x, y, and n are integers with n > 0, then\n", "

(x + y) mod n = \n", "((x mod n) + (y mod n)) mod n,

\n", "and \n", "

(x y) mod n = \n", "((x mod n)·(y mod n)) mod n.

\n", "\n", "Click here for the proof.\n", "\n", "

\n", "\n", "We can use Proposition 0.2 to compute powers modulo n. Since raising a number to an integer power is equivalent to repeated multiplication, we see that \n", "

(x^y) mod n = \n", "(x mod n)^y mod n.

\n", "\n", "EXAMPLE:
\n", "Compute 234⁵ mod 29.

\n", "\n", "Since 234 mod 29 = 2, the answer is the same as 2⁵ mod 29, and 32 mod 29 = 3.

\n", "\n", "WARNING: It is not true that \n", "

(x^y) mod n = \n", "(x mod n)^{(y mod n)} mod n.

\n", "\n", "That is, we cannot apply the modulus to an exponent. However, there is a trick for simplifying a power in the case that the exponent is large—using the binary \n", "representation of the exponent y. The procedure is best explained by an example.

\n", "\n", "EXAMPLE:
\n", "Compute 25³⁵ mod 29.

\n", "\n", "The number 25³⁵ is 49 digits long, and the base is already smaller than the modulus, so there is no obvious way of simplifying the expression. By looking at the \n", "binary representation of 35, we find that 35 = 32 + 2 + 1. Thus,\n", "

25³⁵ = 25³²·25²·25¹.

\n", "\n", "In order to compute 25³² mod 29, we can square the number 5 times.\n", "\n", "

25² mod 29 = 625 mod 29 = 16,
\n", " 25⁴ mod 29 = 16² mod 29 = 256 mod 29 = 24,
\n", " 25⁸ mod 29 = 24² mod 29 = 576 mod 29 = 25,
\n", " 25¹⁶ mod 29 = 25² mod 29 = 625 mod 29 = 16,
\n", " 25³² mod 29 = 16² mod 29 = 256 mod 29 = 24.

\n", "\n", "Finally, we see that \n", "

25³⁵ mod 29 = 25³²·25²·25¹ mod 29 = 24·16·25 mod 29 = 9600 mod 29 = 1.

\n", "Note that we never had to deal with numbers more than 4 digits long.

\n", "\n", "The Sage command PowerMod(x, y, n) uses this algorithm to compute x^y mod n.

\n", "\n", "EXAMPLE:
\n", "Use Sage to find 743532645703453453463^{42364872163462467234} mod 2572750736246233264872.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "PowerMod(743532645703453453463, 42364872163462467234, 2572750736246233264872)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "Note that Sage was able to do this computation fast. We will see that the ability for computers to quickly compute large powers modulo n has applications \n", "in internet security.

\n", "\n", "There is another property of modular arithmetic involving coprime numbers \n", "that will be used often \n", "throughout the book, known to the ancient Chinese since before 240 C.E.\n", "\n", "

\n", "\n", "THEOREM 0.7: The Chinese Remainder Theorem
\n", "If x and y in ℤ⁺ are coprime, then given any a and b in ℤ, there is a unique k in ℤ \n", "such that\n", "

0 ≤ k < x y,

\n", "

k mod x = a mod x, and

\n", "

k mod y = b mod y.

\n", "\n", "Click here for the proof.\n", "\n", "

\n", "\n", "This is a constructive proof, since it gives us a formula for finding the value of k.

\n", "\n", "EXAMPLE:
\n", "Find a non-negative number k less than 210 such that\n", "

k mod 14 = 3, and
\n", " k mod 15 = 7.

\n", "Since 14 and 15 are coprime, we begin by finding u and v such that 14 u + 15 v = 1. But there is the obvious solution\n", "

14 (−1) + 15 (1) = 1.

\n", "Then we compute k to be a v y + b u x = 3·15 + 7·(−14) = −53. But since this is negative, we can add 14·15 to get another \n", "solution, 157.

\n", "\n", "There is a Sage command crt(a, b, x, y) that finds k given the 2 sets {a, b} and {x, y}.

\n", "\n", "EXAMPLE:
\n", "Use Sage to find a number k such that \n", "\n", "

k mod 771234712398742343 = 573457203572345239 and
\n", "k mod 642374682348623642 = 568134658235924534.

" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "crt(573457203572345239, 568134658235924534, 771234712398742343, 642374682348623642)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "We can verify that this solution is correct.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "155720011750587503187230769057470234 % 771234712398742343" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "155720011750587503187230769057470234 % 642374682348623642" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "The Chinese remainder theorem has many applications. One of these is in the distribution of classified information among two or more people in such a way so that no one \n", "person can see the information. Each would receive one of the two (or more) modulus conditions, which is not enough information to determine the number k. Only when \n", "all of the pieces of the problem are assembled can k be determined, which can be decoded.

\n", "\n", "Another application is in solving linear congruence equations of the form\n", "

(a x) mod n = b.

\n", "This can be solved by letting k = a x. Then\n", "

k mod a = 0, and
\n", "k mod n = b.

\n", "Since k is known, we can find x.

\n", "\n", "EXAMPLE:
\n", "Solve the linear congruence equation\n", "

12 x mod 19 = 3.

\n", " \n", "We need to solve k mod 12 = 0 and k mod 19 = 3. Thus, we must first find a u and v such \n", "that 12 u + 19 v = 1. Using the Euclidean algorithm, we find that \n", "

8·12 + (−5)·19 = 1.

\n", "Using these values of u and v, we have that \n", "

k = a v y + b u x = 0·(−5)·19 + 3·8·12 = 192.

\n", "Finally, x = 12 k, so x = 24. Note that we can add or subtract multiples of 19 to get other solutions, so x = 5 also \n", "works.
\n", "\n", "\n", "

Rational and Real Numbers

\n", "\n", "Having studied the properties of integers, let us turn our attention to rational numbers and real numbers. The set of rational numbers ℚ can be described as the numbers of the form p/q, where p is an integer and q is a positive integer.

\n", "\n", "Although the group ℚ is easy to define, it is often hard to visualize. One way to illustrate the rationals graphically can be seen by executing the following Sage\n", "command:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "ShowRationals(-5, 5)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "This plot helps to visualize the rational numbers from −5 to 5 using a sequence of rows. The n^th row represents the rational numbers in simpliest form \n", "whose denominator is equal to n. Thus, the first row represents the integers, the second row the half integers, and so on. Each row is drawn three-fourths closer \n", "to the x-axis than the previous row. In principle there would be an infinite number of rows, getting closer and closer to each other as they get close to \n", "the x-axis.

\n", " \n", "Even though this plot does not show all of the rational numbers (since there are an infinite number of them), we can zoom in on this graph to see more detail. Simply \n", "use different upper and lower bounds. For example, we can zoom in on the apparent "gap" close to the origin:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "ShowRationals(0, 0.1)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "This picture seems to indicate that there are not any rationals between 0 and about 0.04. Is this true?

\n", " \n", "EXPERIMENT:
\n", "Change the 0 and 0.1 in the above command to zoom in even closer on this gap. Try to find an interval in which there are no points plotted in the graph. Can you find \n", "an interval without any rational numbers?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "

\n", "In doing this experiment you not only might make a discovery about rational numbers, but you might even be able to see why this property is true.\n", " \n", "

\n", "\n", "PROPOSITION 0.3
\n", "If a and b are any two different real numbers, then there is a rational number between a and b.

\n", "\n", "Click here for the proof.\n", "\n", "

\n", "It is not hard to extend this proposition to show that between any two numbers, there are in fact an infinite number of rational numbers.

\n", " \n", "There are some other properties of the rational numbers that are suggested by the Sage plot. Here is the plot again, from −5 to 5:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "ShowRationals(-5,5)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "Having all of these dots on a page may tempt one to play "dot to dot" to see if a picture forms. In this case there may not be a picture, but perhaps some \n", "pattern can be formed by connecting these dots. Go ahead and try it!

\n", " \n", "EXPERIMENT:
\n", "Make a printout of the above plot and try to find a way to start at one point, then connect all of the dots using a sequence of straight lines. Try to keep the path \n", "from crossing itself. The aim is not just to connect the dots which are printed, but to created a pattern which, when continued indefinitely, will eventually hit \n", "every rational number no matter how close to the x-axis it appears, or how far to the left or right of the origin it is. There are, in fact, many ways this can \n", "be done.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "

\n", "What does this experiment show? When we are connecting the dots together, we are, in fact, forming a sequence of rational numbers. By finding a way to connect \n", "the dots so that every rational number is eventually hit, we have found an infinite sequence that includes every rational number once and only once. In other words, there \n", "are just as many rational numbers as there are integers! This is at first surprising since we just saw that there are many more rationals, in fact an infinite number of \n", "them between any two.

\n", " \n", "DEFINITION 0.12
\n", "A set S is called countable if there is an infinite sequence of elements from the set that includes every member of the set.

\n", "\n", "\n", "What do sequences have to do with comparing the sizes of two sets? A sequence can be considered as a function between the set of positive integers and the set S. \n", "If a sequence manages to include every member of the set S, then it stands to reason that there are at least as "many" positive integers as there are \n", "elements of S. The shocking fact is that even though it would first appear that there must be infinitely many more rational numbers than integers, in fact the two \n", "sets have the same size.\n", "\n", "

\n", "\n", "PROPOSITION 0.4
The set of rationals forms a countable set.

\n", "\n", "Click here for the proof.\n", "\n", "

\n", "Even though we have shown that there are an infinite number of rational numbers between any two numbers, the natural question to ask is whether there are numbers that are \n", "not rational. The first discovery of a number that was not rational was the square root of two, proven by the Greeks.\n", "\n", "

\n", "\n", "PROPOSITION 0.5
\n", "There is no rational number p/q such that (p/q)² = 2.

\n", "\n", "Click here for the proof.\n", "

\n", "\n", "\n", "This proof is another example of a reductio ad absurdum proof. That is, we assume that the statement we were trying to prove was false, and proceeded until we reach \n", "a contradiction.

\n", " \n", "If real numbers which are not rational are called irrational numbers. Irrational numbers are characterized by the fact that their decimal representation never repeats. \n", "With Sage, we can look at as many digits of √2 as we want, and see that there is no pattern. Here are \n", "the first 1000 digits.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "N(sqrt(2), digits = 1000)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "We will denote the set of real numbers, both rational and irrational, by ℝ.

\n", "\n", "We have already proven that there is, in essence, the same number of rational numbers as integers. This may not come as too much of a shock, since both sets are infinite, \n", "so logically two infinite sets ought to be the same size. But the set of real numbers is also infinite, so one might be tempted to think that there is the same number of \n", "real numbers as integers. However, the number of reals is \"more infinite\" than the number of integers. In other words, we cannot construct a sequence of real numbers \n", "that contains every real number, as we did for rational numbers. This surprising fact was proved by Georg Cantor using a classic argument.\n", "\n", "

\n", "\n", "THEOREM 0.8: Cantor's Diagonalization Theorem
\n", "The set of all real numbers between 0 and 1 is uncountable. That is, there cannot be a sequence of numbers that contains every real number between 0 and 1.

\n", "\n", "Click here for the proof.\n", "\n", "

\n", "We will use the sets ℚ and ℝ throughout this book, so knowing the properties of these two sets will be important in many of the examples.\n", "\n", "

\n", "\n", "

Proofs:

\n", "\n", "\n", "\n", "Proof of Theorem 0.1:

\n", "\n", "Since y > 0, we can consider the rational number x/y. Let q be the largest integer that is less than or equal to x/y. \n", "That is, we will pick the integer q so that\n", "

q ≤ x/y < q + 1.

\n", "Multiplying by y, we have \n", "

y q ≤ x < y q + y.

\n", "If we let r = x − y q, we have 0 ≤ r < y, and also x = y q + r, so we have found \n", "integers q and r that satisfy the required properties.

\n", "\n", "In order to show that q and r are unique, let us suppose that q and \n", "r are two other integers that satisfy the required conditions. \n", "Then q y + r = q y + r, so\n", "

(q − q)y = r − r.

\n", "Since both r and r are between 0 and y − 1, the right hand side is less than y in absolute \n", "value. But the left hand side is at least y in absolute value unless q = q. This in turn will \n", "force r = r, so we see that the solution is unique.

\n", " \n", "Return to text\n", "\n", "

\n", " \n", "\n", "\n", "Proof of Lemma 0.1:

\n", " \n", "Suppose that some number greater than 1 does not have a prime factor. Then we consider the set of all integers greater than 1 which do not have a prime factor, and using the \n", "well ordering axiom, we find the smallest such number, called n. Then n is not prime, otherwise n would have a prime factor. Then by \n", "definition, n must have a positive divisor besides 1 and n, say m. Since 1 < m < n, and n was the smallest number \n", "greater than 1 without a prime factor, m must have a prime factor, say p. Then p is also a prime factor of n, so we have a contradiction. \n", "Therefore, every number greater than 1 has a prime factor.

\n", " \n", "Return to text\n", "\n", "

\n", " n\n", "\n", "\n", "Proof of Theorem 0.2:

\n", " \n", "Suppose that there are only a finite number of prime numbers. Label these prime numbers\n", "

p₁ = 2, p₂ = 3, p₃ = 5, p₄ = 7, …, \n", "p_n.

\n", "Now consider the number \n", "

m = (2·3·5·7·11·13···p_n) + 1.

\n", "This number is odd, so it cannot be divisible by 2. Likewise, m is one more than a multiple of 3, so it is not divisible by 3. In this way we see that m \n", "is not divisible by any of the prime numbers. But this is ridiculous, since m must have a prime factor by Lemma 0.2. Thus, the original assumption that there is \n", "a largest prime number is false, so there are an infinite number of prime numbers.

\n", " \n", "Return to text\n", "\n", "

\n", " \n", "\n", "\n", "Proof of Theorem 0.3:

\n", " \n", "Suppose there is some integer greater than a which is not in S. Let T be the set of integers greater than a but are not in S. \n", "Since T is non-empty, by the well ordering axiom we can let n be the smallest member of T. Note that n ≠ a, \n", "since a is in S. \n", "Also, all integers between a and n would have to be in S, lest there be a smaller value in T. But by the property of S, n would \n", "have to be in S, hence not in T. This contradiction shows that there is no integer greater than a that is not in S, which is equivalent to saying all \n", "integers greater than or equal to a are in S.

\n", " \n", "Return to text\n", "\n", "

\n", "\n", "\n", "\n", "Proof of Lemma 0.2:

\n", " \n", "In this case, our starting point is 2, so let us prove that statement is true for n = 2. Since 2 is prime, we can consider 2 to be the product of one prime, so we \n", "are done.

\n", "\n", "Let us now assume the statement is true for all integers 2 ≤ k < n, and work to prove the statement is true for the case n. If n is prime, \n", "we have n as the product of one prime. If n is not prime, then we can express n = a b, where both a and b are between 1 \n", "and n. By our assumption, a and b can both be expressed as a product of positive primes, and so n can also be expressed as a product of \n", "primes. Thus, by mathematical induction, the statement is true for all n ≥ 2.

\n", " \n", "Return to text\n", "\n", "

\n", " \n", "\n", "\n", "Proof of Theorem 0.4:

\n", " \n", "Let A denote the set of all positive numbers that can be expressed in the form u·x + v·y. Note that both \n", "|x| and |y| can be written in the form u·x + v·y, so we can consider the smallest positive number \n", "n that can be written in the form u·x + v·y. Note that gcd(x, y) is a factor of both \n", "x and y, so gcd(x, y) must be a factor of n.

\n", "\n", "By the division algorithm (Theorem 0.1), we can find q and r, with 0 ≤ r < n, such that x = q n + r. Then\n", "

r = x − q n = x − q (u x + v y) = (1 − q u)x \n", "+ (−v)y,

\n", "which is in the set A. If r ≠ 0, then r would be a smaller positive number in A than n, which contradicts the way we \n", "chose n. Thus, r = 0, and n | x. By a similar reasoning, n is also a divisor of y. \n", "Thus, n is a common divisor of x \n", "and y, and since the gcd(x, y) is in turn a divisor of n, n must be equal to gcd(x, y).

\n", " \n", "Return to text\n", "\n", "

\n", "\n", "\n", "\n", "Proof of Lemma 0.3:

\n", " \n", "Suppose that p ∤ a, so that p and a are coprime. By the greatest common divisor theorem (0.4), there exist \n", "integers u and v such that u a + v p = 1. Then\n", "\n", "

u a b + v p b = b.

\n", " \n", "Since p divides both terms on the left hand side, we see that p | b. Thus, p must divide either a or b.

\n", " \n", "Return to text\n", "\n", "

\n", "\n", "\n", "\n", "Proof of Lemma 0.4:

\n", " \n", "We will use induction on n. The starting case n = 2 is covered by Euclid's Lemma (0.3). Let us suppose the theorem is true for the case n − 1. \n", "That is, if p divides a₁ a₂ a₃ ⋯ a_n−1, then p divides \n", "a_i for some i. If we let b = \n", "a₁ a₂ a₃ ⋯ a_n−1, \n", "then a₁ a₂ a₃ ⋯ a_n = b a_n. By Euclid's Lemma (0.3), \n", "if p divides b a_n, then p divides either b or a_n. But if p divides b, then by \n", "induction p divides a_i for some 1 ≤ i ≤ n − 1. So it either case, p divides a_i for \n", "some 1 ≤ i ≤ n.

\n", " \n", "Return to text\n", "\n", "

\n", " \n", "\n", "\n", "Proof of Theorem 0.5:

\n", " \n", "Lemma 0.2 shows that all integers greater than 1 can be expressed as a product of positive primes. So we only have to show uniqueness. That is, we must show that if\n", "

p₁ p₂ p₃ ⋯ p_n = \n", "q₁ q₂ q₃ ⋯ q_m,

\n", "\n", "where p₁, p₂, … p_n, q₁, q₂, … q_m are all \n", "positive primes, then n = m, and the q_i are a rearrangement of the p_i. We will use induction on n, \n", "the number of prime factors in the first factorization.

\n", "\n", "If n = 1, then p₁ = q₁ q₂ q₃ ⋯ q_m, and \n", "since p₁ is prime and cannot have more than one factor, we must have m = 1, and so p₁ = q₁.

\n", "\n", "By Lemma 0.4, since p_n | q₁ q₂ q₃ ⋯ q_m, p_n must \n", "divide one of the q_i's. Since p_n and q_i are both positive primes, we find that p_n = \n", "q_i. By rearranging the remaining q's, we can write\n", "

p₁ p₂ p₃ ⋯ p_n = \n", "q₁ q₂ q₃ ⋯ q_m−1 p_n.

\n", " \n", "Thus, \n", "

p₁ p₂ p₃ ⋯ p_n−1 = \n", "q₁ q₂ q₃ ⋯ q_m−1.

\n", "\n", "By induction we can assume that the statement is true for the case n − 1, and so n − 1 = m − 1, hence n = m, and \n", "the q_i are a rearrangement of the p_i.

\n", " \n", "Return to text\n", "\n", "

\n", "\n", "\n", "\n", "Proof of Lemma 0.5:

\n", " \n", "We will use induction on the size n = |A|. If A has only one element, a₁, then f(a₁) = b₁, \n", "and B = {b₁}. Let us suppose that the statement is true for n − 1.

\n", "\n", "If A = {a₁, a₂, a₁, … a_n}, then f(a_n) = b for \n", "some b ∈ B. If we let A = A − {a_n}, that is, we remove the \n", "element a_n from the set A, and B = B − {b}, then we can define the \n", "function f : A → B by f(x) = \n", "f(x) for x ∈ A. Since f is a bijection, so \n", "is f, since no other element of A could map to b. By induction, we see \n", "that |A| = |B|, and so |A| = |B|.

\n", " \n", "Return to text\n", "\n", "

\n", " \n", "\n", "\n", "Proof of Theorem 0.6:

\n", " \n", "Let B be the range of f. Then the function f : A → B would be both one-to-one and onto, so by Lemma 0.5 we \n", "have |A| = |B|. Since we also have \n", "that |A| = |B|, then B = B, so the function is onto.

\n", " \n", "Return to text\n", "\n", "

\n", " \n", "\n", "\n", "Proof of Proposition 0.1:

\n", " \n", "Because f is both one-to-one and onto, for every y ∈ B there is a \n", "unique x ∈ A such that f(x) = y. \n", "Thus, we can define g(y) to be that value x such that f(x) = y. \n", "By the way g(y) is defined, we see that f(g(y)) = y for all y ∈ B. If we apply the \n", "function g to both sides of this equation, we have g(f(g(y))) = g(y). \n", "Since every element x ∈ A can be written as g(y) for some y ∈ B, we can \n", "replace g(y) with x to get g(f(x)) = x for all x ∈ A.

\n", "\n", "To show that the function is unique, suppose there is another function h(x) : B → A. Then\n", "

h(y) = h(f(g(y))) = \n", "(h ∘ f)(g(y)) = g(y) for all y ∈ B.

\n", "\n", "Thus, h = g, showing that the function is unique.

\n", " \n", "Return to text\n", "\n", "

\n", " \n", "\n", "\n", "Proof of Proposition 0.2:

\n", " \n", "In both equations, the two sides are between 0 and n − 1, so it is sufficient to show that the difference of the two sides is a multiple of n. \n", "Let a = x mod n, b = y mod n, \n", "c = (x + y) mod n, and d = (x y) mod n. Then there are \n", "integers q₁, q₂, q₃, and q₄ such that \n", "

x = q₁ n + a, y = q₂ n + \n", "b, x + y = q₃ n + c, x y = q₄ n + d.

\n", "For the first equation, we note that \n", "

c − (a + b) = (x + y − q₃ n) − \n", "((x − q₁ n) + (y − q₂ n))
\n", " = q₁ n + q₂ n − q₃ n = (q₁ + \n", "q₂ − q₃) n.

\n", "Thus, the two sides of the first equation differ by a multiple of n. Likewise, for the second equation, we see\n", "

d − a b = (x y − q₄ n) − \n", "(x − q₁ n)·(y − q₂ n)
\n", "= q₁ q₂ n² − y q₁ n − \n", "x q₂ n − q₄ n = (q₁ q₂ n \n", "− y q₁ − x q₂ − q₄) n.

\n", "\n", "So again, the two sides of the second equation differ by a multiple of n.

\n", " \n", "Return to text\n", "\n", "

\n", " \n", "\n", "\n", "Proof of Theorem 0.7:

\n", "We will begin by showing that there cannot be more than one such number.

\n", "\n", "Suppose we have two different numbers, k and m, which satisfy the above conditions. Then\n", "

(k − m) mod x = 0 and \n", "(k − m) mod y = 0.

\n", "Thus, k − m must be a multiple of both x and y. But since x and y are coprime, the \n", "least common multiple of x and y is x y. Thus, k − m is a multiple \n", "of x y.

\n", "\n", "However, both k and m are less then x y. So the only way this is possible is for k − m = 0, \n", "which contradicts our assumption that k and m were distinct solutions.

\n", "\n", "To show that there is a solution, we first note that since x and y are coprime, by the greatest common divisor theorem (0.4), there are \n", "integers u and v such that u x + v y = 1. Then we can consider the number\n", "

k = (a v y + b u x) mod (x y).

\n", " \n", "Clearly 0 ≤ k < x y, so we only have to show that k mod x = a mod x \n", "and k mod y = b mod y. Since v y = 1 − u x,\n", "

k mod x = (a v y + b u x) mod x
\n", " = (a(1 − u x) + b u x) mod x
\n", " = (a + u x(b − a)) mod x = a mod x.

\n", "Likewise, since u x = 1 − v y,\n", "

k mod y = (a v y + b u x) mod y
\n", " = (a v y + b(1 − v y)) mod y
\n", " = ((b + v y(a − b)) mod y = b mod y.

\n", "
\n", " \n", "Return to text\n", "\n", "

\n", "\n", "\n", "\n", "Proof of Proposition 0.3:

\n", "\n", "Let x = |a − b|. Since x is not zero, we let q be any integer that is greater than 1/x. Then \n", "|a·q − b·q| = q·x > 1, so there must be an integer between a·q and \n", "b·q, which we will call p. But then p/q will be between a and b, and the proposition is proved.

\n", "\n", "Return to text

\n", "\n", "

\n", "\n", "\n", "\n", "Proof of Proposition 0.4:

\n", "\n", "In order to show that the rationals are countable, we need a sequence that will eventually contain every rational somewhere in the sequence. \n", "Equivalently, we can connect the dots of the figure formed from
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "ShowRationals(-5,5)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "using a pattern that would, in principle, reach every dot of this figure extended to infinity.There are of course many ways to do this, but one way is given by the patten \n", "in
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CountableQ(5)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "Here is a picture which shows more of this pattern:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CountableQ(9)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "This path starts at 0, and swings back and forth, each time hitting the rationals on the next row. Since there are an infinite number of rows, we can extend this \n", "pattern indefinitely, and every rational number will eventually be hit by this path.This path gives rise the the sequence

\n", " \n", "

{0, 1, 1/2, -1/2, -1, -2, -3/2, -2/3, -1/3, 1/3, 2/3, 3/2, 2, 3, …}

\n", "which contains every rational number, so we have shown that the rationals form a countable set.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "Return to text\n", "\n", "

\n", "\n", "\n", "\n", "Proof of Proposition 0.5:

\n", "\n", "Suppose that there was such a rational number, p/q. Let us further suppose that p/q is in simplest form, so that p \n", "and q are integers with no common factors. We could rewrite the equation (p/q)² = 2 as \n", "

p² = 2 q².

\n", "This would indicate that p² is an even number, which implies that p is even.

\n", "\n", "Next, we make the substitution p = 2r, where r is an integer. This produces the equation\n", "

(2 r)² = 2 q², or

\n", "

2 r² = q².

\n", "This would indicate that q², and hence q, is even. But this contradicts the fact that p/q was written in simplest \n", "form. Thus, there is no rational number whose square is 2.

\n", "\n", "Return to text\n", "\n", "

\n", "\n", "\n", "\n", "Proof of Theorem 0.8:

\n", "\n", "We begin by assuming that we can form such a sequence\n", "

{a₁, a₂, a₃,…}

\n", "and work to find a contradiction. The plan is to find a number b that cannot be in this list. We can do this by forcing b to have a different first \n", "digit than a₁, a different second digit than a₂, a different third digit than a₃, and so on. The only \n", "technical problem with this is that some numbers have two decimal representations, such as
\n", "

0.348600000000000000…= 0.3485999999999999999….

\n", "For these numbers, all we need to do is require that both representations are in the list. (That is, some rational numbers will appear twice on the list \n", "with different decimal representations.)

\n", "\n", "We now can find a number b using any number of procedures, such as letting the n^th digit of b be one more than the n^th digit of \n", "a_n, mod 10. For example, if the list of numbers is

\n", "

a₁ = 0.94837490123798570…

\n", "

a₂ = 0.83840000000000000…

\n", "

a₃ = 0.83839999999999999…

\n", "

a₄ = 0.34281655343424444…

\n", "then b = 0.0499… . Certainly b is missing from the list, since it differs from each member of the list by at least one digit. This contradiction proves \n", "the theorem.

\n", "\n", "Return to text\n", " \n", "

\n", "\n", " \n", "

Sage Interactive Problems

\n", "\n", "
\n", "§0.1 #41)
\n", "Use Sage to find integers u and v such that\n", "

876543212345678 u + 123456787654321 v = 1.

" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "§0.1 #42)
\n", "Use Sage to find integers u and v such that\n", "

98765432123456789 u + 12345678987654321 v = 1.

" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "§0.1 #43)
\n", "Use Sage to find the factorization of 987654321.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "§0.1 #44)
\n", "Use Sage to find the factorization of 12345678987654321.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "§0.1 #45)
\n", "Use Sage to find the factorization of 98765432123456789.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "§0.2 #42)
\n", "Consider the function\n", "

f(x) = 2 ⌊x⌋ − x.

\n", "Sage uses the function floor to denote ⌊x⌋. Thus, we can have Sage plot this function with the commands
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "f(x) = 2*floor(x) - x" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "plot(f(x), [x, 0, 5])" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "Judging by the graph, is this function one-to-one? Is it onto? (Ignore the vertical lines in the graph.)
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "§0.2 #43)
\n", "Define a function g(x) in Sage such that f(g(x)) = x for all x, using the function from Problem 42. Note \n", "that the formula must work for both integers and non-integers. Is g(f(x)) always equal to x?" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "§0.3 #39)
\n", "Use Sage's PowerMod function to compute\n", "

235155792357923947529^{75289347972935390234} mod 4623452735792375925234.

" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "§0.3 #40)
\n", "Use Sage's PowerMod function to compute\n", "

9384572893472723523452^{24523523452345216644} mod 8376258362352836587697.

" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "§0.3 #41)
\n", "Use Sage's crt function to find the solution to the system\n", "

k mod 9243798374502516137 = 237521646243353626,

\n", "and \n", "

k mod 1978654573572351516 = 26325673245684223.

" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "§0.3 #42)
\n", "Use Sage's crt function to find the solution to the system\n", "

k mod 8675612376265160933543 = 152352352346254753548,

\n", "and \n", "

k mod 6226345262345235236201 = 526352346234573523464.

" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "§0.3 #43)
\n", "Use Sage to solve the linear congruence equation\n", "

7289475362034522153 x mod 915156238625161124 = 210982524590982446.

" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "§0.3 #44)
\n", "Use Sage to solve the linear congruence equation\n", "

9357298518686215025 x mod 1965156273498612512 = 1871551633523628256.

" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "§0.4 #25)
\n", "Notice that in the plot of rational numbers between 0.03 and 0.1,
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "S = ShowRationals(0.03,0.1); S" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "that most of the points shown seem to lie on a curve. \n", "Try to find the equation of this curve, using the fact \n", "that each dot is three fourths closer to the x-axis than the previous dot. Verify your answer by replacing the 100*x^2 with your curve, and execute the following\n", "command:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "P = plot(100*x^2, [x, 0.03, 0.1]); P + S" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "(Hint: Scale the function so that f(0.1) = 1.)

" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "§0.4 #26)
\n", "If we begin the sequence in Problem 1 of the textbook with an irrational number, all terms of the sequence will be irrational. Explore what happens if we consider the same \n", "formula, but start with a₀ = √2." ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "a = sqrt(2); a" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "a = Together(1/(1 + 2*floor(a) - a)); a" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\n", "Here, floor(a) calculates ⌊a⌋, and Together rationalizes the denominator. By repeatedly evaluating the last statement, \n", "we can compute the sequence {a₀, a₁, a₂, a₃, …}. Note \n", "that a₆ is √2 plus an integer. When is the next time in the sequence that a_n is an \n", "integer plus √2?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "\n", "\n", "\n", "\n", "" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ ] } ], "metadata": { "kernelspec": { "display_name": "SageMath (stable)", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.14" } }, "nbformat": 4, "nbformat_minor": 0 }