Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

Here are the /Solutions.

# 1. Connectivity of religious symbols

Define the graph C(k,m) = (V,E) where V = { 0, 1, 2, ..., m-1 } and E = { (u,v) | u - v ≡m k or v - u ≡m k }. Compute the number of connected components of C(k,m) as a function of k and m. (Hint: Try drawing some small cases where the vertices are evenly spaced around a circle, and look for symmetries in the connected components.)

# 2. Unique factorization

Suppose you have a totally-ordered set S and an associative and commutative operation *: S×S → S (associative means (x*y)*z = x*(y*z); commutative means x*y=y*x). Let's say that (S,*) has unique factorization if for any x in S, either (a) x is prime: there is no way to produce x as y*z; or (b) x has exactly one factorization p1*p2...*pk where each pi is prime and p1≤p2≤p3...≤pk. For example, the Fundamental Theorem of Arithmetic says that ℕ-{0,1} with the usual ordering and *=multiplication has unique factorization.

Consider the set S = { (x,y) : x, y ∈ ℕ-{0} } ordered lexicographically, so that (x,y) ≤ (x',y') iff x < x' or x = x' and y ≤ y'. Let * be the operation (x,y)*(x',y') = (xx',yy'), so that e.g. (2,3)*(4,5) = (8,15).

1. Prove or disprove: S has unique factorization.
2. Prove or disprove: S-{(1,1)} has unique factorization.

# 3. Square and square-free

A number is square-free if there is no k > 1 such that k2|n. Prove that any n > 0 can be written as ab2 where a is square-free.

# 4. Simultaneous congruences

Prove that the simultaneous congruences

• x + 2y ≡m 0

• 2x + y ≡m 1

have a solution if and only if gcd(m,3) = 1.

2014-06-17 11:57