Midterm review

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

1Proof 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)

2Concepts 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)

3Theorems seen in class¶

3.1Fermat'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.2Wilson'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.3The 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.4Euclid's lemma¶

One formulation is:

Using only the basic properties of the gcd proved in class, (and not the 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.5Infinitely 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.6Chinese remainder theorem¶

Hope we don't have to prove this

3.7Miller-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.8Bé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.