**Maintainer:**admin

The midterm will take place on Wednesday, October 24, during class (in the regular room). Sections covered: everything up until (and partially including) polynomials.

*1*Proof techniques¶

Multiple techniques can be used in one proof.

- Induction (can use the successor function)
- Proving the contrapositive (to show
`A -> B`

, just show`not B -> not A`

- Proof by contradiction (assume the opposite of the statement you're trying to prove, then reach a contradiction)
- When proving an equality, manipulate the expression on the left until it looks like the right (similar for inequalities)
- Proving both directions for if and only if statements
- Using properties of addition, multiplication, etc (the defining properties)
- Also: well-ordering principle
- For gcd: bezout's identity (linear combination)

- When proving set equality or inequality, focus on the elements of the sets (also applies to functions, relations)

*2*Concepts seen in class¶

- Cardinality
- The pigeonhole principle
- Cantor's diagonal argument
- Proves that there is no bijection from $\mathbb{N}$ to $\mathbb{R}$

- Euclidean algorithm
`gcd`

- Complex numbers
- Polar representation: $r\sin(z)/ + r\cos(z)$ where $z = ab + i$ and $r = |z|$
- Exponentation function: $e^{i\theta} = \cos\theta + i\sin\theta$

- Rings
- Addition (commutative, associative, neutral, inverse), multiplication (associative, neutral), distributivity
- Commutative ring: also has multiplicative commutativity
- field: every element has a multiplicative inverse in the field

- Power sets
- Prove that a function mapping a set to its power set is not bijective (even for the empty set!)

- Irrationality of $\sqrt{2}$
- Congruence relations
- Properties of equivalence relations: r (reflexive), s (symmetric), t (transitive)
- set of equivalence classes is a field iff $n$ is prime

- Fermat's little theorem
- Carmichael numbers (pseudoprimes)

*3*Theorems seen in class¶

*3.1*Fermat's little theorem¶

$a^p \equiv a \pmod p$. If $a \not \equiv 0 \pmod p$, then this is equivalent to $a^{p-1} \equiv 1 \pmod p$.

First, we prove the lemma that if $p$ is prime, then it divides the binomial coefficient $\displaystyle \binom{p}{k}$ for all $k = 1, \ldots p-1$. To prove *that*, expand it out to

$$\frac{p!}{k!(p-k)!} = \frac{p \cdot (p-1) \cdot \ldots \cdot (p - k + 1)}{k!}$$

Since the binomial coefficient is always an integer, the denominator must divide the numerator. Since $k < p$, the factorial of $k$ does not divide $p$. So it must divide the other part. But this means that the binomial coefficient is a multiple of $p$, since that is not cancelled out by the denominator. So $p$ must divide it, which proves the lemma.

Now we can prove FLT using induction on $a$. The induction step involves using the binomial theorem.

*3.2*Wilson's theorem¶

$p$ is prime $\iff$ $p \mid (p-1)! + 1$

The proof for this is really quite pretty. First, the $\leftarrow$ direction, using multiple contradictions and proving the contrapositive. First, we assume that $p \mid (p-1)! + 1$ where $p$ is not prime. Since $p$ is not prime, then $a \mid p$ for some $a$ less than $p$ and greater than 1 (factor). So $a$ divides $(p-1)!$ because $a$ is in there somewhere. If it also divides $(p-1)! + 1$ then it must divide the difference between that and $(p-1)!$, which is just 1. So that tells us that $a = 1$. But we chose $a > 1$. So we reach a contradiction, meaning that $a \nmid (p-1)! + 1$. But since $a \mid p$ and $p \mid (p-1)! + 1$, then, by the transitivity of $\mid$, we must have that $a \nmid (p-1)! +1$. But we just showed that that is impossible, which means that our assumption - that $p$ is prime - is not true. Consequently, this doesn't hold for composite $p$, which proves the contrapositive.

For the $\rightarrow$ direction: suppose $p$ is prime. Then $x^2 \equiv 1 \pmod p$ has two sollutions, 1 and -1 (proved in assignment 2, question 7, using Euclid's lemma). So 1 and -1 are their own inverses. Now we look at the product $1 \cdot 2 \cdot \ldots \cdot (p-2) \cdot (p-1)$. Basically, everything has an inverse except $p-1$, which doesn't cancel out. So $(p-1)! \equiv -1 \pmod p$ and so if we add one to it we get what we're trying to prove in congruence relation notation.

*3.3*The fundamental theorem of arithmetic¶

Every non-zero number can be uniquely represented as a product of primes.

First, prove the existence property using the well-ordering principle and proof by contradiction. Assume there is a non-empty set of numbers that can't be written as a product of primes. The least element must be a product of two numbers. You reach a contradiction very quickly, for these two numbers can't be in the set or else the minimality of the least element would be contradicted; however, if they're not in the set, they can be written as a product of primes, and consequently so can their product.

Uniqueness uses Euclid's lemma and proof by induction. Not really that interesting.

*3.4*Euclid's lemma¶

One formulation is:

Using only the basic properties of the gcd proved in class, (and

notthe fundamental theorem of arithmetic) show that if a $p$ is a prime and $p$ divides a product $ab$ of two integers, then $p$ necessarily divides either $a$ or $b$.

Proof:

Since $p\mid ab$ and $p \mid p$ (by the reflexivity of $\mid$), then $\gcd(p, ab) = p$ (since nothing *greater* than $p$ can divide $p$). We assume that $p \nmid a$ and $p \nmid b$. So $\gcd(p, a) = 1$ and $\gcd(p, b) = 1$. By theorem 9.1.2 in the notes (also known as Bézout's identity), there exist integers $x$ and $y$ such that $xp + xa = 1$ (from the fact that $\gcd(p, a) = 1$). If we multiply both sides of the identity by $b$, we get:

$$xbp + xab = b$$

Well, we know that $p \mid ab$, by a premise of this argument. From the definition of a $\gcd$ (definition 9.0.5 (2) in the notes), we know that $p \mid xab$. We also know that $p \mid xbp$, since that's just a multiple of $p$ (definition 9.0.5 (2) again). Then, by definition 9.0.5 (3), we know that $p \mid xbp + xab$, and by the identity above then $p \mid b$. Since this contradicts the premise that $p \nmid b$, then our assumption that $p\nmid a$ and $p\nmid b$ must be wrong, and so $p$ must divide either $a$ or $b$ (or both).

Alternatively, we could just assume, without loss of generality, that $p \nmid a$ and from that conclude that $p \mid b$. Whichever.

Taken from the practice midterm, question 4.

*3.5*Infinitely many primes¶

There are infinitely many primes

Assume that the set of all the primes *in the entire world* is finite, represented in an ordered set as $P = \{p_1, \ldots, p_n\}$ (where $p_n$ is the largest prime number). Now consider the number $N = p_1\ldots p_n + 1$. This number can't be a prime number, because it is greater than the largest prime number $p_n$ by at least one, and so is not in $P$. And yet it *is* a prime number, because the gcd of $N$ and any $p \in P$ (i.e. any prime) is 1, as dividing $N$ by $p$ will always leave a remainder of 1. So we reach a contradiction, which implies that the set of all the primes is *not* finite.

From Monday, September 24 lecture notes.

*3.6*Chinese remainder theorem¶

Hope we don't have to prove this

*3.7*Miller-Rabin¶

Take the sequence $a^{(p-1)}, a^{(p-1)/2}, \ldots$. Should be all 1's, until you get a -1, for all $a$.

Prove that if $p$ is prime then $x^2-1 \equiv \pmod p$ then $x$ can be only 1 or -1 in the field. This is not generally (ever?) true when $p$ is composite. Then we just apply that recursively to each term in the sequence, since the first term in the sequence is congruent to 1 by FLT.

*3.8*Bézout's identity¶

$a$ and $b$ are non-zero integers. Then there exist integers $x$ and $y$ such that $ax + by = \gcd(a, b)$. Also, $\gcd(a, b)$ is the smallest number that can be written in this form (as a linear combination of $a$ and $b$).

Let $L$ be the set of all positive linear combinations of $a$ and $b$. $L$ is clearly not empty - for example, $a^2 + b^2$ is positive and is thus in the set. By the well-ordering principle, $L$ must have a smallest element. We denote that element by $m = ua + vb$ for some $u, v \in \mathbb{Z}$.

Now, we show that $m \mid a$ and $m \mid b$. We can write $a$ as $a = qm + r$ where $q \in \mathbb{Z}$ and $0 \leq r < m$. We can rewrite $r$ as $a - qm = a -q(ua + vb) = a - qua + qvb = (1-qu)a + qvb$. $r$ is clearly a linear combination of $a$ and $b$. If it's greater than zero, then it is an element of $L$. However, since we selected $r$ to be strictly *less* than $m$, then $r$ being in $L$ would contradict the minimality of $m$. So we must have that $r = 0$ to avoid that contradiction. But then we have that $a = qm + 0= qm$ and so $m \mid a$. In the same way, we get that $m \mid b$.

This shows that $m$ is a common divisor of $a$ and $b$. Now we have to show that $m$ is the *greatest* common divisor of $a$ and $b$. Let $e$ be any common divisor of $a$ and $b$. Then $e$ also divides any linear combination of $a$ and $b$, including $m$, and so $e \mid m$. The largest $e$ that divides $b$ can only be $m$ itself (since no number larger than $a$ can divide $a$ for any $a \in \mathbb{Z} \setminus \{0\}$). So the greatest common divisor of $a$ and $b$ has to be equal to the least element in $S$. This concludes the proof.

Sidenote: a question on the midterm asked for a proof of something closely related to this. If only I knew this then.