[FrontPage] [TitleIndex] [WordIndex

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. Equations mod m

Let a and b be constants in ℤm, where m∈ℕ and m≥2, and let x be a variable. Show that the equation ax=b (mod m) has a unique solution in ℤm if and only if gcd(a,m) = 1.

1.1. Solution

First suppose gcd(a,m) = 1. From the extended Euclidean algorithm we have that there exists some a-1∈ℤm such that a-1a = 1 (mod m), and thus x = a-1ax = a-1b (mod m). It is easy to see that this solution is unique (if there is some y such that ay = b, then a-1ay = y = a-1b = x).

Now suppose gcd(a,m) ≠ 1. We will consider two cases:

1. If gcd(a,m) = 0, then a=0 (because every nonzero a has at least 1 as a factor). So we have 0x=b (mod m), which either has no solutions (if b≠0, no value of x works), or m solutions (if b=0, every value of x works). In either case we don't have one solution.

2. If gcd(a,m) > 1, then either we have no solutions to ax=b (mod m), or we have at least one solution. In the latter case, call the solution x. Let k = gcd(a,m) and let x' = x + m/k (mod m). Because m/k < k, we have x' ≠ x (mod m). We also have ax' = a(x + m/k) = ax + am/k = ax + (a/k)m = b + 0 = b (mod m). It follows that if ax=b (mod m) has either no solutions or at least two distinct solutions.

2. Divisibility

Recall that for m,n∈ℕ, we write m|n if there exist some k∈ℕ such that n=km.

  1. Let a∈ℕ, a≠0. Show that m|n if and only if am|an.
  2. Show that m|n if and only if m2|n2.

2.1. Solution

1. Suppose first that m|n, i.e., that there exists k such that n=km. Then an = akm = k(am),so am|an. For the other direction, suppose that am|an. Then there exists k such that an=k(am). Divide by a to get n=km.

2. Again suppose that m|n and thus that n=km for some k. Then n2 = (km)2 = k2m2, so m2|n2.

The other direction is trickier, and I suspect it is hard to do without using the fact numbers in ℕ-{0} have unique factorizations. Suppose that m and n are both nonzero, and let $m = \prod p^{i_p}$ and let $n = p^{j_p}$, where in each case the product is taken over all primes. Then it is not hard to see that m|n if and only if ip≤jp for all p. But this occurs if and only if 2ip≤2jp for all p, or if $m^2 = \prod p^{2i_p}$ divides $n^2 = \prod p^{2j_p}$.

This leaves the case where one or both of m and n is zero. If n=0, then we have m2|n2 and m|n, since everything divides 0. If m=0 and n≠0, then, m2∤n2 and m∤n, so again we are happy.

3. Partial orders

Let R be a partial order on B, and let f:A→B be a function. Define the relation Rf on A by the rule (x,y) ∈ Rf if and only if (f(x),f(y)) ∈ R.

Show that Rf is a partial order if and only if f is injective.

3.1. Solution

If f is injective, then we can verify that Rf has the necessary properties of reflexivity, antisymmetry, and transitivity:

If f is not injective, there exist x,y∈A such that x≠y but f(x)=f(y). Because R is reflexive, we have (f(x),f(y))∈R, which implies (x,y)∈Rf and similarly (y,x)∈Rf. But then Rf is not antisymmetric.

2014-06-17 11:57