# 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^{-1}a = 1 (mod m), and thus x = a^{-1}ax = a^{-1}b (mod m). It is easy to see that this solution is unique (if there is some y such that ay = b, then a^{-1}ay = y = a^{-1}b = 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.

- Let a∈ℕ, a≠0. Show that m|n if and only if am|an.
Show that m|n if and only if m

^{2}|n^{2}.

## 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^{2} = (km)^{2} = k^{2}m^{2}, so m^{2}|n^{2}.

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^{2}|n^{2} and m|n, since everything divides 0. If m=0 and n≠0, then, m^{2}∤n^{2} 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.