1.5: Exercises

Exercise \(\PageIndex{1}\)

Apply Eratosthenes’ Sieve to get all prime numbers between 1 and 200. (Hint: you should get 25 primes less than 100, and 21 between 100 and 200.)

Exercise \(\PageIndex{2}\)

Factor the following into prime numbers (write as a product of primes): 393, 16000, 5041, 1111, 1763, 720.

Exercise \(\PageIndex{3}\)

Find pairs of primes that differ by 2. These are called twin primes. Are there infinitely many such pairs? (Hint: This is an open problem; the affirmative answer is called the twin prime conjecture.)

Exercise \(\PageIndex{4}\): Goldbach Conjecture

Show that small enough even integers can be written as the sum of two primes. Is this always true? (Hint: This is an open problem; the affirmative answer is called the Goldbach conjecture.)

Exercise \(\PageIndex{5}\)

Comment on the types of numbers (rational, irrational, transcendental) we use in daily life.

1. What numbers do we use to pay our bills?
2. What numbers do we use in computer simulations of complex processes?
3. What numbers do we use to measure physical things?
4. Give examples of the usage of the “other” numbers.

Exercise \(\PageIndex{6}\)

Let \(a\) and \(b\) be rationals and \(x\) and \(y\) irrationals.

1. Show that \(ax\) is irrational iff \(a \ne 0\).
2. Show that \(b+x\) is irrational.
3. Show that \(ax+b\) is irrational iff \(a \ne 0\).
4. Conclude that \(a \sqrt{2}+b\) is irrational iff \(a \ne 0\).

Exercise \(\PageIndex{7}\)

Show that \(\sqrt{3}, \sqrt{5}\), etcetera (square roots of primes) are irrational.

Exercise \(\PageIndex{8}\)

Show that numbers of the form that \(a\sqrt{2}+b\) are irrational and dense in the reals (\(a\) and \(b\) are rational).

Exercise \(\PageIndex{9}\)

1. Use an pictorial argument similar to that of Figure 2 to show that \(\mathbb{N} \times \mathbb{N}\) (the set of lattice points \((n, m)\) with \(n\) and \(m\) in \(\mathbb{N}\)) is countable.
2. Suppose \(A_{i}\) are countably infinite sets where \(i \in I\) and \(I\) countable. Show that there is a bijection \(f_{i} : \mathbb{N} \rightarrow A_{i}\) for each \(i\).
3. Show there is a bijection \(F : \mathbb{N} \times \mathbb{N} \rightarrow \bigcup_{i \in I} A_{i}\) given by \(F(n, m) = f_{n}(m)\).
4. Conclude that the countable union of countably infinite sets is countably infinite.

Exercise \(\PageIndex{10}\)

What is wrong in the following attempt to prove that \([0, 1]\) is uncountable?
Assume that \([0, 1]\) is countable, that is: there is a bijection \(f\) between \([0, 1]\) and \(\mathbb{N}\). Let \(r(n)\) be the unique number in \([0, 1]\) assigned to \(n\). Thus the infinite array \((r(1), r(2), \cdots)\) forms an exhaustive list of the numbers in \([0, 1]\), as follows:

\[r(1) = 0. \textbf{0} 0000000000 \dots \nonumber\]

\[r(2) = 0.1 \textbf{0} 101010111 \dots \nonumber\]

\[r(3) = 0.00 \textbf{0} 11111111 \dots \nonumber\]

\[r(4) = 0.111 \textbf{1} 1100000 \dots \nonumber\]

\[r(5) = 0.0001 \textbf{0} 010010 \dots \nonumber\]

\[r(6) = 0.10000 \textbf{1} 00011 \dots \nonumber\]

\[\vdots \nonumber\]

(Written as number on the base 2.) Construct \(r^{∗}\) as the string whose nth digit differs from that of \(r(n)\). Thus in this example: \(r^{∗} = 0. \textbf{111010} \dots\),

which is different from all the other listed binary numbers in \([0, 1]\). (Hint: what if \(r^{∗}\) ends with an infinite all ones subsequence?)

Exercise \(\PageIndex{11}\)

The set \(f(T)\) in the proof of Theorem 1.20 is called the middle third Cantor set. Find its construction. What does it look like? (Hint: locate the set of numbers whose first digit (base 3) is a 1; then the set of numbers whose second digit is a 1.)

Exercise \(\PageIndex{12}\)

The integers exhibit many, many other intriguing patterns. Given the following function:

\[\begin{equation} \left\{ \begin{array}{cc} {n \mbox{ even: }}&{f(n) = \frac{n}{2}}\\ {n \mbox{ odd: }}&{f(n) = \frac{3n+1}{2}} \end{array} \right. \end{equation}\]

a) (Periodic orbit) Show that \(f\) sends 1 to 2 and 2 to 1.
b) (Periodic orbit attracts) Show that if you start with a small positive inte- ger and apply f repeatedly, eventually you fall on the orbit in (a).
c) Show that this is true for all positive integers.
(Hint: This is an open problem; the affirmative answer is called the Collatz conjecture.)

Exercise \(\PageIndex{13}\)

It is known that \(2^{11213}-1\) is prime. How many decimal digits does this number have? (Hint: \(\log_{10} 2 \approx 0.301029996\).)

Exercise \(\PageIndex{14}\)

This exercise prepares for Mersenne and Fermat primes, see Definition 5.11.

1. Use \(\sum_{i=0}^{b-1} 2^{ia} = \frac{2^{ab}-1}{2^{a}-1}\) to show that if \(2^{p}-1\) is prime, then \(p\) must be prime.
2. Use \(\sum_{i=0}^{b-1} (-2)^{ia} = \frac{(-2)^{ab}-1}{(-2)^{a}-1}\) to show that if \(2^{p}+1\) is prime, then \(p\) has no odd factor.

Exercise \(\PageIndex{15}\)

In the following, we assume that \(e-1 = \sum_{i=1}^{\infty} \frac{1}{i!} = \frac{p}{q}\) is rational, and show that this leads to a contradiction.

1. Show that the above assumption implies that \[\sum_{i=1}^{q} \frac{q!}{i!}+\frac{q!}{q+i!} = p(q-1)! \nonumber\] (Hint: multiply both sides of by \(q!\).)
2. Show that \(\sum_{i=1}^{q} \frac{q!}{i!}+\frac{q!}{q+i!} < \frac{1}{q^2}\). (Hint: write out a few terms of the sum on the left.)
3. Show that the sums in (b) cannot have an integer value.
4. Show that the other two terms in (a) have an integer value.
5. Conclude there is a contradiction unless the assumption that e is rational is false.

Exercise \(\PageIndex{16}\)

Show that Liouville’s theorem (Theorem 1.14) also holds for rational for rational numbers \(\rho = \frac{r}{s}\) as long as \(\frac{p}{q} \ne \frac{r}{s}\).

Exercise \(\PageIndex{17}\)

1. Show that for all positive integers \(p\) and \(n\), we have \(p(n+1)n! \le (n+p)!\).
2. Use (a) to show that \[\sum_{k = n+1}^{\infty} 10^{-k!} \le \sum_{k = n+1}^{\infty} 10^{-p(n+1)n!} (1-10^{-p(n+1)n!})^{-1} \nonumber\]
3. Show that b) implies equation (1.1).

Exercise \(\PageIndex{18}\)

Show that the inequality of Roth’s theorem does not hold for all numbers. (Hint: Let \(\rho\) be a Liouville number.)

Definition 1.25

Let \(A\) be a set. Its power set \(P(A)\) is the set whose elements are the subsets of \(A\). This always includes the empty set denoted by \(\emptyset\).

In the next two exercises, the aim is to show something that is obvious for finite sets, namely:

Theorem 1.26

The cardinality of a power set is always (strictly) greater than that of the set itself.

Exercise \(\PageIndex{19}\)

a) Given a set \(A\), show that there is an injection \(f : A \rightarrow P(A)\). (Hint: for every element \(a \in A\) there is a set \(\{a\}\).)

b) Conclude that \(|A| \le |P(A)|\). (Hint: see Definition 1.23.)

Exercise \(\PageIndex{20}\)

Let \(A\) be an arbitrary set. Assume that that there is a surjection \(S : A \rightarrow P(A)\) and define

\[R = \{a \in A|a \notin S(a)\} \nonumber\]

1. Show that there is a \(q \in A\) such that \(S(q) = R\).
2. Show that if \(q \in R\), then \(q \notin R\). (Hint: equation 1.2.)
3. Show that if \(q \notin R\), then \(q \in R\). (Hint: equation 1.2.)
4. Use (b) and (c) and exercise 1.19, to establish that \(|A| < |P(A)|\). (Hint: see Definition 1.23.)

In the next two exercises we show that the cardinality of \(\mathbb{R}\) equals that of \(P(\mathbb{N})\). This implies that that \(|\mathbb{R}| > |\mathbb{N}|\), which also follows from Theorem 1.20.

Exercise \(\PageIndex{21}\)

Let \(T\) be the set of sequences defined in the proof of Theorem 1.20. To a sequence \(t \in T\), associate a set \(S(t)\) in \(P(\mathbb{N})\) as follows:

\[\begin{array}{ccc} {i \in S \mbox{ if } t(i) = 2}&{and}&{i \notin S \mbox{ if } t(i) = 0} \end{array} \nonumber\]

1. Show that there is a bijection \(S : T \rightarrow P(\mathbb{N})\).
2. Use the bijection \(f\) in the proof of Theorem 1.20 to show there is a bijection \(K \rightarrow P(\mathbb{N})\).
3. Show that (a) and (b) imply that \(|P(\mathbb{N})| = |K| = |T|\). (Hint: see Definition 1.23.)
4. Find an injection \(K \rightarrow \mathbb{R}\) and conclude that \(|P(\mathbb{N})| \le |\mathbb{R}|\).

Exercise \(\PageIndex{22}\)

1. Show that there is a bijection \(\mathbb{R} \rightarrow (0, 1)\).
2. Show that there is an injection \((0, 1) \rightarrow T\). (Hint: use usual binary (base 2) expansion of reals.)
3. Use (a), (b), and exercise 1.21 (a), to show that \(|\mathbb{R}| \le |P(\mathbb{N})|\).
4. Use (c) and exercise 1.21 (d) to show that \(|\mathbb{R}| = |P(\mathbb{N})|\).

Exercise \(\PageIndex{23}\)

1. Show that having the same cardinality (see Definition 1.23) is an equivalence relation on sets.
2. Conclude that “cardinality” is an “equivalence class of sets”.

Exercise \(\PageIndex{24}\)

1. Fix some \(n > 0\). Show that having the same remainder modulo \(n\) is an equivalence relation on \(\mathbb{Z}\). (Hint: for example, \(-8, 4\), and 16 have the remainder modulo 12.)
2. Show that addition respects this equivalence relation. (Hint: If \(a+b = c, a \sim a′\), and \(b \sim b′\), then \(a′+b′ =c′\) with \(c \sim c′\).)
3. The same question for multiplication.