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

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.

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.

2014-06-17 11:57