Today we discussed and proved Quadratic Reciprocity. See the first two sections of this document for the proof.

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.

We proved that ℤ_{p}^{x} has a
primitive root for every prime p.
Click here for more details.

Today we discussed primitive roots. Click here for more details.

Today we explored the *order* of an element of
Z_{d}^{x}.
Click here for more details.

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.

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 φ(p^{2}) = 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,

Today we discussed invertible elements and the
set Z_{d}^{x}. We proved that one
has a natural notion of division on this set. We
also proved Euler's theorem.
Click here for more details.

Today we continued discussing multiplication
in Z_{d}, in particular proving our
conjectures from last lecture.
Click here for more details.

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.

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
x^{2} + y^{2} = 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, n^{2} ≡ 0 or 1
(mod 4). Now, suppose x and y are integers whose
squares sum to 2015. Then it would follow that
x^{2} + y^{2} ≡ 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.

Today we continued discussing primes, in particular proving Chebyshev's upper and lower bounds on the prime counting function. Click here for more details.

Today we continued discussing primes, in particular mostly proving Chebyshev's upper bound on the prime counting function. Click here for more details.

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.

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 ord_{p}(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
ord_{p}(mn) = ord_{p}(m) + ord_{p}(n).
Further, if d | n, then
ord_{p}(d) ≤ ord_{p}(n); it follows that
ord_{p}(a,b) =
min{ord_{p}(a), ord_{p}(b)}.

Finally, we examined Euclid's proof of the infinitude of primes:
given any finite collection of primes
p_{1}, p_{2}, ..., p_{k}, consider the
integer N = p_{1} p_{2} ... p_{k} + 1.
By the FTA, ∃p | N. But
p_{i} cannot divide N for any i, since
N - p_{1} p_{2} ... p_{k} = 1; it follows
that p ≠ p_{i} for all i. In other words,
any finite list of primes is incomplete.

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 n_{k-1}) is a divisor
of n_{j} for all j; in particular, n_{k-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) | n_{k-1},
whence (a,b) ≤ n_{k-1}. Putting all this together
shows that n_{k-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.

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)|n_{k-1} (recall that
n_{k-1} denotes the last nonzero output of the algorithm).
Finally, Jay proposed that n_{k-1} should be a common divisor
of a and b, and that this would imply that n_{k-1} = (a,b).
We left these ideas as an exercise for the weekend.

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.

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

since otherwise we could substract or add another copy of d. By the definition of d, this implies that n - kd = d, whence n = (k+1)d. It follows that every element of aℤ + bℤ is a multiple of d, i.e. aℤ + bℤ ⊆ dℤ. This proves the theorem, leaving the proof of David's conjecture (on a formula for d) for next lecture.

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 n
^{2}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 n
^{th}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!