Lectures 23-24 (Apr 2 and 4)
Today we discussed and proved Quadratic Reciprocity. See the first two sections of this document for the proof.
Lectures 21 (Mar 26)
We discussed various formulas and open problems concerning primitive roots. This led us to discuss the Möbius function, and several outstanding open questions connected to it. Finally, we talked about the Diffie-Hellman Key Exhange.
Lectures 18--20 (Mar 14, 19, 21)
We proved that ℤpx has a primitive root for every prime p. Click here for more details.
Lecture 17 (Mar 12)
Today we discussed primitive roots. Click here for more details.
Lecture 16 (Mar 7)
Today we explored the order of an element of Zdx. Click here for more details.
Lecture 15 (Mar 5)
Today we proved (half of) David's conjecture from last lecture. Namely, we showed that if (m,n) = 1, then φ(mn) = φ(m) φ(n). Click here for more details.
Lecture 14 (Feb 28)
Today we discussed Euler's phi function φ(n), in particular trying to find a formula for it. Nakita proposed that if p is prime, then φ(p2) = pφ(p), and we were able to prove this. Building on the same ideas, we proved that
for any prime p and positive integer k. We then played around some more, and David conjectured that
if and only if (m,n) = 1. If true, this would allow us to figure out φ(n) with relative ease. For example,
Lecture 13 (Feb 26)
Today we discussed invertible elements and the set Zdx. We proved that one has a natural notion of division on this set. We also proved Euler's theorem. Click here for more details.
Lecture 12 (Feb 14)
Today we continued discussing multiplication in Zd, in particular proving our conjectures from last lecture. Click here for more details.
Lecture 11 (Feb 12)
Today we wrote out the multiplication tables modulo 4, 5, 6, 7, 8, and 9, and hunted for patterns. Among other observations, we distinguished two types of rows. A `good' row was one in which every cell holds a different number (like a Sudoku puzzle). A `bad' row was one in which some numbers appeared more than once. David and Qamar conjectured that the n-th row is good iff (n,d)=1. Theepi conjectured that a row is bad iff it contains a 0. We discussed both of these. We also noticed and proved various symmetries in the table.
Lecture 10 (Feb 7)
Today we began discussing modular arithmetic, a subject which we shall explore for a good part of the rest of the term. We started by doing arithmetic on the clock. We decided that 15 and 27 are both the same as 3 on the clock, that 12+19 is the same as 7, and that 5 times 7 is the same as 11. Of course, if we had a clock with 5 numbers on it, instead of the usual 12, our calculations above would all be wrong. To indicate which clock we're working on, we write things like 5 x 7 ≡ 11 (mod 12), read `five times seven is congruent to 11 modulo 12'. On the other hand, 5 x 7 ≡ 5 (mod 5).
More generally, we write a ≡ b (mod d) if the numbers a and b are indistinguishable on the `d-clock' (i.e. the clock with the numbers 1 through d on it). Nakita proposed defining this more formally: a ≡ b (mod d) iff d | b-a. We observed that this is equivalent to saying that there exists an integer q such that a = qd + b.
We next proved a bunch of basic properties of congruence. The most interesting ones: if a ≡ b (mod d) and x ≡ y (mod d), then a+x ≡ b+y (mod d) and ax ≡ by (mod d). Using these ideas, we solved the following problem, which (at first glance) has nothing to do with modular arithmetic: find all integers x and y such that x2 + y2 = 2015. It's not at all obvious how to attack this problem aside from trial an error. Using modular arithmetic, however, we can give an extremely simple proof that no solutions exist! To do this, we first observed that for any integer n, n2 ≡ 0 or 1 (mod 4). Now, suppose x and y are integers whose squares sum to 2015. Then it would follow that x2 + y2 ≡ 2015 (mod 4). By our earlier observation, the left hand side of this congruence is either 0, 1, or 2. The right hand side, on the other hand, is congruent to 3 (mod 4). Thus, this congruence cannot possibly have a solution, which proves that the original equation also cannot be solved. We will discuss this phenomenon further next week.
Lecture 9 (Feb 5)
Today we continued discussing primes, in particular proving Chebyshev's upper and lower bounds on the prime counting function. Click here for more details.
Lecture 8 (Jan 31)
Today we continued discussing primes, in particular mostly proving Chebyshev's upper bound on the prime counting function. Click here for more details.
Lecture 7 (Jan 29)
Today we continued discussing primes, in particular: lower bounds on the prime counting function, a different proof of the infinitude of primes, and some history (the Prime Number Theorem and the Riemann Hypothesis). Click here for more details.
Lecture 6 (Jan 24)
We started by clarifying some of the discussion from last time by stating a new (but equivalent) definition of prime. An integer greater than 1 is composite if it can be written as the product of two integers a,b ∈ (1,n); otherwise, it is called prime.
Next, we defined the function ordp(n); it is the exponent of the largest power of p dividing n. This function is well-defined (because of the FTA), and satisfies some nice properties. For example we proved that ordp(mn) = ordp(m) + ordp(n). Further, if d | n, then ordp(d) ≤ ordp(n); it follows that ordp(a,b) = min{ordp(a), ordp(b)}.
Finally, we examined Euclid's proof of the infinitude of primes: given any finite collection of primes p1, p2, ..., pk, consider the integer N = p1 p2 ... pk + 1. By the FTA, ∃p | N. But pi cannot divide N for any i, since N - p1 p2 ... pk = 1; it follows that p ≠ pi for all i. In other words, any finite list of primes is incomplete.
Lecture 5 (Jan 22)
After reviewing the Euclidean Algorithm, we completed the proof that it outputs the GCD by proving that the final output of the algorithm (which we denoted nk-1) is a divisor of nj for all j; in particular, nk-1 is a common divisor of a and b, and is therefore at most (a,b). On the other hand, we proved last lecture that (a,b) | nk-1, whence (a,b) ≤ nk-1. Putting all this together shows that nk-1 = (a,b) as claimed.
Next, we applied the Euclidean algorithm to a few examples. Moreover, we used it (in reverse) to find integers x and y such that 37x + 17y = 1 (we know such integers exist, since 37ℤ + 17ℤ = ℤ).
We finished the lecture by stating and proving the Fundamental Theorem of Arithmetic: every integer ≥ 2 has a unique prime factorization. We observed that this is not a totally trivial statement, by looking at an analogue of the natural numbers: the set E of positive even numbers. We found that 60 has two different prime factorizations (60 = 6 x 10 = 2 x 30). Of course, this requires a slightly different definition of the notion of prime, but it was a natural one: an element of E is prime iff it cannot be expressed as the product of two smaller elements of E. Having seen that the FTA says something special about ℕ, we proved it. First, we proved the existence of prime factorization by strong induction. Next, we proved uniqueness by repeatedly using our lemma about primes: if p | ab, then p | a or p | b. Next lecture, we continue to discuss primes, in particular turning to their distribution.
Lecture 4 (Jan 17)
We began by working out all the common factors of two numbers, using the same approach as at the end of last lecture. Then I wrote down the formal statement of the Euclidean algorithm. We proved that the algorithm terminates after a finite number of steps (in fact, we gave an upper bound on how many steps before it must terminate). We next proved that (a,b)|nk-1 (recall that nk-1 denotes the last nonzero output of the algorithm). Finally, Jay proposed that nk-1 should be a common divisor of a and b, and that this would imply that nk-1 = (a,b). We left these ideas as an exercise for the weekend.
Lecture 3 (Jan 15)
We started by re-proving the theorem from last lecture, but in a more methodical way. First we proved a lemma: given any integer a and any positive integer d, there exist integers q and r such that a = qd + r and 0 ≤ r < d. The proof was simply to take q to be the floor of q/d, and then follow your nose. With this lemma in hand, we could give a short and quick proof that for any two integers a and b (at least one of which is nonzero), aℤ + bℤ = dℤ, where d is the smallest positive element of aℤ + bℤ.
Next, we proved David's conjecture that d = (a,b). [This is the notation for the greatest common divisor of a and b. We also introduced the notation d|n to mean that d divides n, i.e. n is a multiple of d.] We proved this in two steps. First, we showed that d was a common divisor of a and b. [a is in aℤ + bℤ, which implies that a is in dℤ, so d|a; same for b.] Next, we proved that any common divisor is ≤ d. [Suppose c is a common divisor of a and b. If c ≤ 0, we're done. Else, since d is in dℤ, we see that d is in aℤ + bℤ. Thus d = aj + bk. Dividing both sides by c, we see that the RHS must be an integer; hence, d/c is an integer. Moreover, it must be positive. Thus, d/c ≥ 1, and the result follows.]
We next derived two corollaries from this. The first, which is immediate, is that for any two integers a and b there exist integers x and y such that (a,b) = ax + by. The second, which took a bit more ingenuity, was that if a prime p|ab, then p|a or p|b.
We concluded lecture with a cool way to figure out whether or not a given fraction is in reduced form. For example, is 203/416 reduced? Suppose d|203 and d|416. Then certainly d|(416-203), i.e. d|213. But if this is the case, then d|(213-203), i.e. d|10. This means d must be 1, 2, 5, or 10, and it is clear that the only one of these which is a common divisor of 203 and 416 is 1. Thus, we have proved that 203/416 is reduced without dividing or factoring; all we did was a few subtractions, which is much easier to do. Next time, we formalize this method into a process called the Euclidean Algorithm.
Lecture 2 (Jan 10)
Fix two integers a and b. Last time we guessed that aℤ + bℤ = dℤ for some integer d. In this lecture, we developed the following proof:
Theorem: Suppose that at least one of a and b is nonzero,
and let d denote the least positive integer in the set aℤ + bℤ.
Then
Proof:
First, Jay observed that a simple argument shows that the RHS ⊆
LHS. It therefore remains to prove the reverse inclusion.
Pick an arbitrary element n in aℤ + bℤ. We saw that
n - d is also an element of aℤ + bℤ. More generally, n - kd is
an element of aℤ + bℤ, for any integer k. Choosing k in such a
way as to make n - kd positive and as small as possible, we see that
Lecture 1 (Jan 8)
We started with a discussusion of six open questions:
- How many times does the digit 7 appear in the decimal expansion of π?
- Is π+e rational?
- Is there always a prime between n2 and (n+1)2, for every natural number n?
- Can every even number larger than 2 be written as the sum of two primes?
- Is there a formula for the nth prime, in terms of n?
- Given a big (200-digit) number N, does there exist an algorithm which is guaranteed to produce a prime factor of N within 20 years?
Even though nobody knows the answers to any of these questions, we have a good idea of what the answers probably are. (In order: infinitely many times; no; yes; yes; no; maybe [no if you're in CS, yes if you're in math].) We talked about a few of these in some more detail, before moving on to the postage stamp problem (what postages can one make using only 3 and 4 cent stamps?). We then changed the problem slightly to get a nicer answer: we proved that 3ℤ + 4ℤ = ℤ. Similarly, 3ℤ + 5ℤ = ℤ, but 3ℤ + 3ℤ = 3ℤ and 4ℤ + 6ℤ = 2ℤ. What is going on here? Given two arbitrary integers a and b, what can one say about aℤ + bℤ? We immediately guessed that no matter what a and b are, there should exist an integer d such that aℤ + bℤ = dℤ. Moreover, David conjectured a simple formula for d: d is the greatest common divisor of a and b. More on these next time!
