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.
- Let a∈ℕ, a≠0. Show that m|n if and only if am|an.
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 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 ip≤jp for all p. But this occurs if and only if 2ip≤2jp 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 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:
For reflexivity, observe that for any x∈A, we have (f(x),f(x))∈R (by reflexivity of R). So (x,x)∈Rf.
For antisymmetry, let x,y be such that (x,y)∈Rf and (y,x)∈Rf. 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 Rf. 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)∈Rf.
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.