IMO-1959

1. Prove that the fraction \(\frac{21n+4}{14n+3}\) is irreducible for every natural number \(n\).
• To show that a fraction is irreducible, we need to prove that the numerator and denominator are relatively prime. Note that we have \(3 (14n+3) - 2 (21n+4) = 1\), \(\forall n \in \mathbb{N}\). Let \(d\) be the g.c.d of \(21n+4\) and \(14n+3\). Hence, \(d | \left( 3 (14n+3) - 2 (21n+4) = 1 \right) \). Hence, \(d | 1 \implies d = 1\). Hence, \(21n+4\) and \(14n+3\) are relatively prime. Hence, the fraction \(\frac{21n+4}{14n+3}\) is irreducible for every natural number \(n\).
2. For what real values of \(x\) is \[\sqrt{\left( x + \sqrt{2x-1} \right)} + \sqrt{\left( x - \sqrt{2x-1} \right)} = A,\] given (a) \(A = \sqrt{2} \), (b) \(A = 1\), (c) \(A = 2\), where only non-negative real numbers are admitted for square roots?
• Only non-negative real numbers are admitted for square roots, we need \(2x-1 \geq 0\) and \(x \geq \pm \sqrt{2x-1}\). The two conditions yield us \(x \geq \frac12\). Squaring both sides, we get, \[\left( x + \sqrt{2x-1} \right) + \left( x - \sqrt{2x-1} \right) + 2 \sqrt{\left( x + \sqrt{2x-1} \right)\left( x - \sqrt{2x-1} \right)} =A^2\] \[2x + 2 \sqrt{x^2 -2x + 1} = A^2\] \[2x + 2 \left \lvert x - 1 \right \rvert = A^2 \]
• If \(x \geq 1\), we get \[2x + 2x - 2 = A^2 \implies 4x = A^2 + 2 \implies x = \frac{A^2 + 2}{4}\] Hence, if \(A \geq \sqrt{2}\), we have \(x = \frac{A^2 + 2}{4}\).
• If \(\frac12 \leq x \leq 1\), we get \(2x + 2 - 2x = A^2 \implies 2 = A^2\), \(\forall x \in \left[\frac12,1\right]\).
• So the solution can be written as follows: \(x = \left \{ \begin{array}{lr} \frac{A^2+2}{4} & \text{If } A \gt \sqrt{2}\\ \text{Any value }\in \left[\frac12,1\right] & \text{If } A = \sqrt{2} \\ \text{No solution } & \text{If }A \lt \sqrt{2} \end{array} \right. \)
• For the current problem, we get \(x = \left \{ \begin{array}{lr} \frac{3}{2} & \text{If } A = 2 \\ \text{Any value }\in \left[\frac12,1\right] & \text{If } A = \sqrt{2} \\ \text{No solution } & \text{If }A = 1 \end{array} \right. \)
3. Let \(a,b,c\) be real numbers. Consider the quadratic equation in \(\cos(x)\) : \[ a \cos^2(x) + b \cos(x) + c = 0. \] Using the numbers \(a,b,c \) form a quadratic equation in \(\cos(2x)\), whose roots are the same as those of the original equation. Compare the equations in \(\cos(x)\) and \(\cos(2x)\) for \(a=4\), \(b=2\) and \(c=-1\).
• We have \(\cos^2(x) = \frac{1 + \cos(2x)}{2}\). Hence, the equation becomes \[\displaystyle a \left( \frac{1 + \cos(2x)}{2} \right) + b \sqrt{\frac{1 + \cos(2x)}{2}} + c = 0\] Rearranging and squaring both sides, we get \[\left( a \left( \frac{1 + \cos(2x)}{2} \right) + c \right)^2 = b^2 \left( \frac{1 + \cos(2x)}{2} \right) \] \[ a^2 + a^2 \cos^2(2x) + 4c^2 + 2a^2 \cos(2x) + 4ac + 4ac \cos(2x) = 2b^2 + 2b^2 \cos(2x)\] \[a^2 \cos^2(2x) + (2a^2 + 4ac -2 b^2) \cos(2x) + (a^2 + 4c^2 + 4ac - 2b^2) = 0\] Plugging in \(a = 4, b=2\) and \(c=-1\), we get the equation in terms of \(\cos(x)\) as \[4 \cos^2(x) + 2 \cos(x) - 1 = 0\] and the equation in terms of \(\cos(2x)\) as \[16 \cos^2(2x) + 8 \cos(2x) - 4 = 0.\] Hence, \(\cos(x)\) and \(\cos(2x)\) satisfy the same quadratic equation.

Algorithms - Exercises from Chapter 0

1. In each of the following situations, indicate whether \(f = \mathcal{O}(g)\) (or) \(f = \Omega(g)\) or both (in which case \(f = \Theta(g)\)).
• \(n-100 = \Theta(n-200)\)
• \(n^{1/2} = \mathcal{O}(n^{2/3})\)
• \(100n + \log n = \mathcal{O}(n + (\log n)^2)\)
• \(n \log n = \Theta (10n \log 10n)\)
• \(\log 2n = \Theta (\log 3n)\)
• \(10 \log n = \Theta (\log \left( n^2 \right))\)
• \(n^{1.01} = \Omega (n \log^2 n)\)
• \(n^2 / \log n = \mathcal{O}(n (\log n)^2)\)
• \(n^{0.1} = \mathcal{O}(\left( \log n \right)^{10})\)
• \((\log n)^{\log n} = \Omega(n / \log n\))
• \(\sqrt{n} = \Omega ((\log n)^3)\)
• \(n^{1/2} = \mathcal{O}(5^{\log_2n})\)
• \(n2^n = \mathcal{O}(3^n)\)
• \(2^n = \Theta (2^{n+1})\)
• \(n! = \Omega (2^n)\)
• \(\left(\log n \right)^{\log n} = 2^{\left(\log_2 n \right)^2}\)
• \(\sum_{i=1}^{n} i^k = \Theta (n^{k+1})\)
2. Show that, if \(c\) is a positive real number, then \(g(n) = 1 + c + c^2 + \cdots + c^n\) is:
• \(\Theta(1) \) if \(c \lt 1\)
• \(\Theta(n) \) if \(c = 1\)
• \(\Theta(c^n) \) if \(c \gt 1\)
• Solution: We have that \(g(n) = \frac{c^{n+1}-1}{c-1}\) whenever \(c \neq 1\). Note that \(g(n)\) is a monotonously increasing function for all positive real \(c\) i.e. we have \(g(n+1) \gt g(n)\).
• If \(c \lt 1\), we have \(1 \leq g(n) \lt \frac1{1-c}\), for all \(n \in \mathbb{Z}^+\). Hence, we get \(g(n) = \Theta(1)\).
• If \(c = 1\), we have \(g(n) = n+1\). Hence, we have that \(g(n) = \Theta(n)\).
• Since \(c \in \mathbb{R}^+\), we have \(g(n) \gt c^n, \forall n \in \mathbb{Z}^+\). For \(c \gt 1\), choose \(k = \frac{c}{c-1}\). We have \(1 + c + c^2 + \cdots + c^n =\frac{c^{n+1}-1}{c-1} \lt \frac{c^{n+1}}{c-1} = \frac{c}{c-1} c^n = k c^n\). Hence, we have for any \(n\), \[c^n \lt 1 + c + c^2 + \cdots + c^n \lt k c^n.\] Hence, we get \(g(n) = \Theta(c^n)\).
3. The Fibonacci numbers are defined by the rule \[F_0 = 0, F_1 = 1, F_{n} = F_{n-1} + F_{n-2}, n \geq 2.\] In this problem, we will confirm that this sequence grows exponentially fast and obtain some bounds on its growth.
• Use induction to prove that \(F_n \geq 2^{0.5n}\) for \(n \geq 6\).
• We have \(F_6 = 8 = 2^{0.5 \times 6}\) and \(F_7 = 13 \gt 12 \gt 8 \times 1.5 \gt 8 \times \sqrt{2} = 2^{3.5}\). Assume that for all \(k\) such that \(6 \leq k \leq m\), we have \(F_k \geq 2^{0.5k}\). We have \(F_{m+1} = F_{m} + F_{m-1} \gt 2^{0.5 m} + 2 ^{0.5 (m-1)} = 2 ^{0.5 m} \left(1 + \frac1{\sqrt{2}} \right) \gt 2^{0.5 m} \sqrt{2} = 2^{0.5 (m+1)}.\) We have checked the base cases for \(k=6\) and \(k=7\) and hence by induction we have \(F_n \geq 2^{0.5n}\). Hence proved.
• Find a constant \(c \lt 1\) such that \(F_n \leq 2^{cn}\) for all \(n \geq 0\). Show that the answer is correct.
• We need \(2^{c(n+1)} \geq 2^{cn} + 2^{c(n-1)}\) i.e. we need \(2^c \geq 1 + \frac1{2^c}\). Setting \(2^c = x\), we need \(x\) such that \(x \geq 1 + \frac1x\) i.e. we need \(x\) such that \(x^2 \geq x + 1\). Since we have \(x = 2^c\) and \(0 \leq c \lt 1\), we need \(x\) such that \(1 \leq x \lt 2\). Setting \(x^2 - x - 1 = 0\), we get \(x = \frac{1 \pm \sqrt{5}}{2}\). Since \(1 \leq x \lt 2\), we get \(x = \frac{1 + \sqrt{5}}{2}\). Hence, set \(c = \log_2 \left(\frac{1 + \sqrt{5}}{2}\right)\). We shall now check that setting \(c = \log_2 \left(\frac{1 + \sqrt{5}}{2}\right)\), we have \(F_n \leq 2^{cn}\). Clearly, we have \(F_0 = 0 \lt 1 = 2^{c \times 0}\). Similarly, we have \(F_1 = 1 \lt \frac{1 + \sqrt{5}}{2} = 2^{\log_2 \left(\frac{1 + \sqrt{5}}{2}\right)}\). Assume that we have \(F_k \leq 2^{ck}\) for all \(k \leq m\). Hence, we get \(F_{m+1} = F_m + F_{m-1} \leq 2^{cm} + 2^{c(m-1)} = 2^{cm} \left(1 + \frac1{2^c} \right) = 2^{cm + c} = 2^{c(m+1)}\). Hence, \(c = \log_2 \left(\frac{1+\sqrt{5}}{2} \right)\) does the job.
• What is the largest \(c\) you can find for which \(F_n = \Omega (2^{cn})\)?
• By a similar argument as above, we get that \(c = \log_2 \left(\frac{1+\sqrt{5}}{2} \right)\) does the job.
4. Is there a faster way to compute the \(n^{th}\) Fibonacci number? One idea involves \(matrices\). We start by writing the equations \(F_1 = F_1\) and \(F_2 = F_0 + F_1\) in matrix notation: \[ \begin{pmatrix}F_1 \\ F_2 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} \begin{pmatrix}F_0 \\ F_1 \end{pmatrix}\] Similarly, \[\begin{pmatrix}F_2 \\ F_3 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} \begin{pmatrix}F_1 \\ F_2 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^2 \begin{pmatrix}F_0 \\ F_1 \end{pmatrix}\] and in general, we have \[\begin{pmatrix} F_n \\ F_{n+1} \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^n \begin{pmatrix}F_0 \\ F_1 \end{pmatrix}\] So, in order to compute \(F_n\), it suffices to raise this \(2 \times 2\) matrix, call it \(X\), to the \(n^{th}\) power.
• Show that two \(2 \times 2\) matrices can be multiplied using \(4\) additions and \(8\) multiplications.
• \[\begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} e & f \\ g & h \end{pmatrix} = \begin{pmatrix} a \times e + b \times g & a \times f + b \times h \\ c \times e + d \times g & c \times f + d \times h \end{pmatrix}\] Hence, it is clear that we need \(4\) additions and \(8\) multiplications.

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\).