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 m²|n².

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 n² = (km)² = k²m², so m²|n².

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 and let , 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 i_p≤j_p for all p. But this occurs if and only if 2i_p≤2j_p for all p, or if divides .

This leaves the case where one or both of m and n is zero. If n=0, then we have m²|n² and m|n, since everything divides 0. If m=0 and n≠0, then, m²∤n² 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 R_f on A by the rule (x,y) ∈ R_f if and only if (f(x),f(y)) ∈ R.

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

3.1. Solution

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

• For reflexivity, observe that for any x∈A, we have (f(x),f(x))∈R (by reflexivity of R). So (x,x)∈R_f.

• For antisymmetry, let x,y be such that (x,y)∈R_f and (y,x)∈R_f. Then (f(x),f(y))∈R and (f(y),f(x))∈R, and by antisymmetry of R we have f(x)=f(y). But then x=y since f is injective.

• For transitivity, let (x,y) and (y,z) both be in R_f. Then (f(x),f(y))∈R and (f(y),f(z))∈R, from which it follows that (f(x),f(z))∈R by transitivity of R. So (x,z)∈R_f.

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)∈R_f and similarly (y,x)∈R_f. But then R_f is not antisymmetric.