# 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.

## 1.1. Solution

- Claim
- The number of components is equal to gcd(k,m).
- Proof
Observe that if there is a path from u to v there must be some sequence of nodes u, u+k, u+2k, u+3k, ... u+nk that gets there (mod m, of course). So in particular we have v - u ≡

_{m}nk for some n. Let d = gcd(k,m), then k = bd for some for b and for connected u and v we have v - u ≡_{m}nk = nbd. Since d|m, nbd ≡_{m}ad for some a where 0 ≤ ad < m. There are exactly m/d such values and thus there are exactly m/d values in the connected component containing u. Since this is true for any u, the number of connected components must be m/(m/d) = d.

# 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.

## 2.1. Solution

- Disproof: There are no prime elements: for any (x,y), (x,y) = (x,y)*(1,1).
Proof: Given (m,n), compute the unique factorizations m = p

_{1}...p_{k}and n = q_{1}...q_{l}in ℕ-{0,1}. Then we claim that (1,q_{1})...*(1,q_{l})*(p_{1},1)...*(p_{k},1) is the unique factorization of (m,n). Observe first that the order property holds and that each factor (1,q_{i}) or (p_{i},1) is prime (if not, (1,q) = (1,a)*(1,b) gives a factorization q = ab and similarly for (p,1)). Suppose now that there is some other factorization of (m,n). If it contains a term (p,q) where both p and q are not 1, we can factor (p,q) = (1,q)*(p,1) and (p,q) is not prime. So we can write the alternate factorization as (1,q'_{1})...*(1,q'_{l'})*(p'_{1}1)...*(p'_{k'},1) = (p'_{1}...p'_{k'}, q'_{1}...q'_{l'}) = (m,n). But then the p' sequence equals the p sequence an similar for q and q' by the Fundamental Theorem of Arithmetic.

# 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.

## 3.1. Solution

For n = 1, let a=1 and b=1.

For larger n, compute the prime factorization

Equality holds because 2⌊x/2⌋+(x mod 2) = x for all x (it's the DivisionAlgorithm in action again).

Now let a be the left-hand product and b the right-hand product. It's easy to see that a is square-free, since if k^{2}|a for some k > 1 we'd have p^{2}|a for some prime factor p of k, but a has no prime factors with exponent greater than 1.

# 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.

## 4.1. Solution

Let's hunt for a solution in ℤ_{m} using what we remember from high-school algebra:

- x + 2y = 0, so x = -2y.

Plugging into the second equation gives

- -4y + y = 1

or

- 3y = -1.

If gcd(3,m) = 1, there exists some 3^{-1} such that 3^{-1}×3 = 1 (mod m). Multiplying both sides by 3^{-1} then gives

y = -3

^{-1}

from which we get

x = 2(3

^{-1}).

If gcd(3,m) ≠ 1, we get stuck at the 3^{-1} step, since 3^{-1} (mod m) doesn't exist. To show that this is a problem with the equation and not with our solution method, observe that if

- 3y = -1 (mod m)

we have

- 3y = qm - 1

for some q (working now over the ordinary integers ℤ). But then taking both sides mod 3 gives

0 ≡

_{3}(qm - 1) ≡_{3}3q(m/3) - 1 ≡_{3}-1.

But 0 isn't congruent to 1 mod 3, so there is no y that makes 3y ≡_{m} -1 work in this case.