Homework 2

Emma Knight

Due: June 18th at 5PM EST

1 More on Unique Factorization

Problem 1. Recall that E = {. . . ,4,2, 0, 2, 4 . . .}, the set of even integers. In this problem, I

will use divides for the notion of “E-divides; that is, for a, b 2 E, I will say a|b i↵ there exists d 2 E

such that da = b.

(a) Find all the primes of E.

(b) Show that, while prime factorization in E isn’t unique, that any two factorizations of a number

in E have the same number of prime factors.

(c) Can you list all the prime factorizations of 2i3j in E (here, i and j are integers with i > 0

and j 0)? Can you relate the number of such factorizations to a counting problem?

The next two problems are about Q[x], which is the set of all polynomials over Q in the variable

x. This set has a lot of properties in common with the integers, and it is a useful exercise to think

about what properties of Z carry over to Q[x]. Firstly, there are a couple of definitions:

Definition 1. Let f = f(x) = aixi + ai1xi1 + · · ·+ a1x+ a0 be a nonzero polynomial.

The degree of f , written deg(f), is the degree of the largest nonzero term.

f is monic if the coecient in front of the largest nonzero term is 1.

Problem 2. This problem gives some basic properties of Q[x].

(a) Give some examples of prime polynomials in Q[x]. Can you show there are infinitely many

primes?

(b) Show that deg(fg) = deg(f)+deg(g), and that, if f+g 6= 0, then deg(f+g) max(deg(f), deg(g)).

When is this inequality strict?

1

(c) Show that every nonzero polynomial is the product of a constant polynomial and a monic

polynomial in a unique way.

Problem 3. Let f and g be nonzero polynomials in Q[x]. Show that there exists q and r 2 Q[x]

such that f = qg + r and either r = 0 or deg(r) < deg(f).

Additionally, explain how to modify the argument for the fundamental theorem of arithmatic to

show that Q[x] has unique factorization.

2 Congruences and the Ring Z/nZ

Problem 4. Verify that a ⌘ b (mod n) is an equivalence relation; that is, show that a ⌘ a (mod n)

for all a, that if a ⌘ b (mod n) then b ⌘ a (mod n) for all a and b, and that, if a ⌘ b (mod n) and

b ⌘ c (mod n) then a ⌘ c (mod n) for all a, b, and c.

Additionally, verify the assertion that starts chapter 8; that is, show that if a1 ⌘ a2 (mod n) and

b1 ⌘ b2 (mod n), then a1 ± b1 ⌘ a2 ± b2 (mod n) and a1b1 ⌘ a2b2 (mod n).

We define Z/nZ to be the set of equivalence classes of Z under the equivalence relation of congruence

mod n. The previous problem showed that this set has addition, multiplication, and subtraction.

It is left as a practice problem to show that these three operations satisfy the properties you expect

them to1.

Problem 5. Let a, n be integers.

(a) Without using Euler’s formula, show that (a, n) = 1 if and only if there exists a b 2 Z such

that ab ⌘ 1 (mod n). Such a number is called a unit mod n.

(b) Show that (a, n) > 1 if and only if there exists b 2 Z such that b 6⌘ 0 (mod n) and such that

ab ⌘ 0 (mod n). Such a number is called a zero-divisor mod n.

Problem 6. List all the primes less than 40 where 1 is a square (mod p). Do you see a pattern?

1The properties that they satisfy are the properties of a commutative ring with unity, in case you’ve heard that

term or want to look on Wikipedia.

2

欢迎咨询51作业君