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₁*p₂...*p_k where each p_i is prime and p₁≤p₂≤p₃...≤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).

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 k²|n. Prove that any n > 0 can be written as ab² 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.