Math 330: Number Systems
Additional Homework Sets
and Minor Projects

An integer n is called even if it is divisible by 2, i.e., if there exists an integer k such that n = 2k.

• [Q] Is 0 even? Why or why not?

• [A] If m and n are even then m+n and mn are even.
• [B] For any natural number n, n²+n is even.
• [C] For any natural number n, n is even or n+1 is even.
• [D] For any integer n, n is even or n+1 is even.

Suppose you have two integers m, n (not both 0). The greatest common divisor gcd(m,n) is defined as the largest integer that is a divisor of both m and n. Now define two sets of integers:
        S_m,n := { mx+ny : x, y in Z }
and
        T_m,n := { mx+ny : x, y in Z and mx+ny is positive }.
(That is, T_m,n consists of the positive integers in S_m,n.)

Theorem 2G. The smallest number in T_m,n is gcd(m,n).

We won't prove this, but there are some questions about it.
Added 9/28: You may not use Theorem 2G to solve these problems. Reasons: (a) We haven't proved that theorem. (b) It would be circular reasoning, since the proof of the theorem requires [A]. (c) I want you to study the actual sets and gcd's, and not just apply a general theorem. That's how you understand theorems: see how they work in examples.

• [A] Prove that T_m,n does contain a smallest number.
• [B] Let n be any positive integer. Find the set T_0,n . Find the smallest positive integer in it. Is it gcd(0,n)? What is gcd(0,n), anyway?
• [C] Let n be any positive integer. What is gcd(1,n)? Find the set T_1,n . Find the smallest positive integer in it. Is it gcd(1,n)?
• [D] We noticed in class that gcd(9,12)=3. Find T_9,12 . Find the smallest positive integer in it. Is it gcd(9,12)?

Do the following problems.

• [U] Prove that any non-empty set of integers, bounded above, has a largest element.
• [V] In example 4.1, what is x₂₀?
• [W] In example 4.2, if x₁ = 23, what is x₁₀?
• [X] Find a simple formula for   ∑_k=1ⁿ   1.     Prove it using the definition (page 42).
• [Y] Prove propositions 4.4 & 4.6(i).
• [Z] Do project 4.8.

Do the following problems.

• [A] Prove propositions 4.6(ii) & 4.9(i).
• [B] Do project 4.7.
• [C] Prove that for any natural number k,     ∑_j=1^k   2^j   =   2^k+1 − 2.
• [D] Restate in a formal logical way:
  • Every odd natural number is a square number.

(a) with quantifiers without an implication,
(b) with an implication (and with quantifiers if necessary).
Then:
(c) negate both statements and
(d) compare the negations.

Do the following problems.

• [E] In Homework Set 5 we defined "even" integers. How would you define "odd" integers? Explain why this is a good definition, or if you're not sure, why you have doubts.
• [F] For each of the following sets, find max A and min A, if possible. (See page 31.) You can use ordinary arithmetic freely to figure out what numbers are in the sets. The purpose of this question is to practice the concepts of minimum and maximum elements of a set.
  1. A = { (-1)⁰, (-1)¹, (-1)², (-1)³, ... }.
  2. A = { 1⁰, 1¹, 1², 1³, ... }.
  3. A = { 2⁰, 2¹, 2², 2³, ... }.
  4. A = { 2⁰, 2¹, 2², 2³, ... , 2¹⁰ }.
  5. A = { (1/2)⁰, (1/2)¹, (1/2)², (1/2)³, ... }.
  6. A = { (1/2)⁰, (1/2)¹, (1/2)², (1/2)³, ... , (1/2)¹⁰ }.
  7. A = { x in Z : x has two different prime factors }.
  8. A = { x in Z : x³ < x }.
  9. A = { x in N : x³ < x }.
• [G] Write each of the sets in [F] as a sequence (a_j). Don't forget to state the range of your index (i.e., subscript).

Definition: Let's say the "real natural numbers" are a set N_R such that N_R is a subset of R and:

1. 1 is in N_R .
2. If n is in N_R , then n+1 is in N_R .
3. 0 is not in N_R ,
4. For every n in R such that n is not 0, we have n in N_R or −n in N_R .
5. If a subset A contained in R satisfies (i) and (ii) then N_R is contained in A.

The x+1 Problem. Define a sequence of numbers, x₁, x₂, x₃, ..., by the following rule:
x_n+1 = x_n +1 if x_n is odd,
x_n+1 = x_n/2 if x_n is even.
Does this sequence always reach 1 for any starting point x₁ in N?

The project is to answer this question. You may produce a proof, or a disproof.



The 5x+1 Problem. Let x_n+1 = 5x_n +1 if x_n is odd, x_n/2 if x_n is even. Does this sequence always reach 1 for any starting point x₁ in N?
Do some examples, turn them in, I'll look at them, and we'll see if we can guess anything about it. I don't know any more than you do!