Math 502: Abstract Algebra

Homework 1
Lawrence Tyler Rush
<me@tylerlogic.com>
February 1, 2014
http://coursework.tylerlogic.com/courses/upenn/math502/homework01

1


First, a helpful Lemma. Let S be defined as in the problem’s specification.

Lemma 1.1. The set S is nfor some n >0.

Proof. First note that S has positive elements, for if s S and s0 (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,

nℤ ⊆ S
(1.1)

Assume for later contradiction that there is an a S for which n ⁄|a. Then the division algorithm, since n0, 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)


Given that S = nby Lemma 1.1, define f : S by
f(m ) = mn

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 = nmand 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)


The fact that every element of S is a multiple of f(1) follows directory from Lemma 1.1, the fact that n generates n, and the construction of f, namely f(1) = n.

(c)


Let G be a cyclic group with subgroup H and generator g. If H is trivially {1}, then we are done, as 1 generates H.

So assume that H has at least two distinct elements. Define S = {ngn H}. The set S then also has at least two different elements. Now for n,m S we have that gn,gm H which implies that gngm = gn+m H as H is a group. Hence n + m S implying the closure of S under addition. Also since H is a group, (gm)-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 gn H, there is some integer a such that gn = gaf(1) = (gf(1))a. Hence gf(1) generates H.

2


(a)


Let a,b be nonzero, and S be the set {ar + bsr,s }. If a = b, then the existence of the greatest common divisor of a,a is trivial since the a would be the integer such that any other integer which divides a also divides a.

So let’s proceed assuming that ab. With this, we know that S has at least two elements, thereby allowing us to make use of the problem 1. So let fS 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)


Let a,b be relatively prime non-zero integers and c an integer such that a|bc. Let as + cr ∈⟨a,cfor some s,r . Since a and b are relatively prime, their greatest common divisor is 1, meaning that a,b= 1= . Therefore r ∈⟨a,b. However, for n,m such that an + bm = r, this implies that as + cr = as + c(an + bm) = as + can + cbm. Thus a divides as + cr, since a|bc, and therefore every element of a,c, including a(0) + c(1) = c is divisible by a.

(c)


We will define a prime according to Jacobson [Jac09, pg. 22] as an integer p0,±1 with ±p and ±1 being its only divisors.

Every nonzero integer can be decomposed into ±1p1e1⋅⋅⋅pme+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 p1e1⋅⋅⋅paea and q1f1⋅⋅⋅qbfb be decompositions of n. Therefore p1 must divide q1f1⋅⋅⋅qbfb since both decompositions are equal, in other words, there is some qi equal to p1. Thus p1e1-1⋅⋅⋅paea and q1f1⋅⋅⋅qifi-1⋅⋅⋅qbfb 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 p1 = qi 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.1

3


Suppose that m,n are integers that are relatively prime. From problem two, we know that there exist integers u,v such that um + vn = 1. From this we obtain that um + vn 1 mod n, but since vn is a multiple of n this yields um 1 mod n. Similarly we obtain vn 1 mod m. These two equations in turn give us that for some integers a,b,
bum ≡ b mod n   and   avn ≡ a mod m
(3.2)

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

bum ≡ 0 mod m   and   avn ≡ 0 mod n

which when combined with Equation 3.2, yields

avn+ bum ≡ a mod m and avn +bum  ≡ b mod n

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

4


(a)


Let a be a n + 1 decimal digit number. Let the decimal digits of a be represented by d0,d1,,dn where each di is in {0,1,,9} and d0 corresponds to the lowest magnitude digit, and dn, the highest. Then we have that
    ∑n
a =    di10i
    i=0

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

   ( ∑n     )         n∑                       ∑n
a ≡     di10i  mod 9 =    (di mod 9)(10i mod 9) =  (di mod 9)(10 mod 9)⋅⋅⋅(10 mod 9)
     i=0               i=0                      i=0         ◟---------◝◜--------◞
                                                                   i times

however, 1 10 mod 9, leaving us with

                  (     )
   ∑n              ∑n
a ≡   (di mod 9) =    di  mod 9
   i=0             i=0

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

(b)


Let a be a n + 1 decimal digit number. Let the decimal digits of a be represented by d0,d1,,dn where each di is in {0,1,,9} and d0 corresponds to the lowest magnitude digit, and dn, the highest.

Formula for 11 We can see that 10 is a unit of 11with order 2 in (ℤ∕11ℤ)×. Therefore 102i 10 mod 11 and 102i+1 1 mod 11 for integer i. We can also say that di = 0 when i > n, and because of it, we can write

   ∑n        ∑n         ∑n
a =    di10i =   d2i102i +   d2i+1102i+1
    i=0       i=0        i=0

which implies

   ( ∑n         ∑n           )         ∑n                 ∑n                        ∑n     ∑n
a ≡     d2i102i +   d2i+1102i+1   mod 11 ≡   d2i(102i mod 11)+   d2i+1 (102i+1 mod 11) ≡ 10  d2i+   d2i+1
     i=0        i=0                    i=0                i=0                       i=0    i=0

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

100  ≡  1 mod 7
101  ≡  3 mod 7
  2
10   ≡  2 mod 7
103  ≡  6 mod 7
104  ≡  4 mod 7
105  ≡  5 mod 7
We can again also say that di = 0 when i > n, and because of it, we can write
   ∑n        ∑n         ∑n             n∑             ∑n             ∑n             n∑
a =   di10i =   d6i106i+    d6i+1106i+1 +    d6i+2106i+2+    d6i+3106i+3+    d6i+4106i+4 +    d6i+5106i+5
   i=0       i=0        i=0            i=0            i=0            i=0            i=0

which results in the following after modding by 7

    ∑n       ∑n         ∑n         ∑n         ∑n         ∑n
a =    d6i + 3  d6i+1 + 2   d6i+2 + 6   d6i+3 + 4   d6i+4 + 5   d6i+5
    i=0      i=0        i=0        i=0        i=0        i=0

5


(a) Prove Euler’s totient function is multiplicative


First, let m and n be coprime integers. Then problem 1 informs use that there are intgers r,s such that mr + ns = 1 or in other words mr = n(-s) + 1, which implies mr 1 mod n. Hence m (ℤ ∕nℤ)×.

Now let m (ℤ ∕n ℤ)×. 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 (ℤ ∕nℤ)×. This allots us the following equation

      ||      ×||
ϕ(n) = |(ℤ∕nℤ) |
(5.3)

The multiplicativity of ϕ According to [Cha13] the Chinese Remainder Theorem tells us that for an integer n 2 with prime factorization n = p1e1⋅⋅⋅paea, ∕nis isomorphic to (∕p1e1) ×⋅⋅⋅× (∕paea). This in turn implies (∕n)× is isomorphic to (∕p1e1)××⋅⋅⋅× (∕paea)×. Let m and n be coprime with prime factorizations p1e1⋅⋅⋅paea and q1f1⋅⋅⋅qbfb, respectively. Therefore the prime factors of their prime factorization have that piqj for each possible i,j. Now according to equation 5.3, ϕ(mn) = |∕mn|, and thus we have the following sequence of equations.

           |                                                   |
ϕ(mn )  =  ||(ℤ ∕pe1ℤ)× × ⋅⋅⋅× (ℤ∕peaℤ)× ×(ℤ∕qf1ℤ)× × ⋅⋅⋅× (ℤ∕qfbℤ)×||
                1              a     |    1               b     |
        =  ||(ℤ ∕pe1ℤ)× × ⋅⋅⋅× (ℤ∕peaℤ)×||||(ℤ∕qf1ℤ)× × ⋅⋅⋅× (ℤ ∕qfbℤ)× ||
           |    1              a    ||    1               b     |
           ||      × ||||     × ||
        =  |(ℤ ∕mℤ ) ||(ℤ∕nℤ ) |
        =  ϕ(m )ϕ(n)

(b)


Let’s first examine the value of ϕ(pe) for prime p and positive e (note negative e is pointless to consider as it isn’t an integer). The value of ϕ(pe) will be the number of integers between 1 and pe which are coprime to pe, but the only such integers are the positive multiples of p less than or equal to pe. There are pe-1 of them, namely p,2p,3p,,(pe-1)p. Hence, because there are pe postive integers less than or equal to pe
   e    e   e-1   e-1
ϕ(p ) = p - p  = p   (p- 1)
(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 p1e1p2e2⋅⋅⋅pmem where each pi is distinct, we have the formula

ϕ(n) = ϕ(pe11pe22 ⋅⋅⋅pemm) = ϕ (pe11)ϕ(pe22)⋅⋅⋅ϕ(pemm) = pe11-1(p1 - 1)pe22-1(p2 - 1)⋅⋅⋅pemm -1(pm - 1)

References


[Cha13]   Ching-li Chai. Excursion in elementary number theory. http://www.math.upenn.edu/~chai/502f13/course_notes/nber_thy.pdf, 2013.

[Jac09]    Nathan Jacobson. Basic Algebra I. Basic Algebra. Dover Publications, Incorporated, 2009.