1

Proof. First note that S has positive elements, for if s ∈ S and s≠0 (such an s exists since S has at least two different elements), then either s is positive or s - 2s is; the latter being guaranteed to be in S due to the closure of addition and subtraction.

As a subset of the well-ordered set ℕ, the set S ∩ ℕ -{0}, must have a least element, call it n. Certainly all integer multiples of n are in S as S is closed under addition and subtraction. So in the least,

(1.1)

Assume for later contradiction that there is an a ∈ S for which n ⁄|a. Then the division algorithm, since n≠0, yields the existence of q,r ∈ ℤ with 0 ≤ r < |n| such that a = qn + r. Therefore r = a - qn ∈ S by the closure of addition and subtraction on S. Since a was assumed to not be a multiple of n, then 0 < r < |n|, but this contradicts the fact that n is the least element of S ∩ ℕ -{0}. Thus, no such a exists, moreover all elements of S are multiples of n. Hence combining this with equation 1.1 leaves us with S = nℤ. __

(a)

This is surjective since any element of ℕ ∩S has the form mn and thus f will map m to it. The map is injective because if f(m) = f(m′) for m,m′∈ ℕ, then nm = nm′ and thus m = m′. So f is a bijection.

Because multiplication by a nonzero natural number preserves order, then f is an order-preserving map as it simply multiplies its input by the nonzero natural number n.

Finally to prove uniqueness, let g : ℕ → ℕ ∩S be an order-preserving bijection. We first note that g(0) = 0 because 0 is the least element of both ℕ and ℕ ∩ S; any other output for g would contradict its given order-preservation. Now assume that there exists an N such that for all k with 0 ≤ k < N we have g(k) = f(k). Define ℓ by ℓ = min{j ∈ S ∩ ℕ∣j ≥ f(N) = mN}, remembering that S = nℤ. We know ℓ exists since S ∩ ℕ is a subset of the well-ordered set ℕ. Thus f(k) = mk < ℓ for all k such that 0 ≤ k < N, and therefore since f is an order-preserving bijection, f(N) = ℓ. However, the inductive hypothesis implies that g, being an order-preserving bijection, must also have that g(N) = ℓ. Hence g and f are one in the same.

(b)

(c)

So assume that H has at least two distinct elements. Define S = {n∣gⁿ ∈ H}. The set S then also has at least two different elements. Now for n,m ∈ S we have that gⁿ,g^m ∈ H which implies that gⁿg^m = g^n+m ∈ H as H is a group. Hence n + m ∈ S implying the closure of S under addition. Also since H is a group, (g^m)^-1 = g^-m ∈ H informing us that n-m ∈ S. Hence S is closed under subtraction. In summary, S is a set with at least two different elements which is closed under addition and subtraction.

Thus by parts (a) and (b) of this problem, we have a unique order-preserving map, f : ℕ → S ∩ ℕ, for which every element of S is an integer multiple of f(1). In other words, for every gⁿ ∈ H, there is some integer a such that gⁿ = g^af(1) = ^a. Hence g^f(1) generates H.

2

(a)

So let’s proceed assuming that a≠b. With this, we know that S has at least two elements, thereby allowing us to make use of the problem 1. So let fℕ → ℕ ∩ S be the unique order-preserving bijection, and define c to be f(1). So for any d that divides a and b, d will also divide every element of S. This will include c since part (b) of problem 1 states that c generates all of S and c is therefore contained in S. So d divides c.

Relation of gcd(a,b) to S The greatest common divisor of a,b is the value c such that c generates S = ⟨a,b⟩.

(b)

(c)

Every nonzero integer can be decomposed into ±1p₁^e₁p_m^e+m We will first prove this for positive integers, then for negative ones.

As a base case we have that for 1 or any positive prime p, the decomposition is 1 and p, respectively. So let n ∈ ℕ be composite and assume that all natural numbers less than n can be decomposed as per above. Then we can find positive integers q,r < n such that qr = n. By the inductive hypothesis, then q and r can be decomposed into ± a product powers of primes. Hence so can n, namely the decomposition produced by the product of the decomposition of q and r.

As for a negative integer, m, the above proof for decomposition of positive integers informs us that there is such a decomposition for |m|, and thus simply negating the decomposition yields a decomposition for m.

The decomposition is unique. As a base case we have that for 1 or any positive prime p, the decomposition 1 and p, respectively, are unique. So let n ∈ ℕ be composite and assume that all natural numbers less than n can be uniquely decomposed. Let p₁^e₁p_a^e_a and q₁^f₁q_b^f_b be decompositions of n. Therefore p₁ must divide q₁^f₁q_b^f_b since both decompositions are equal, in other words, there is some q_i equal to p₁. Thus p₁^e₁-1p_a^e_a and q₁^f₁q_i^f_i-1q_b^f_b are equal, but these integers are less than n, which our inductive hypothesis tells us that their prime decompositions are unique. Therefore their multiplication by p₁ = q_i will be unique decompositions of n.

As for a negative integer, m, the above proof for unique decomposition of positive integers informs us that there is such a unique positive decomposition for |m|, and thus simply negating the it yields a unique decomposition for m.¹

3

(3.2)

As multiples of m and n, respectively, bum and avn have that

which when combined with Equation 3.2, yields

Thus the desired formula for c is c = avn + bum

4

(a)

In class we saw that the canonical addition and multiplication operations in ℤ∕9ℤ are compatible with the addition and multiplication operations of the integers. This yields to us

however, 1 ≡ 10 mod 9, leaving us with

again using the compatibility of addition in ℤ∕9ℤ with integer addition.

(b)

Formula for 11 We can see that 10 is a unit of ℤ∕11ℤ with order 2 in ^×. Therefore 10²ⁱ ≡ 10 mod 11 and 10²ⁱ⁺¹ ≡ 1 mod 11 for integer i. We can also say that d_i = 0 when i > n, and because of it, we can write

which implies

Formula for 7 Similar to the above method for 11, 10 is a unit of ℤ∕7ℤ with order 6 in ^×. Therefore

which results in the following after modding by 7

5

(a) Prove Euler’s totient function is multiplicative

Now let m ∈^×. Then there exists some integer r such that mr ≡ 1 mod (n). Then problem 1 implies the existence of an s such that mr = ns + 1, i.e. mr + n(-s) = 1. Hence gcd(m,n) = 1 and therefore m and n are coprime.

Combining these two results implies that an integer m is coprime to an integer n if and only if m ∈^×. This allots us the following equation

(5.3)

The multiplicativity of ϕ According to [Cha13] the Chinese Remainder Theorem tells us that for an integer n ≥ 2 with prime factorization n = p₁^e₁p_a^e_a, ℤ∕nℤ is isomorphic to (ℤ∕p₁^e₁ℤ) ×× (ℤ∕p_a^e_aℤ). This in turn implies (ℤ∕nℤ)^× is isomorphic to (ℤ∕p₁^e₁ℤ)^××× (ℤ∕p_a^e_aℤ)^×. Let m and n be coprime with prime factorizations p₁^e₁p_a^e_a and q₁^f₁q_b^f_b, respectively. Therefore the prime factors of their prime factorization have that p_i≠q_j for each possible i,j. Now according to equation 5.3, ϕ(mn) = |ℤ∕mnℤ|, and thus we have the following sequence of equations.

(b)

(5.4)

Given Equation 5.4 and the fact that ϕ is multiplicative from the previous part of the problem, then for any n with prime decomposition of p₁^e₁p₂^e₂p_m^e_m where each p_i is distinct, we have the formula

References