Wednesday, September 26, 2012

Applications of the FTA; introduction to relations

Lecture notes for lecture #10 of MATH 235, normally taught by Henri Darmon, but with Miljan Brakočević temporarily filling in while Darmon is away for a week. These lecture notes are student-generated and any errors or omissions should be assumed to be the fault of the notetaker and not of the lecturer. To correct an error, you have to be registered and logged-in; alternatively, you can contact @dellsystem directly.

In this lecture, we covered section 10.1 and started chapter 12 of the notes.

1Applications of the fundamental theorem of arithmetic¶

1.1Proposition 10.1.1¶

Let $a, b \in \mathbb{Z} \setminus \{0\}$. Then $a$ divides $b$ if and only if $a = \varepsilon p_1^{a_1} \ldots p_m^{a_m}$ and $b = \mu p_2^{a_1'}\ldots p_m^{a_m'} q_1^{b_1}\ldots q_t^{b_t}$, where $a_i' \geq a_i$ for all $i$ and all the exponents are integers.

In other words, this means that if $a$ divides $b$, then all of $a$'s prime factors are contained in $b$; and, if all of $a$'s prime factors are contained in $b$, then $a$ necessarily divides $b$.

1.1.1Proving the leftward implication¶

First, we prove the $\leftarrow$ implication. This is fairly straightforward; fro the given factorisations, it's quite easy to see that $a\mid b$:

$$\frac{b}{a} = \frac{\varepsilon}{\mu} p_1^{a_1'-a_1} \ldots p_m^{a_m' - a_m} q_1^{b_1} \ldots q_t^{b_t} \in \mathbb{Z} \setminus \{0\}$$

The fraction $\frac{b}{a}$ must be an integer, because all the bases are integers and their exponents are also all integers.

1.1.2Proving the rightward implication¶

Now we prove the $\to$ implication. This one is a bit more involved. From the fundamental theorem of arithmetic, we can write a prime factorisation for $a$:

$$a = \varepsilon p_1^{a_1} \ldots p_m^{a_m}$$

Now, because $\frac{b}{a}$ is an integer (given that $a \mid b$), we can write a prime factorisation for that too:

$$\frac{b}{a} = \upsilon p_1^{a_1''}\ldots p_m^{a_m''} q_1^{b_1} \ldots q_t^{b_t}$$

This is valid because we set $a_i'' \geq 0$ for all $i$, which allows $p_i^{a_i''} = p_i^0 = 1$.

We then multiply $a$ and $\frac{b}{a}$:

$$b = a \cdot \frac{b}{a} = \epsilon \upsilon p_1^{a_1 + a_1''} \ldots p_m^{a_m + a_m''} q_1^{b_1} \ldots q_t^{b_t}$$

We simply have to set $a_i' = a_i + a_i''$ to get the prime factorisation for $b$ that we were trying to reach. $\blacksquare$

1.2Corollary 10.1.2¶

If $a = p_1^{a_1} \ldots p_m^{a_m}$, and $b = p_1^{b_1} \ldots p_m^{b_m}$, then the following is true:

$$\gcd(a, b) = p_1^{\min(a_1, b_1)} \ldots p_m^{\min(a_m, b_m)}$$

This is a general result that follows from the previous proposition. We can derive it as follows: let $d$ be a divisor of $a$ and $b$. Then we can write $d$ as $d = p_1^{c_1} \ldots p_m^{c_m}$. But since $d \mid a$ and $d \mid b$, then we must have that $c_i \leq a_i$ and $c_i \leq b_i$ for all $i$. To maximise $d$ (and thus find the greatest common divisor), we can set $c_i$ equal to the lesser of $a_i$ and $b_i$, i.e., $\min(a_i, b_i)$.

We can apply this result to any $a, b \in \mathbb{N}$, even numbers that don't have any prime factors in common, using the same trick where we set the exponent to 0 that we used above. For instance, if $a = 21$ and $b = 55$, then:

$$21 = 3 \cdot 7 = 3^1 \cdot 7^1 \qquad 55 = 5 \cdot 11 = 5^1 \cdot 11^1$$

But we can also write their factorisations as:

$$21 = 3^1 \cdot 5^0 \cdot 7^1 \cdot 11^0 \qquad 55 = 3^0 \cdot 5^1 \cdot 7^0 \cdot 11^1$$

So their $\gcd$ would be $3^0\cdot 5^0 \cdot 7^0 \cdot 11^0 = 1$.

1.3Proposition 10.1.3¶

Any non-zero rational number $q$ can be written as

$$q = \varepsilon p_1^{a_1} \ldots p_m^{a_m}$$

where $\varepsilon = \pm 1$ as usual, the $p$s are distinct prime numbers, and $a_i \in \mathbb{Z} \setminus \{0\}$ (so the exponents can be negative, which is not covered by the fundamental theorem of arithmetic). Moreover, this expansion is unique.

1.3.1Proving the existence property¶

First, we have to show that such an expansion exists for $q$. Let $q = \frac{a}{b}$, where $a, b \in \mathbb{Z} \setminus \{0\}$. Using the fundamental theorem of arithmetic we can write factorisations for $a$ and $b$:

$$a = \varepsilon_a r_1^{s_1} \ldots r_n^{s_n} \qquad b = \varepsilon_b r_1^{t_1} \ldots r_n^{t_n}$$

where $s_i, t_i \geq 0$, using the same trick we used above. So $q$ is given by

$$q = \frac{a}{b} = \frac{\varepsilon_a}{\varepsilon_b} r_1^{s_1 - t_1} \ldots r_n^{s_n-t_n}$$

Note that the exponents here can be negative.

In any case, we know have the factorisation we wanted (just replace $r$ by $p$, and let $a_i = s_i - t_i$). $\blacksquare$

1.3.2Proving the uniqueness property¶

Assume that we have two different factorisations for $q$:

$$q = \varepsilon p_1^{a_1} \ldots p_m^{a_m} = \varepsilon' p_1^{a_1'} \ldots p_m^{a_m'}$$

Again, we can say that the $p$s (the prime bases) are the same for both sides because the exponent can always be 0.

Right away, we can conclude that $\varepsilon = \varepsilon'$ (since they just indicate the sign). Then we can divide both sides of the equation (the one relating the two factorisations of $q$) by $p_1^{a_1'} \ldots p_m^{a_m'}$:

$$1 = p_1^{a_1 - a_1'} \ldots p_m^{a_m - a_m'} = p_1^{c_1} \ldots p_m^{c_m}$$

Now we sort the terms in the multiplication in ascending order, so that all the negative exponents are to the left of term $t$ (inclusive). We can divide the equation above by the negative exponents, resulting in:

$$\underbrace{p_1^{-c_1} \ldots p_t^{-c_i}}_{\text{positive exponents}} = p_{t+1}^{c_{t+1}} \ldots p_m^{c_m}$$

Since we now have only positive exponents, we can use the uniqueness property of the fundamental theorem of arithmetic to conclude that this could only happen if $c_i = 0$ for all $i$. Which means that $a_i = a_i'$ for all $i$, and so the two "different" factorisations for $q$ are really the same factorisation.

1.4Proposition 10.1.4¶

The square root of 2 is irrational.

The proof given in class is actually kind of neat, and uses the fundamental theorem of arithmetic (which makes sense, given the section this is in), as opposed to the more-or-less standard proof using properties of odd and even numbers. As usual, we prove by contradiction: assume $\sqrt{2} \in \mathbb{Q}$. So by proposition 10.1.3, we can write it as

$$\sqrt{2} = p_1^{a_1} \ldots p_m^{a_m}$$

where all the exponents $a_i$ are, of course, integers. If we square both sides of the equation, we get:

$$(\sqrt{2})^2 = 2 = p_1^{2a_1} \ldots p_m^{2a_m}$$

By the fundamental theorem of arithmetic (?), we know that 2 is a prime number which is divisible by only 1 and 2. So it must be that the $p$s are 1 and 2. WLOG, let $p_1 = 2$ and $2a_1 = 1$, and $p_2 = 1$ and $2a_1 = 1$. But then $a_1 = a_2 = \frac{1}{2}$, contradicting our original premise that all the exponents $a_i$ are integers. $\blacksquare$

2Introduction to relations¶

Now we begin a really fun topic: relations¹. We define a relation on a set $S$ as a subset $\Gamma \subseteq S \times S$. $s$ is related to $t$ under this relation if and only if $(s, t) \in \Gamma$. We use the notation $s \sim t$ to say that $s$ is related to $t$.

The implication, of course, is that any subset of $S \times S$ could be a relation. Even the empty subset.

Note that a relation is not the same as a function, for obvious reasons; an element in the "domain" of a relation could be related to multiple elements.

2.1Properties of relations¶

2.1.1Transitivity¶

If $a \sim b$ and $b \sim c$, then $a \sim c$.

2.1.2Partial ordering¶

A partial order is a relation that is transitive (defined above), as well as antisymmetric (if $a \sim b$ and $b \sim a$, then $a = b$). Reflexivity is also necessary (for every $a$ we have $a \sim a$), although it was not mentioned in class.

2.1.3Linear ordering¶

A linear (or total) order has all the properties of a partial order with one more: totality, which means that given any $a$ and $b$, either $a \sim b$ or $b \sim a$.

2.1.4Equivalence¶

An equivalence relation is reflexive, transitive, and symmetric² (if $a \sim b$, then $b \sim a$). For example, a simple equivalent relation would be having the same birthday as someone else. I obviously have the same birthday as myself (reflexivity); if I have the same birthday as Alice, and Alice has the same birthday as Bob, then I have the same birthday as Bob (transitivity); and if Alice has the same birthday as me, then I have the same birthday as Alice (symmetry).