Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani

This post contains the solution to the exercises of the book by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani named "Algorithms". This post is a work in progress.

1. Exercises in Chapter 0
2. Exercises in Chapter 1

Elementary Number Theory - 1 Problems

1. Suppose that \(a,b,c \in \mathbb{N}\). Prove each of the following:
• If \(a|b\) and \(b|c\), then \(a|c\).
• Since \(a|b\) and \(b|c\), we have \(b= ak_1\) and \(c = b k_2\) where \(k_1,k_2 \in \mathbb{Z}\). Hence, we get \(c = b k_2 = a k_1 k_2 = a (k_1 k_2)\). Since \(k_1,k_2 \in \mathbb{Z}\), we get \(k_1 k_2 \in \mathbb{Z}\). Hence, we get \(a | c\).
• If \(a|b\) and \(a|c\), then \(a| (bx+cy)\) for every \(x,y \in \mathbb{Z}\).
• Since \(a|b\) and \(a|c\), we have \(b = a k_1\) and \(c = a k_2\) where \(k_1,k_2 \in \mathbb{Z}\). Hence, \(bx + cy = a k _1 x + a k_2 y = a \left(k_1 x + k_2 y \right)\). Note that since \(k_1,k_2,x,y \in \mathbb{Z}\), we have \(k_1 x + k_2 y \in \mathbb{Z}\). Hence, we get \(a | \left( bx + cy \right)\).
2. Prove that if \(n \in \mathbb{N}\) is composite, then it has a prime factor not exceeding \(\sqrt{n}\).
• Let \(n = p_1 p_2 \ldots p_r\) where \(p_i\)'s are prime not necessarily distinct. Further we are given that \(n\) is composite. Hence, we have \(r \geq 2\). Now assume the contrary that all the prime factors of \(n\) exceed \(\sqrt{n}\) i.e. \(p_k > \sqrt{n}\), \(\forall k \in \{1,2,\ldots,r \}\). Then \(n = p_1 p_2 \ldots p_r > \left(\sqrt{n} \right)^r = n^{r/2}\). Hence, we have \(n > n^{r/2}\). This implies \(r < 2\). This contradicts the fact that \(r \geq 2\). Hence there is at-least one prime factor not exceeding \(\sqrt{n}\).
3. Prove that \(n^4 + 4\) is composite for every natural number \(n > 1\).
• \(n^4 + 4 = n^4 + 4n^2 + 4 - 4n^2 = \left(n^2+2 \right)^2 - \left( 2n \right)^2 = \left( n^2+ 2 + 2n \right) \left( n^2 + 2 - 2n\right)\). Note that \(n^2+2 + 2n > n^2 + 2 -2n\), \(\forall n \in \mathbb{N}\). For \(n > 1\), we have \(n^2 + 2 -2n = (n-1)^2 + 1 > 1\). Hence, \(n^4 +4 = \left( n^2+ 2 + 2n \right) \left( n^2 + 2 - 2n\right)\) where \(\left( n^2+ 2 + 2n \right) \in \mathbb{Z}\) and \(\left( n^2 + 2 - 2n\right) \in \mathbb{Z}\). Further for \(n > 1\), we have \(\left( n^2+ 2 + 2n \right) > \left( n^2+ 2 - 2n \right) > 1\). Hence, \(n^4 +4\) is a product of two natural numbers greater than \(1\). Hence, \(n^4+4\) is composite for every natural number \(n > 1\).

Elementary Number Theory - 1.3 Definitions and Propositions

Theorem: (Euclid)
There are infinitely many primes.


Proof:
This is a classic proof by contradiction. Assume that there are only finitely many primes, say \(n\) of them and denote them by \(\mathbb{P} = \{p_1,p_2,\ldots,p_n\}\). Consider the number \(m = p_1p_2 \ldots p_n +1\). If \(m\) is a prime, we have \(m \neq p_l\) for any \(l \in \{1,2,\ldots,n\}\). Hence, we have constructed a new prime not in \(\mathbb{P}\). This means either \(m\) is not a prime (or) there are infinitely many primes. Hence, if \(m\) is a prime, we have proved that there are infinitely many primes. If \(m\) is not a prime, then since \(m\) is also not an irreducible, and since we have assumed that only finitely many primes exist, we have that \(p_i | m\) for some \(p_i\). But we have \(m - p_1p_2 \ldots p_n = 1\). This means the \(p_i | 1\). CONTRADICTION. Hence, there are infinitely many primes.

Definition:
The greatest integer part of a real number \(\alpha\), denoted by \(\lfloor \alpha \rfloor\), is the greatest integer less than or equal to \(\alpha\) i.e. the unique integer \(m \in \mathbb{Z}\) such that \(m \leq \alpha \lt m+1\).


Proposition:
Suppose \(\alpha,\beta \in \mathbb{R}\).

1. We have \(\alpha-1 \lt \lfloor \alpha \rfloor \leq \alpha\) and \(0 \leq \alpha - \lfloor \alpha \rfloor \lt 1\).
• By definition, we have that \(\lfloor \alpha \rfloor \in \mathbb{Z}\) such that \(\lfloor \alpha \rfloor \leq \alpha \lt \lfloor \alpha \rfloor + 1\). Rearranging the inequalities, we get \(\alpha - 1 \lt \lfloor \alpha \rfloor \leq \alpha\). Again by rearranging, we get \(0 \leq \alpha - \lfloor \alpha \rfloor \lt 1\).
2. If \(\alpha \geq 0\), then \(\lfloor \alpha \rfloor\) counts the number of positive integers not exceeding \(\alpha\). In other words, \[\lfloor \alpha \rfloor = \sum_{1 \leq n \leq \alpha} 1.\]
• \(\sum_{1 \leq n \leq \alpha}\) 1 = \(\sum_{1 \leq n \leq \lfloor \alpha \rfloor} 1 + \sum_{\lfloor \alpha \rfloor \lt n \leq \alpha} 1\). Since we have \(0 \leq \alpha - \lfloor \alpha \rfloor \lt 1\), the contribution of the second term is zero as there is no integer \(n\) such that \(\lfloor \alpha \rfloor \lt n \leq \alpha\). The first term is nothing but \(\lfloor \alpha \rfloor\).
3. For every \(n \in \mathbb{Z}\), we have \(\lfloor \alpha + n \rfloor = \lfloor \alpha \rfloor + n\).
• Let \(\lfloor \alpha \rfloor = m \in \mathbb{Z}\). We have that \(m \leq \alpha \lt m+1\). Hence, we have \(m + n \leq \alpha + n \lt (m+n) + 1\). Hence, we get \(\lfloor \alpha +n \rfloor = m + n = \lfloor \alpha \rfloor + n\).
4. We have \(\lfloor \alpha \rfloor + \lfloor \beta \rfloor \leq \lfloor \alpha + \beta \rfloor \leq \lfloor \alpha \rfloor + \lfloor \beta + 1\).
• Let \(\lfloor \alpha \rfloor = m\) and \(\lfloor \beta \rfloor = n\). This means \(m \leq \alpha \lt m + 1\) and \(n \leq \beta \lt n + 1\). Adding the two, we get \(m + n \leq \alpha + \beta + m + n + 2\). Hence, we get \(\lfloor \alpha \rfloor + \lfloor \beta \rfloor \leq \lfloor \alpha + \beta \rfloor \leq \lfloor \alpha \rfloor + \lfloor \beta + 1\).
5. If \(\alpha \in \mathbb{Z}\), then \(\lfloor \alpha \rfloor + \lfloor -\alpha \rfloor = 0\). If \(\alpha \not \in \mathbb{Z}\), then \(\lfloor \alpha \rfloor + \lfloor -\alpha \rfloor = -1\).
• If \(\alpha \in \mathbb{Z}\), then \(-\alpha \in \mathbb{Z}\). Hence, we have \(\lfloor \alpha \rfloor = \alpha\) and \(\lfloor -\alpha \rfloor = - \alpha\). Hence, \(\lfloor \alpha \rfloor + \lfloor -\alpha \rfloor = \alpha + (- \alpha) = 0\). If \(\alpha \notin \mathbb{Z}\), then let \(m = \lfloor \alpha \rfloor\). Since \(\alpha \notin \mathbb{Z}\), we get \(m \lt \alpha \lt \alpha + 1\). Multiplying by negative one, we get \(-m-1 \lt -\alpha \lt -m \). This means \(\lfloor \alpha \rfloor = - m - 1\). Hence, we get \(\lfloor \alpha \rfloor + \lfloor -\alpha \rfloor = m + (-m-1) = -1\).
6. The number \(- \lfloor -\alpha \rfloor\) is the smallest integer not less than \(\alpha\).
• Let \(m = \lfloor \alpha \rfloor\). If \(\alpha \in \mathbb{Z}\), then \(m = \alpha\). We get \(-\alpha = -m \in \mathbb{Z}\). Hence, \(- \lfloor -\alpha \rfloor = m\) which is nothing but the smallest integer not less than \(\alpha\). If \(\alpha \notin \mathbb{Z}\), then \(m \lt \alpha \lt m + 1\). Hence, \(-m - 1 \lt -\alpha \lt -m \). Hence, we get \(\lfloor -\alpha \rfloor = - m - 1\). Hence, we get \(- \lfloor -\alpha \rfloor = m + 1\) which is nothing but the smallest integer not less than \(\alpha\).
7. If \(n \in \mathbb{Z}^+\), then \(\lfloor \lfloor \alpha \rfloor / n \rfloor = \lfloor \alpha/n \rfloor\).
• If \(\alpha \in \mathbb{Z}\), then it follows trivially since \(\lfloor \alpha \rfloor = \alpha\). If \(\alpha \notin \mathbb{Z}\), let \(m = \lfloor \alpha \rfloor\). We then have \(m = qn + r\) where \(r \in \{0,1,2,\ldots,n-1\}\). Hence, \(\alpha = qn + r + \{\alpha\}\) where \(\{\alpha\} \in [0,1)\). Note that \(r + \{\alpha\} \in (0,n)\). We then get \(\lfloor \lfloor \alpha \rfloor / n \rfloor = \lfloor \frac{qn+r}{n} \rfloor = q\). We also get \(\lfloor \alpha/n \rfloor = \lfloor (qn + r + \{\alpha\})/n \rfloor\) = q. Hence, we get the desired result.
8. The number \(\lfloor \alpha + \frac12 \rfloor\) is one of the two nearest integers to \(\alpha\). Furthermore, if these two integers differ from \(\alpha\) by the same value, then \(\lfloor \alpha + \frac12 \rfloor\) is the larger of these two integers.
• Follows immediately from the definition.
9. If \(\alpha \gt 0\) and \(n \in \mathbb{N}\), then \(\lfloor \frac{\alpha}{n} \rfloor\) is the number of positive integers not exceeding \(\alpha\) and which are multiples of \(n\).
• Follows from the second part of this problem.

Theorem:

Suppose that \(n \in \mathbb{N}\) and \(p\) is a prime. Then the largest integer \(k\) such that \(p^k | n!\) is given by \[k = \sum_{j=1}^{\infty} \left \lfloor \frac{n}{p^j} \right \rfloor .\]
Proof:
Let \(r_m\) be the highest power of \(p\) dividing \(m\). Then we get \(k = \displaystyle \sum_{m=1}^{n} r_m\). We have \(r_m = \displaystyle \sum_{l=1}^{\infty} 1_{\{p^l | m\}} \). Hence, we get \(k = \displaystyle \sum_{m=1}^{n} \sum_{l=1}^{\infty} 1_{\{p^l | m\}} = \sum_{l=1}^{\infty} \sum_{m=1}^{n} 1_{\{p^l | m\}} = \sum_{l=1}^{\infty} \left \lfloor \frac{n}{p^l} \right \rfloor\). Hence, the largest integer \(k\) such that \(p^k | n!\) is given by \[k = \sum_{j=1}^{\infty} \left \lfloor \frac{n}{p^j} \right \rfloor .\]

Elementary Number Theory - 1.2 Definitions and Propositions

Definition: We say \(a \in \mathbb{Z}^+\) and \(a \gt 1\) is an irreducible if it has exactly two positive divisors, namely \(1\) and \(a\).
Definition: We say \(p \in \mathbb{Z}^+\) and \(p \gt 1\) is a prime if \(p | ab \implies p | a\) (or) \(p | b\).
Definition: We say \(a \in \mathbb{Z}^+\) and \(a \gt 1\) is composite if \(a\) is not a prime.


Proposition:
\(p\) is a prime if and only if \(p\) is irreducible.

Proof:

• We shall first prove that "If \(p\) is a prime, then \(p\) is an irreducible".
• If \(p\) is not irreducible, then \(p=ab\) for some \(a,b \in \mathbb{Z}^+\) where \(1 \lt a,b \lt p\). Clearly, \(p|p\) i.e. \(p|ab\) but \(p\not | a\) and \(p\not | b\) since \(1 \lt a,b \lt p\). Hence, \(p\) is not a prime.
• We shall now prove that "If \(p\) is an irreducible, then \(p\) is a prime".
• If \(p\) is an irreducible, we shall prove that if \(p\not | a\) and \(p\not | b\), then \(p\not ab\). Since \(p\) is an irreducible, the divisors of \(p\) are \(1\) and \(p\). Since \(p\not | a\) and \(p\not | b\), we have \((p,a) = 1\) and \((p,b) = 1\). Hence, we get \(ax_1 + py_1 = 1\) and \(bx_2 + py_2 = 1\). Multiplying out the two, we get \((ax_1 + py_1)(bx_2 + py_2) = 1\). i.e. we get \(abx_1x_2 + p(ax_1y_2 + bx_2y_1 + py_1 y_2) = 1\). Hence, we get that \((ab,p) = 1\). Hence, we have that \(p\not| ab\). Hence, \(p\) is a prime.

Proposition:

Suppose that \(a_1,a_2,\ldots,a_k \in \mathbb{Z}\), and \(p\) is a prime. If \(p | a_1a_2\ldots a_k\), then \(p|a_j\) for some \(j \in \{1,2,\ldots,k\}\).

Proof:

The proof follows immediately from the previous proposition and induction. Since \(p\) is a prime, it divides either \(a_1\) (or) \(a_2a_3 \ldots a_k\) and then get the rest by simple induction.

Proposition (Fundamental Theorem of Arithmetic):

Every natural number \(n > 1\) is representable as a product of primes, uniquely up to the order of factors.

Proof:
First, we shall prove by induction that any natural number is a product of prime(s). Let \(P(n)\) be the statement that \(n+2\) can be written as a product of prime(s). Let \(S = \{n \in \mathbb{N}: P(n) \text{ is true }\}\). Clearly, \(0 \in S\). This is so since \(2\) is a prime and can be written as \(2=2\). Assume that all natural numbers up-to \(k\) is in \(S\). Now consider \(k+1\). If \(k+3\) is irreducible, we proved that it is a prime and hence \(k+3 = k+3\). If \(k+3\) is not an irreducible, then we have \(k+3 = ab\), where \(1 \lt a,b \lt k+3\). Now by induction hypothesis, since \(1 \lt a,b \leq k+2\), we have \(a\), \(b\) to be product of primes i.e. \(a = p_1p_2 \ldots p_l\) and \(b = p_{l+1} p_{l+2} \ldots p_{l+m}\) where \(p_i\) are primes. Hence, \(k+3 = ab = p_1 p_2 \ldots p_l p_{l+1} p_{l+2} \ldots p_{l+m}\). Hence, \(k+3\) can also be expressed as a product of primes. Hence, \(k+1 \in S\). By principle of mathematical induction, we have that every natural number. Hence, every natural number is representable as a product of primes.
We still needs to prove uniqueness. Assume that the representation is not unique i.e. let \(n=p_1 p_2 \ldots p_l = q_1 q_2 \ldots q_k\). Consider \(p_1\). We have \(p_1 | n\). This means that \(p_1 | \prod_{j=1}^{k} q_j\) and from the definition of a prime we get \(p_1 | q_j\) for some \(j\). From the definition of a prime, we get that \(p_1 | q_j\). But from an earlier proved proposition since \(q_j\) is a prime, the only factors of \(q_j\) are \(1\) and \(q_j\) itself. This gives us \(p_1 = q_j\). Repeat this argument a finite number of times to conclude that \(l = k\) and get the desired result.

Proposition:
Every natural number \(n > 1\) is uniquely representable in the form \[n = p_1^{\alpha_1} p_2^{\alpha_2} \ldots p_k^{\alpha_k}\] where \(p_1 < p_2 < \cdots \lt p_k\) are primes and \(\alpha_k \in \mathbb{Z}^+\).

Proof:
Follows immediately from the above proposition and grouping together equal primes. The above is the canonical prime decomposition of a natural number \(n\).

Convergence of sequence of rationals and irrationals

Note that both \(\mathbb{Q}\) and \(\mathbb{R} \backslash \mathbb{Q}\) are dense in \(\mathbb{R}\).

1. Convergence of sequence of distinct rationals to a
• Rational number:
• Want sequence of distinct rationals say \(\{a_n\}_{n=1}^{\infty}\) to another rational number say \(a\). Choose \(a_k = a + \frac1k\) where \(k \in \mathbb{Z}^+\). Clearly, \(a_k\)'s are rationals and converge to the rational number \(a\).
• Irrational number:
• Want sequence of distinct rationals say \(\{a_n\}_{n=1}^{\infty}\) to an irrational number say \(a\). Choose \(a_k = \frac{\lfloor 10^k a \rfloor}{10^k}\) where \(k \in \mathbb{Z}^+\). Clearly, \(a_k\)'s are rationals and converge to the irrational number \(a\).
2. Convergence of sequence of distinct irrationals to a
• Rational number:
• Want sequence of distinct irrationals say \(\{a_n\}_{n=1}^{\infty}\) to a rational number say \(a\). Choose \(a_k = a + \frac{x}k\) where \(k \in \mathbb{Z}^+\) and \(x\) is any irrational number. Clearly, \(a_k\)'s are irrationals and converge to the rational number \(a\).
• Irrational number:
• Want sequence of distinct irrationals say \(\{a_n\}_{n=1}^{\infty}\) to another irrational number say \(a\). Choose \(a_k = a + \frac1k\) where \(k \in \mathbb{Z}^+\). Clearly, \(a_k\)'s are irrationals and converge to the irrational number \(a\).