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₁*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.

2.1. Solution

1. Disproof: There are no prime elements: for any (x,y), (x,y) = (x,y)*(1,1).

2. Proof: Given (m,n), compute the unique factorizations m = p₁...p_k and n = q₁...q_l in ℕ-{0,1}. Then we claim that (1,q₁)...*(1,q_l)*(p₁,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,q'_l')*(p'₁1)...*(p'_k',1) = (p'₁...p'_k', q'₁...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²|n. Prove that any n > 0 can be written as ab² 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²|a for some k > 1 we'd have p²|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 0

• 2x + 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 ≡₃ (qm - 1) ≡₃ 3q(m/3) - 1 ≡₃ -1.

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