# MATH PROBLEM SET 1

Key: (E) denotes easy. If you honestly feel the problem is
too easy, just write

"okay", but try to solve some harder problems as well.

1.1)(E) Prove the Division Theorem: If a ≥ b > 0 are integers, then there exist

unique non-negative integers q and r such that a = qb + r and 0 ≤ r < b. Hint:

It suffices to take q to be the largest non-negative integer such that a − qb ≥ 0.

1.2)(E) In the notation of Problem 1.1), show that b|a
r = 0.

1.3) Prove the converse of Euclid's Lemma: suppose d is a positive integer such

that whenever d|ab, d|a or d|b. Then d is prime.

Remark: Among other things, this allows us to generalize the notion of primes

to not-necessarily principal ideals.

1.4)a)(E) "To contain is to divide": for integers a and b, we have
.

b) Confirm that part a) holds true for elements a and b in any commutative ring.

c) For elements a, b in an integral domain R, show that the following are
equivalent:

(i) There exists a unit such that b = ua.

(ii) There exist units such that b = ua, a = vb.

(iii) a | b and b | a.

(iv) There is an equality of principal ideals (a) = (b).

d)* Find a commutative ring R (not an integral domain) and elements a and b such

that in part c) above, (iii) and (iv) hold but (i) and (ii) do not. In other
words, in

a general commutative ring, being associates is a stronger relation than
generating

the same principal ideal.

1.5) Prove or disprove: The gcd(0, 0) does not exist. In other words, when a = b
= 0,

there is no integer d such that for all integers e, if e | a & e | b, then e |
d.

The next exercise concerns the rng E = 2Z of all even integers.

1.6) Give a necessary and sufficient condition on a positive element x ∈ E to
have

two different factorizations into positive E-primes. Hint: pay attention to

and also to the number of odd primes dividing x.

1.7) Prove Proposition 12 , about

the basic properties of the functions.

1.8) Complete the proof that is never an
integer by showing

that for all n ≥1, .

1.9)** Show that except for n = 1, 2, 6, the decimal expansion of
is
nonterminating.

(I.e., show that except for these values, for some prime

p ≠ 2, 5.)

1.10) For any nonzero integers a and b, show that

gcd(a, b) ยท lcm(a, b) = ab.

1.11) For integers a and b, show that the intersection of the two ideals (a) ∩
(b)

is an ideal of Z. In fact, if you know the definition of an ideal in a
commutative

ring, show that the intersection of any two (or more. . .) ideals is always an
ideal.3

Because Z is a PID, we must have (a) ∩ (b) = (c) for some c ∈ Z, well-determined

up to a sign. What is c in terms of a and b?

1.11.5) a) Let be a (finite) set of integers. Define the greatest
common

divisor gcd() of the set, and show that it exists and is unique up
to

a sign. In fact, show that the set

is an ideal of Z, and that the positive generator of this (necessarily
principal!) ideal

is the gcd we are looking for.

b) Define lcm(), show it exists, and explain how to get it from
the ideals

1.12) Show that .

2.13)* Find an identity relating and
. Can

you extend this to more than three numbers? (Hint: inclusion/exclusion.)

1.14) One says that a set of integers is **
relatively prime in pairs**

if for all i ≠ j, .

a) Show that if are relatively prime in pairs, then gcd() = 1.

b) Show that the converse does not hold when n ≥ 3: indeed, find the smallest

example of three integers which are not simultaneously divisible by any d > 1
but

for which any two have a nontrivial common divisor.

Remark: The phrase "let be relatively prime integers" is
therefore ambiguous

when n ≥ 3. Probably it ought to mean the weaker condition that

gcd() = 1 but careful authors rephrase to avoid the ambiguity. If
you

hear someone say it, stop and ask them which one they mean!

1.15) Prove the rational roots theorem: if

is a polynomial with integer coefficients, the only possible rational roots are
of the

form where and
. Explain how
this gives yet another proof of, e.g.,

the irrationality of .

1.16) a) Show that is irrational.

b)* Let a, b ∈ . Give a criterion for the irrationality of
.

G1.1) Let F be a field and let be a surjective map satisfying
properties

a) and b) of Proposition 12; v is said to be a **discrete valuation** of F.

a) Let . Show that is a subring of F, the

**valuation ring**. (It is common to formally set v(0) = ∞ to avoid having to keep

"manually inserting 0.")

b) Since v is surjective, there is an element π ∈ with v( π) = 1. Show that for

any n ≥1,

the principal ideal of generated by
(of course π^{0} = 1).

c) Show that every ideal of is of the form ( π^{n})
for a suitable n ∈ N. In particular,

every ideal of is principal, and there is a
unique maximal ideal, (π ).

d) When F = Q,
,
what is the valuation ring ?

e) Suppose k is a field, and consider F = k(t), the quotient field of the ring
of

polynomials k[t] with coefficients in k. Show that the map v which takes a
rational

function to deg(q(x))−deg(p(x)) is a
discrete valuation of k(t). Note that this

is consistent with our previous convention that the degree of the zero
polynomial

is −∞!