Sep 9-13
By groups, look at:
Suppose have a proposition that makes a “for all” assertion.
Proposition: All odd numbers are prime.
More formally, the proposition says: For all integers \(x\), if \(x\) is odd then \(x\) is prime.
This statement is FALSE if we can find one odd integer \(x\) that is not prime. In other words, if we can show the negation:
There exists an \(x\) such that \(x\) is odd and \(x\) is not prime.
Notice that the negation of “If \(x\) is odd then \(x\) is prime” is “\(x\) is odd and \(x\) is not prime” as we’ve seen before.
Suppose we have a proposition that makes a “there exists” statement.
Proposition: There exist integers \(x\), \(y\), and \(z\) so that \[ 114=x^3+y^3+z^3 \]
To DISPROVE this statement, we need to rule out ALL triples \((x,y,z)\) because the negation would be
Proposition: For all integers \(x\),\(y\), \(z\), we have \[ x^3+y^3+z^3\not= 114. \]
In fact the answer to this question is unknown; after the solution of \(42\), \(114\) is the smallest number where the answer is not known.
Definition: Given two integers \(d\) and \(n\), we say that \(d\) divides \(n\) (or \(n\) is divisible by \(d\)) if there exists an integer \(m\) so that \(n=dm\). We write \(d|n\) to mean “\(d\) divides \(n\)”.
Proposition: Let \(a\), \(b\), and \(c\) be integers.
Proposition: if \(a|b\) and \(b|c\) then \(a|c\).
Proposition: if \(a|b\) and \(a|c\) then \(a|(bx+cy)\) for any integers \(x\) and \(y\). In particular \(a|(b+c)\) and \(a|(b-c)\).
Proposition: if \(a|b\) and \(b|a\) then \(a=b\) or \(a=-b\).
Question: We are using this fact. Let \(k\) and \(m\) be integers such that \(km=1\). Then either \(k=m=1\) or \(k=m=-1\). Why is this true? Prove it.
Proposition: If \(a|b\) and \(b\not=0\), then \(|a|\le|b|\).
Proposition: Let \(a\) and \(b\) be integers, and suppose \(b>0\). Then there are integers \(q\) and \(r\) so that \[a=qb+r\] and \[ 0\le r<b. \] Furthermore, there is only one \(q\) and one \(r\) satisfying these conditions. (We say \(q\) and \(r\) are unique).
Examples:
Suppose \(b=2\). Then this proposition says that any integer \(a\) can be written \[ a=2q+r \] with \(r=0\) or \(r=1\). So this proposition tells us that every number is either even or of the form \(2q+1\) for some integer \(q\).
Suppose \(b=3\). Then this proposition says that any integer \(a\) can be written \[ a=3q+r \] with \(r\in \{0,1,2\}\). In other words, there are three kinds of numbers: those that are divisible by \(3\); those that are of the form \(3q+1\) (meaning they are one more than a multiple of \(3\)) and those of the form \(3q+2\) (meaning they are two more than, or one less than, a multiple of \(3\).
In grade school, we called \(q\) the quotient and \(r\) the remainder when dividing \(a\) by \(b\).
For example, dividing \(7\) into \(25\) gives \(3\) with remainder \(4\). In other words, \(25=7*3+4\).
We want the remainder to be less than the divisor (or we could take more into the quotient)
The Well-ordering principle: Every non-empty set \(S\) of positive integers has a smallest element: that is, there exists (exactly one) \(x\in S\) so that, for all \(y\in S\), \(x\le y\).
THIS IS AN AXIOM!
Another version: Let \(S\) be a set of positive integers. Suppose that, for every \(y\in S\), there exists \(x\in S\) so that \(x<y\). Then \(S\) is empty.
Negation of the original statement: If, for all \(x\in S\), there exists \(y\in S\) so that \(y<x\), then \(S\) is empty.
We have \(a\) and \(b\); we want to divide \(a\) by \(b\) and identify the remainder.
Now suppose \(a=xb+s\) and \(0\le s<b\). Then \(qb+r=xb+s\) so \((q-x)b=s-r\). This tells us that \(b\) divides \(s-r\). Since \(0\le r<b\) and \(0\le s<b\), we know that \(0\le |r-s|<b\). Therefore \(r-s=0\) so \(r=s\), and then \(q=x\). In other words, \(q\) and \(r\) are the only solutions to the equation \(a=qb+r\) with \(0\le r<b\).
The condition that \(a\) be positive is not necessary. Can you re-do the proof if \(a<0\)? You have to fix a few steps.
What is the remainder when \(-257\) is divided by \(11\)? What is the quotient.
Recall that a number is ‘\(5\)-ish’ if it is divisible by \(5\). What does the division algorithm tell you about numbers that are NOT \(5\)-ish?
Definition: Let \(a\) and \(b\) be integers, at least one of which is not zero. An integer \(d\) is a common divisor of \(a\) and \(b\) if \(d|a\) and \(d|b\). The greatest common divisor \(\mathrm{gcd}(a,b)\) of \(a\) and \(b\) is the largest integer among all common divisors of \(a\) and \(b\).
Note that a common divisor of \(a\) and \(b\) must be smaller than \(|a|\) and \(|b|\). So there must be a greatest one. (How is this related to the well ordering principle?)
Some examples:
To prove that an integer \(d\) is a common divisor of \(a\) and \(b\), you must show that \(d|a\) and \(d|b\).
To prove that it is the greatest common divisor of \(a\) and \(b\), you must prove:
The Euclidean Algorithm is a method for finding the greatest common divisor. It is the prototypical example of a “method of descent” in which you take a problem and systematically transform it into easier, but equivalent, problems until the solution becomes obvious.
Euclidean Algorithm
Enter a: 1230
Enter b>0: 54
1230 = 22*54 + 42
54 = 1*42 + 12
42 = 3*12 + 6
12 = 2*6 + 0
GCD = 6Euclidean Algorithm
Enter a: 1029381029
Enter b>0: 1201233111
1029381029= 0* 1201233111 + 1029381029
1201233111= 1* 1029381029 + 171852082
1029381029= 5* 171852082 + 170120619
171852082= 1* 170120619 + 1731463
170120619= 98* 1731463 + 437245
1731463= 3* 437245 + 419728
437245= 1* 419728 + 17517
419728= 23* 17517 + 16837
17517= 1* 16837 + 680
16837= 24* 680 + 517
680= 1* 517 + 163
517= 3* 163 + 28
163= 5* 28 + 23
28= 1* 23 + 5
23= 4* 5 + 3
5= 1* 3 + 2
3= 1* 2 + 1
2= 2* 1 + 0
GCD = 1In each step in Euclid’s algorithm, we replace a pair of numbers \((a,b)\) with \((b,r)\), where \(r\) is the remainder when \(a\) is divided by \(b\). The point is that the greatest common divisor of this new, smaller pair of numbers is the same. Since each time we do this, the numbers get smaller, eventually one of them has to become zero. But the greatest common divisor of \(x\) and \(0\) is \(x\), so at the last step the greatest common divisor is visible.
The key idea is that the replacement of \(a\) and \(b\) by \(b\) and \(r\) does not change the greatest common divisor.
Proposition: Let \(a\) and \(b\) be two integers with \(b\not=0\). Let \(q\) and \(r\) be integers so that \(a=qb+r\). Then \[ \mathrm{gcd}(a,b) = \mathrm{gcd}(b,r) \].
Proof:
Given \(a\) and \(b\) with \(b\not=0\), construct the sequence of remainders where \(r_1\) is the remainder when \(a\) is divided by \(b\), \(r_2\) is the remainder when \(b\) is divided by \(r_1\), and \(r_k\) is the remainder when \(r_{k-2}\) is divided by \(r_{k-1}\).
Proposition: There exists an \(N\) so that \(r_{N}\not=0\) and \(r_{N+1}=0\), and this \(r_{N}=\mathrm{gcd}(a,b)\).
Proof:
See page 31. Given integers \(a\) and \(b\), construct a table:
| a | b | q | |
|---|---|---|---|
| 1 | 0 | a | |
| 0 | 1 | b |
The next row of the table is constructed by 1: divide a by b to get q and r, and write them as follows:
| a | b | q | |
|---|---|---|---|
| 1 | 0 | a | |
| 0 | 1 | b | |
| r | q |
Then fill in the two left most columns by calculating (row-2)-q(row-1).
| a | b | r | q |
|---|---|---|---|
| 1 | 0 | a | |
| 0 | 1 | b | |
| 1 | -q | r | a |
Then repeat this process until you get a zero in the r column.
| a | b | r | q |
|---|---|---|---|
| 1 | 0 | 1534 | 0 |
| 0 | 1 | 87 | 0 |
| 1 | -17 | 55 | 17 |
| -1 | 18 | 32 | 1 |
| 2 | -35 | 23 | 1 |
| > | -3 | 53 | 9 |
| 8 | -141 | 5 | 2 |
| -11 | 194 | 4 | 1 |
| 19 | -335 | 1 | 1 |
Theorem: Let \(a\) and \(b\) be integers with \(b\not=0\). Then there are integers \(x\) and \(y\) so that \(ax+by=d\) where \(d\) is the greatest common divisor of \(a\) and \(b\). Conversely, if \(d\) is a common divisor of \(a\) and \(b\) so that there exist integers \(x\) and \(y\) such that \(ax+by=d\), then \(d\) is the greatest common divisor of \(a\) and \(b\).
Proof: Each row of the extended GCD algorithm has \(x,y\) in the columns headed \(a,b\). And each row satisfies \(ax+by=r\) where \(r\) is the entry in that column. The last row has the greatest common divisor in the \(r\) column, so those \(x\) and \(y\) give the solution. (Strictly speaking this is a proof by induction).
Conversely, suppose \(d\) is a common divisor of \(a\) and \(b\) and \(ax+by=d\) for some \(x\) and \(y\). Let \(f\) be any other common divisor. Then \(f\) divides \(ax+by\) so \(f\) divides \(d\) so \(d\ge f\). Thus \(d\) must be the greatest common divisor.
Proposition: Let \(a\) and \(b\) be integers with \(b\not=0\) and let \(d\) be the greatest common divisor of \(a\) and \(b\). Then there exist integers \(x\) and \(y\) so that \[ ax+by=d. \]
Proof: Let \[ S=\{ ax+by : x,y\in\mathbb{Z}\}. \] Both \(b\) and \(-b\) belong to \(S\), and therefore the subset of \(S\) consisting of positive elements is non-empty. Let \(d\) be the smallest positive element of \(S\), which exists by the well-ordering principle. I will show first that \(d\) is a common divisor of \(a\) and \(b\), and then that it is the greatest common divisor.
Use the division algorithm to write \(a=qd+r\) with \(0\le r<d\)> Then \(a=q(ax+by)+r\) and so \((1-qx)a+bqy=r\). This shows that \(r\in S\). Since \(0\le r<d\), and \(d\) is the smallest positive element of \(S\), we must have \(r=0\) and therefore \(d|a\). Repeating the argument with \(b\) shows that \(d|b\), so \(d\) is a common divisor of \(a\) and \(b\).
To show that \(d\) is the greatest common divisor, let \(s>0\) be any common divisor. Then since \(s|a\) and \(s|b\), we know that \(s|(ax+by)\) and so \(s|d\). Therefore \(s\le d\), so \(d\) is the largest common divisor.
Let \(a\) and \(b\) be integers with \(b\not=0\) and let \(d\) be their greatest common divisor.
Also the following important fact.
Proposition: Suppose \(a,b,c\) are integers and \(\mathrm{gcd}(a,c)=1\). If \(a|bc\) then \(a|b\).
Proof: \(ax+cy=1\) so \(abx+bcy=b\). Since \(a\) divides \(ab\) and \(a\) divides \(bc\) we have \(a|b\).