MATH 115: ELEMENTARY NUMBER THEORY HOMEWORKS # 1–2

JOHN VOIGHT

Homework #1 (Due June 28):

• §1.1: 4, 5, 8, 9; 1.1A: A set S ⊂ ℝ is well-ordered if for every subset T ⊂ S, T has a least element.

(a) Show that the sets

ℤ_{<0} = {−1, −2, −3, … }

and

{1/n : n ∈ ℤ_{>0}} = {1, 1/2, 1/3, 1/4, 1/5, … }

are not well-ordered.

(b) Show that if S ⊂ ℝ is well-ordered, then S cannot contain a decreasing

sequence of distinct real numbers.

• §1.4: 6, 7, 8, 17, 18, 36, 46

• §3.1: 6, 7, 10, 11, 16; 3.1A: Let p_{1} = 2, p_{2} = 3, … be the sequence of increasing primes, so that p_{n} is the nth prime. Is the number P_{n} = p_{1}p_{2} ⋯ p_{n} +1 itself always prime? 3.1B: For x ∈ ℝ_{>0}, let s(x) denote the number of positive square integers not exceeding x, namely

s(x) = #{n^{2} ≤ x : n ∈ ℤ_{>0}}

Show that s(x) ∼ \sqrt{x}.

• §3.2: 5, 6, 8, 9, 16

Homework #2 (Due July 6, no class Monday, July 5):

• §3.3: 1(a), 1(d), 3(a), 3(d), 9; 3.3A: Let f_{0} = 1, f_{1} = 1, f_{i+1} = f_{i} + f_{i−1} (for i > 0) be the sequence of Fibonacci numbers. Prove that f_{i} < f_{i+2}/2 for all i > 0. [Hint: Use Theorem 3.11 or prove it directly.] 3.3B: Assume that the limit

α = lim_{i→∞} \frac{f_{i+1}}{f_{i}}

exists. Show that α = (1 + \sqrt{5})/2. [This explains where α comes from in Example 1.24.]

• §3.4: 2, 4(d), 7, 10, 19–22, 39, 44, 47

• §4.1: 4, 8, 16, 17, 20, 26

• §3.6: 1(a)–(c); 3.6A: Find all integers x, y ∈ ℤ for which

x^{2} = 4y^{2} + 9.