Solutions Manual for Elementary Number Theory (5th Edition) by Goddard & Rosen – Step-by-Step Exercise Solutions

SOLUTIONS MANUAL

,SOLUTIONS MANUAL TO ACCOMPANY ELEMENTARY NUMBER THEORY AND ITS APPLICATIONS 5TH
EDITION Bart Goddard Kenneth H. .Rosen AT&T Laibs
CHAPTER 1


The Integers
1.1. Numbers, Sequences, and Sums
1.1.1. a. The set of integers greater than 3 is well-ordered. Every subset of this set is also a subset of the set
of positive integers, and hence must have a least element.

b. The set of even positive integers is well-ordered. Every subset of this set is also a subset of the set
of positive integers, and hence must have a least element.

c. The set of positive rational numbers is not well-ordered. This set does not have a least element.
If a/b were the least positive rational number then a/(b + a) would be a smaller positive rational
number, which is a contradiction.

d. The set of positive rational numbers of the form a/2 is well-ordered. Consider a subset of numbers
of this form. The set of numerators of the numbers in this subset is a subset of the set of positive
integers, so it must have a least element b. Then b/2 is the least element of the subset.

e. The set of nonnegative rational numbers is not well-ordered. The set of positive rational numbers
is a subset with no least element, as shown in part c.

1.1.2. Let S be the set of all positive integers of the form a
— bk. S is not empty since a— b(—1) = a + b is a
positive integer. Then the well-ordering principle implies that S has a least element, which is the num-
ber we’re looking for.

1.1.3. Suppose that x and y are rational numbers. Then x = a/b and y = c/d, where a, b, c, and d are integers
with b /= 0 and d /= 0. Then xy = (a/b) ·(c/d) = ac/bd and x + y = a/b + c/d = (ad + bc)/bd where bd =/
0. Since both x + y and xy are ratios of integers, they are both rational.

1.1.4.a. Suppose that x is rational and y is irrational. Then there exist integers a and b such that x = ba where
a and b are integers with b/= 0. Suppose that x + y is rational. Then there exist integers c and d with
d /= 0 such that x + y = dc . This implies that y = (x + y)— x = (a/b) —(c/d) = (ad —bc)/bd, which
means that y is rational, a contradiction. Hence x + y is irrational.
√ √
b. This is false. A counterexample is given by 2 + (— 2) = 0.
√
c. This is false. A counterexample is given by 0 · 2 = 0.
√ √
d. This is false. A counterexample is given by 2· 2 = 2.
√ √
1.1.5. Suppose that 3 were rational. Then there would exist positive integers a and b with 3 = a/b. Con-
√ √ √
sequently, the setS = {k 3 | kand k 3 are positive integers} is nonempty sincea = b 3. Therefore, by
√ √ √ √
the well-ordering property,S has a smallest element, says =t 3. We haves 3— s =s 3— t 3 = (s —
t s t s s —s s—t
√ √ √ √
) 3. Since 3 = 3√and are both √ integers,√ 3 = ( ) 3 must also be √ an integer.
√ Furthermore,
√
it is positive, since 3 = ( 3 1) and 3 1. It is less than since = 3, 3 = 3 , and 3
s —s s — > s s t s√ t <
3. This contradicts the choice of s as the smallest positive integer in S. It follows that 3 is irrational.

,1.1.6. Let S be a set of negative integers. Then the set T = {—s : s ∈ S} is a set of positive integers. By the
well-ordering principle, T has a least element t0. We prove that —t0 is a greatest element of S. First note

, 2 1. THE INTEGERS


that since t0 ∈ S, then t0 = —s0 for some s0 ∈ S. Then — t0 = s0 ∈ S. Second, if s ∈ S, then —s ∈ T , so
t0 ≤ —
s. Multiplying by 1—yields s ≤t0— . Since the choice of s was arbitrary, we see that —t0 is greater
than or equal to every element of S.

1.1.7. a. Since 0 ≤ 1/4 < 1, we have [1/4] = 0.

b. Since —1 ≤ —3/4 < 0, we have [—3/4] = —1.

c. Since 3 ≤ 22/7 < 4, we have [22/7] = 3.

d. Since —2 ≤ —2 < —1, we have [—2] = —2.

e. We compute [1/2 + [1/2]] = [1/2 + 0] = [1/2] = 0.

f. We compute [—3 + [—1/2]] = [—3 — 1] = [—4] = —4.

1.1.8. a. Since —1 ≤ —1/4 < 0, we have [—1/4] = —1.

b. Since —4 ≤ —22/7 < —3, we have [—22/7] = —4.

c. Since 1 ≤ 5/4 < 2, we have [5/4] = 1.

d. We compute [[1/2]] = [0] = 0.

e. We compute [[3/2] + [—3/2]] = [1 + (—2)] = [—1] = —1.

f. We compute [3 — [1/2]] = [3 — 0] = [3] = 3.

1.1.9. a. Since [8/5] = 1, we have {8/5} = 8/5 — [8/5] = 8/5 — 1 = 3/5.

b. Since [1/7] = 0, we have {1/7} = 1/7 — [1/7] = 1/7 — 0 = 1/7.

c. Since [—11/4] = —3, we have {—11/4} = —11/4 — [—11/4] = —11/4 — (—3) = 1/4.

d. Since [7] = 7, we have {7} = 7 — [7] = 7 — 7 = 0.

1.1.10. a. Since [—8/5] = —2, we have {—8/5} = —8/5 — [—8/5] = —8/5 — (—2) = 2/5.

b. Since [22/7] = 3, we have {22/7} = 22/7 — [22/7] = 22/7 — 3 = 1/7.

c. Since [—1] = —1, we have {—1} = —1 — [—1] = —1 — 1 = 0.

d. Since [—1/3] = —1, we have {—1/3} = —1/3 — [—1/3] = —1/3 — (—1) = 2/3.

1.1.11. If x is an integer, then [x] + [—x] = x — x = 0. Otherwise, x = z + r, where z is an integer and r is a
real number with 0 < r < 1. In this case, [x] + [—x] = [z + r] + [—z — r] = z + (—z — 1) = —1.

1.1.12. Let x = [x] + r where 0 ≤ r < 1. We consider two cases. First suppose that r < 21 . Then x + 12 =
[x] + (r + 1 ) < [x] + 1 since r + 1 < 1. It follows that [x + 1 ] = [x]. Also 2x = 2[x] + 2r < 2[x] + 1
2 2 2
since 2r < 1. Hence [2x] = 2[x]. It follows that [x] + [x + 12] = [2x]. Next suppose that 21 ≤ r < 1. Then
[x] + 1 ≤ x + (r + 12) < [x] + 2, so that [x + 1 2] = [x] + 1. Also 2[x] + 1 ≤ 2[x] + 2r = 2([x] + r) = 2x <
2[x] + 2 so that [2x] = 2[x] + 1. It follows that [x] + [x +21 ] = [x] + [x] + 1 = 2[x] + 1 = [2x].

1.1.13. We have [x]≤ x and [y] ≤ y. Adding these two inequalities gives [x] + [y]≤ x + y. Hence [x + y] ≥
[[x] + [y]] = [x] + [y].