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 p_{1}*p_{2}...*p_{k} where each p_{i} is prime and p_{1}≤p_{2}≤p_{3}...≤p_{k}. 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).

- Prove or disprove: S has unique factorization.
- 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 k^{2}|n. Prove that any n > 0 can be written as ab^{2} where a is square-free.

# 4. Simultaneous congruences

Prove that the simultaneous congruences

x + 2y ≡

_{m}02x + y ≡

_{m}1

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