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.

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

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 = p1...pk and n = q1...ql in ℕ-{0,1}. Then we claim that (1,q1)...*(1,ql)*(p1,1)...*(pk,1) is the unique factorization of (m,n). Observe first that the order property holds and that each factor (1,qi) or (pi,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'11)...*(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 k2|n. Prove that any n > 0 can be written as ab2 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 k2|a for some k > 1 we'd have p2|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 ≡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.

2014-06-17 11:57