Sean Xie

Some problems I found interesting:

• Rounding a matrix without changing its row or column sums

  CO 380

  Question. A rounding of a real matrix \(A\) replaces each entry \(x\) with either \(\lfloor x\rfloor\) or \(\lceil x\rceil\). Prove that if every row sum and column sum of \(A\) is an integer, then \(A\) has a rounding in which all row sums and column sums remain unchanged.

  Solution.

  Let \(A=(a_{ij})\) be an \(m\times n\) real matrix and \( a_{ij}=\lfloor a_{ij}\rfloor + b_{ij} \text{ and } 0\le b_{ij}<1. \) Let \(B=(b_{ij})\). Since the row and column sums of \(A\) are integers, and the row and column sums of \((\lfloor a_{ij}\rfloor)\) are also integers, the row and column sums of \(B\) are integers. So it suffices to prove the result for matrices with entries in \([0,1)\).

  We induct on the number of entries lying strictly between \(0\) and \(1\). Entries equal to \(0\) or \(1\) are already rounded and will not be changed.

  Suppose some entries lie in \((0,1)\). Construct a bipartite graph with row vertices \(r_i\) and column vertices \(c_j\), putting an edge \(r_ic_j\) exactly when \(b_{ij}\in(0,1)\).

  Every non isolated vertex has degree at least \(2\). Indeed, if a row had exactly one entry in \((0,1)\), then since all other entries in that row are \(0\) or \(1\), the row sum would not be an integer. The same argument applies to columns, so this graph contains a cycle.

  Let the cycle be

  \[ r_{i_1}c_{j_1}r_{i_2}c_{j_2}\cdots r_{i_k}c_{j_k}r_{i_1}, \]

  where indices are taken mod \(k\). Consider the entries \( b_{i_tj_t} \text{ and } b_{i_{t+1}j_t} \) corresponding to consecutive edges of the cycle. Add \(\varepsilon\) to each \(b_{i_tj_t}\), and subtract \(\varepsilon\) from each \(b_{i_{t+1}j_t}\). Each row and each column in the cycle has one entry increased and one entry decreased, so all row and column sums are preserved.

  Let

  \[ \varepsilon = \min\Bigl( \{1-b_{i_tj_t}:1\le t\le k\} \cup \{b_{i_{t+1}j_t}:1\le t\le k\} \Bigr). \]

  Then all entries remain in \([0,1]\), and at least one entry that was in \((0,1)\) becomes either \(0\) or \(1\). So the number of entries in \((0,1)\) decreases. By the inductive hypothesis, the new matrix has a rounding preserving all row and column sums. Since only entries originally in \((0,1)\) were changed, that same \(0/1\)-matrix is also a valid rounding of \(B\).

  Thus \(B\) has a \(0/1\)-rounding preserving all row and column sums. Adding back the integer matrix \((\lfloor a_{ij}\rfloor)\), we obtain a rounding of \(A\) preserving all row and column sums.

• Extracting an RSA secret from two accepting transcripts

  CO 487

  Question. Let \(N\) be an RSA modulus, let \(e\) be prime, and suppose \(de\equiv1\pmod{\varphi(N)}\). Choose \(x\in\mathbb Z_N^*\). The prover has public key \((N,e,X=x^e\bmod N)\) and secret key \((N,x)\).

  The prover samples \(y\) uniformly from \(\mathbb Z_N^*\) and sends \(Y=y^e\bmod N\). The verifier samples \(c\) uniformly from \(\{0,\ldots,e-1\}\). The prover responds with \(z=yx^c\bmod N\), and the verifier accepts when \(z^e\equiv YX^c\pmod N\).

  (a) Show that the protocol is complete. (b) Show special soundness: from two accepting transcripts with the same commitment and different challenges, recover the secret key.

  Hint. You may use the following theorem: given coprime integers \(\alpha,\beta\) and \(\Phi,\Omega\in\mathbb Z_n^*\) with \(\Phi^\alpha=\Omega^\beta\), an efficient algorithm computes \(x\in\mathbb Z_n^*\) such that \(x^\alpha=\Omega\).

  Solution (a).

  The prover samples \(y \in_R \mathbb{Z}_N^*\) and computes

  \[ Y = y^e \bmod N . \]

  After receiving \(c \in \{0,\dots,e-1\}\), the prover computes

  \[ z = y x^c \bmod N . \]

  The verifier checks whether

  \[ z^e \equiv Y X^c \bmod N . \]

  Compute the left-hand side:

  \[ z^e = (y x^c)^e \equiv y^e (x^c)^e = y^e x^{ce} \bmod N . \]

  Since \(X = x^e \bmod N\), we have

  \[ X^c = (x^e)^c = x^{ec} = x^{ce} \bmod N . \]

  Thus,

  \[ z^e \equiv y^e x^{ce} \equiv Y X^c \bmod N . \]

  Therefore the verifier's check always succeeds, and the protocol is complete.

  Solution (b).

  Suppose we are given two accepting transcripts with the same commitment \(Y\) but distinct challenges:

  \[ (Y,c,z)\quad\text{and}\quad (Y,c',z'),\qquad c\neq c', \]

  where \(c,c'\in\{0,\dots,e-1\}\) and all values lie in \(\mathbb{Z}_N^*\). The verifier's checks imply

  \[ z^e \equiv Y X^c \bmod N,\qquad (z')^e \equiv Y X^{c'} \bmod N. \]

  Eliminating \(Y\) by dividing the two congruences (division is valid since \(z,(z')\in\mathbb{Z}_N^*\)) gives

  \[ \left(\frac{z}{z'}\right)^e \equiv X^{\,c-c'} \bmod N. \]

  Set

  \[ \Phi \;=\; \frac{z}{z'}\ \text{mod }N,\qquad \Omega \;=\; X,\qquad \alpha=e,\qquad \beta=c-c'. \]

  Note \(\beta\) is nonzero modulo \(e\) because \(0\le c,c'\le e-1\) and \(c\neq c'\). Since \(e\) is prime we have \(\gcd(\alpha,\beta)=\gcd(e,c-c')=1\). The congruence above is \( \Phi^\alpha \equiv \Omega^\beta \bmod N. \) By the given theorem, there is an efficient algorithm that computes \(x\in\mathbb{Z}_N^*\) such that

  \[ x^\alpha \equiv \Omega \bmod N, \]

  i.e. \(x^e \equiv X \bmod N\). But the prover's secret \(x\) satisfies \(X\equiv x^e\bmod N\), so the algorithm recovers (one of) the e-th roots of \(X\) modulo \(N\). In particular, the prover's secret \(x\). Hence the protocol satisfies special soundness.

• Connecting singular values to eigenvalues

  CS 475

  Question.

  Let \(A\) be a full rank \(m \times n\) matrix (where \(m \geq n\)). Consider

  \[\begin{eqnarray*} H = \begin{bmatrix} 0 & A^T \\ A & 0 \end{bmatrix}. \end{eqnarray*}\]

  Determine an eigenvalue decomposition of \(H\), i.e., find \(Q\) such that \(HQ=Q\Lambda\), where \(\Lambda\) is a diagonal matrix. How are \(Q\) and \(\Lambda\) related to the singular vectors and singular values of \(A\)? Explain. (Hint: Consider

  \[ Q = \frac{1}{\sqrt{2}} \begin{bmatrix} V & V & 0 \\ \hat{U} & -\hat{U} & \sqrt{2} \hat{U}_{m-n} \end{bmatrix}, \]

  where an SVD of \(A\) is given by \(A = U \Sigma V^T\), and \(U = \begin{bmatrix} \hat{U} & \hat{U}_{m-n} \end{bmatrix}\).)

  Solution.

  Noting the hint, define the vectors

  \[ q_k^{\pm} = \frac{1}{\sqrt{2}} \begin{bmatrix} v_k \\ \pm \hat{u}_k \end{bmatrix}, \quad \text{for } k = 1, \dots, n, \]

  where \( v_k \) and \( \hat{u}_k \) are the \( k \)-th columns of \( V \) and \( \hat{U} \), respectively. Now, we verify that these are eigenvectors of \( H \). Specifically,

  \[ H q_k^{\pm} = \frac{1}{\sqrt{2}} \begin{bmatrix} A^T (\pm \hat{u}_k) \\ A v_k \end{bmatrix} = \frac{1}{\sqrt{2}} \begin{bmatrix} \pm \sigma_k v_k \\ \sigma_k \hat{u}_k \end{bmatrix} = \pm \sigma_k \cdot \frac{1}{\sqrt{2}} \begin{bmatrix} v_k \\ \pm \hat{u}_k \end{bmatrix} = \pm \sigma_k q_k^{\pm}. \]

  Thus, \( q_k^{+} \) and \( q_k^{-} \) are eigenvectors of \( H \) corresponding to the eigenvalues \( \sigma_k \) and \( -\sigma_k \), respectively.

  We now consider the remaining \( m - n \) eigenvectors of \( H \). Define

  \[ q_j^0 = \begin{bmatrix} 0 \\ \hat{u}_{j} \end{bmatrix}, \quad j = 1, \dots, m - n, \]

  where \( \hat{u}_j \) is a column of \( \hat{U}_{m-n} \). Since \( \hat{u}_j \in \operatorname{Null}(A^T) \), we have

  \[ H q_j^0 = \begin{bmatrix} A^T \hat{u}_j \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}, \]

  so \( q_j^0 \) is an eigenvector with eigenvalue \(0\).

  We now assemble all \( n + m \) eigenvectors into the matrix

  \[ Q = \frac{1}{\sqrt{2}} \begin{bmatrix} V & V & 0 \\ \hat{U} & -\hat{U} & \sqrt{2} \hat{U}_{m-n} \end{bmatrix}, \]

  which is orthogonal since its columns are mutually orthonormal. The corresponding diagonal matrix of eigenvalues is therefore

  \[ \Lambda = \operatorname{diag}(\sigma_1, \dots, \sigma_n, -\sigma_1, \dots, -\sigma_n, 0, \dots, 0), \]

  where the last \( m - n \) entries are zero. Then,

  \[ H = Q \Lambda Q^T \]

  is an eigenvalue decomposition of \( H \).

  This decomposition shows connection between the eigenvalues and eigenvectors of \( H \) and the SVD of \( A \). Specifically, the nonzero eigenvalues of \( H \) are \( \pm \sigma_i \), where \( \sigma_i \) are the singular values of \( A \), and the corresponding eigenvectors are constructed from the left and right singular vectors of \( A \).

• Classifying a surface through its fundamental forms and curvature

  PMATH 365

  Question. Let \(S\) be the smooth surface \(z=ax^2+by^2\), where \(a,b\in\mathbb R\). Show that every point on \(S\) is:

  (a) elliptic if and only if \(ab>0\), giving an elliptic paraboloid; (b) hyperbolic if and only if \(ab<0\), giving a saddle surface; (c) parabolic if and only if \(ab=0\) and at least one of \(a,b\) is nonzero, giving a parabolic cylinder; (d) planar if and only if \(a=b=0\), giving the \(xy\)-plane.

  Solution (a).

  Consider the homeomorphism \(\alpha:\mathbb R^2\to S\) via \((u,v)\mapsto(u,v,au^2+bv^2)\). To see that \(\alpha\) is indeed a chart of \(S\), consider the partial derivatives

  \[ \alpha_u=(1,0,2au),\alpha_v=(0,1,2bv). \]

  Since \(\alpha_u\times\alpha_v=(-2au,-2bv,1)\ne\vec0\) for all \((u,v)\in\R^2\), \(\alpha_u\) and \(\alpha_v\) are linearly independent and thus \(D\alpha(u,v)\) has full rank \(2\), which fulfills the definition of a 2-submanifold.

  The first fundamental form \(\mathcal F_I\) is given by

  \[ \mathcal F_I = \begin{bmatrix} \alpha_u\cdot\alpha_u & \alpha_u\cdot\alpha_v \\ \alpha_v\cdot\alpha_u & \alpha_v\cdot\alpha_v \\ \end{bmatrix} = \begin{bmatrix} 1+4a^2u^2 & 4abuv \\ 4abuv & 1+4b^2v^2 \\ \end{bmatrix} \]

  and we give extra attention to the positive value

  \[ d=\det\mathcal F_I=4a^2u^2+4b^2v^2+1. \]

  With reference to the standard unit normal \(N_\alpha\) given by

  \[ N_\alpha=\frac{\alpha_u\times\alpha_v}{\lVert\alpha_u\times\alpha_v\rVert}=\frac{(-2au,-2bv,1)}{\sqrt{4a^2u^2+4b^2v^2+1}}=\frac{(-2au,-2bv,1)}{\sqrt d} \]

  and the second partial derivatives

  \[ \alpha_{uu}=(0,0,2a),\alpha_{uv}=(0,0,0),\alpha_{vu}=(0,0,0),\alpha_{vv}=(0,0,2b), \]

  the second fundamental form \(\mathcal F_{II}\) is given by

  \[ \mathcal F_{II} = \begin{bmatrix} \alpha_{uu}\cdot N_\alpha & \alpha_{uv}\cdot N_\alpha \\ \alpha_{vu}\cdot N_\alpha & \alpha_{vv}\cdot N_\alpha \\ \end{bmatrix} = \begin{bmatrix} \frac{2a}{\sqrt{d}} & 0 \\ 0 & \frac{2b}{\sqrt{d}} \\ \end{bmatrix} \\ = \frac{2}{\sqrt{d}} \begin{bmatrix} a & 0 \\ 0 & b \\ \end{bmatrix}. \]

  Noting that \(\mathcal F_I\) is invertible, we compute the Weingarten matrix

  \[\begin{align*} \mathcal W &= \mathcal F^{-1}_I \mathcal F_{II} \\ &= \left(\frac{1}{\det\mathcal F_I}\adj \mathcal F_I\right) \mathcal F_{II} \\ &= \left(\frac{1}{d} \begin{bmatrix} 4b^2v^2+1 & -4abuv \\ -4abuv & 4a^2u^2+1 \end{bmatrix} \right) \frac{2}{\sqrt{d}} \begin{bmatrix} a & 0 \\ 0 & b \\ \end{bmatrix}\\ &=\frac{2}{d\sqrt d} \begin{bmatrix} a(4b^2v^2+1) & -b(4abuv) \\ -a(4abuv) & b(4a^2u^2+1) \end{bmatrix} \\ \mathcal W&=\frac{2}{d\sqrt d} \begin{bmatrix} 4ab^2v^2+a & -4ab^2uv \\ -4a^2buv & 4a^2bu^2+b \end{bmatrix}. \end{align*}\]

  The, the Gaussian curvature is given by

  \[\begin{align*} K&=\det \mathcal W \\ &=\det\left(\frac{2}{d\sqrt d} \begin{bmatrix} 4ab^2v^2+a & -4ab^2uv \\ -4a^2buv & 4a^2bu^2+b \end{bmatrix} \right) \\ &=\left(\frac{2}{d\sqrt d}\right)^2\det \begin{bmatrix} 4ab^2v^2+a & -4ab^2uv \\ -4a^2buv & 4a^2bu^2+b \end{bmatrix}\\ &=\frac{4}{d^3}((4ab^2v^2+a)(4a^2bu^2+b)-(4ab^2uv)(4a^2buv)) \\ &=\frac{4}{d^3}(ab+4a^3bu^2+4ab^3v^2+16a^3b^3u^2v^2-16a^3b^3u^2v^2) \\ &=\frac{4}{d^3}(ab+4a^3bu^2+4ab^3v^2) \\ &=\frac{4ab}{d^3}(1+4a^2u^2+4b^2v^2) \\ &=\frac{4ab}{d^3}d \\ K&=\frac{4ab}{d^2} \end{align*}\]

  Since \(d^2\) is positive for any point on \(S\), the sign of \(K\) for any point on \(S\) is determined by \(ab\). For \(S\) to be elliptic, we must have \(K>0\iff ab>0\).

  Solution (b).

  This is similar to the elliptic case in part (a). For \(S\) to be hyperbolic, we must have \(K<0\iff ab<0\).

  Solution (c).

  With \(d\) defined as in part (a), the mean curvature is given by

  \[\begin{align*} H&=\frac12\tr\mathcal W \\ &=\frac12\tr\left(\frac{2}{d\sqrt d} \begin{bmatrix} 4ab^2v^2+a & -4ab^2uv \\ -4a^2buv & 4a^2bu^2+b \end{bmatrix}\right) \\ &=\frac{1}{d\sqrt d}\tr \begin{bmatrix} 4ab^2v^2+a & -4ab^2uv \\ -4a^2buv & 4a^2bu^2+b \end{bmatrix}\\ &=\frac{a + b + 4ab^2v^2 + 4a^2bu^2}{d\sqrt d}\\ &H=\frac{a + b + 4ab(au^2 + bv^2)}{d\sqrt d}. \end{align*}\]

  For \(S\) to be parabolic, we must have have \(K=\frac{4ab}{d^2}=0\iff ab=0\). We also need \(H\ne0\). Since \(ab=0\), the mean curvature becomes

  \[ H=\frac{a + b}{d\sqrt d}, \]

  so we must have \(H\ne0\iff a+b\ne0\iff a\ne0\text{ or }b\ne0\).

  Solution (d).

  This is similar to the parabolic case in part (c). For \(S\) to be planar, we need \(K=H=0\). For \(K=0\), we must have \(ab=0\). Under this condition, to have \(H=0\), we must have \(a+b=0\iff a=b=0\text{ or }a=-b\text{ for nonzero }a,b\). The latter case is not possible since it would imply \(ab\ne0\).

• Why a group of order 56 cannot be simple

  PMATH 347

  Question. A group \(G\) is simple if its only normal subgroups are \(\{1\}\) and \(G\). Prove that there is no simple group of order \(56\).

  Solution.

  Note the prime factorization \(56=2^3\cdot 7\). Let \(G\) be a group of order 56. Let \(n_p\) denote the number of Sylow \(p\)-subgroups of \(G\). By the 3rd Sylow theorem, \(n_7\mid |G|\) and \(n_7=7k+1,k\in\mathbb N\cup \{0\}\). Also, we have by a remark given in class that \(n_7\mid 2^3=8\). Thus \(n_7=1\) or \(n_7=8\) (choosing \(k=0\) and \(k=1\), respectively). If \(n_7=1\), let the single Sylow \(7\)-subgroup be \(P_7\). We have by Corollary 6.6 (presented in class) that \(P_7\) is a normal subgroup of \(G\), so \(G\) is not simple. If \(n_7=8\), each of the Sylow \(7\)-groups will contain \(6\) elements of order \(7\) and \(1\) identity. Since two subgroups of order 7 intersect in either 1 or 7 elements, we note that the non-identity element are distinct, which make \(6\times8=48\) elements of order 7. This leaves \(56-48=8\) elements which is the size of only the Sylow \(2\)-subgroup, say \(P_2\). By Corollary 6.6 (presented in class), we have that \(P_2\triangleleft G\) so \(G\) is not simple.

• Connecting solid angles, dihedral angles, and Euler's formula

  PMATH 320

  Question (a). Let \(P\) be a spherical \(n\)-gon on the unit sphere with area \(A\) and interior angle sum \(S\). Assume it has no holes. Compute \(A-S\) in terms of \(n\). You may use Theorem 24, which gives \(A=S-\pi\) for a spherical triangle, and the fact that for \(n\geq4\), every spherical \(n\)-gon is obtained by attaching a triangle to an edge of an \((n-1)\)-gon.

  Solution (a).

  We prove the result by induction on \(n\).

  For \(n=3\), Theorem~24 gives \( A=S-\pi, \) so

  \[ A-S=-\pi=-(3-2)\pi. \]

  Now suppose the result holds for an \((n-1)\)-gon. By the given fact, an \(n\)-gon is obtained from an \((n-1)\)-gon by attaching a spherical triangle along one of its edges.

  Let the \((n-1)\)-gon have area \(A'\) and angle sum \(S'\), and let the attached triangle have area \(a\) and angle sum \(s\). Attaching the triangle adds its area and its three angles, so

  \[ A=A'+a \text{ and } S=S'+s. \]

  By Theorem 24, \( a=s-\pi. \) Therefore,

  \[ \begin{aligned} A-S &=(A'+a)-(S'+s)\\ &=(A'-S')+(a-s)\\ &=-(n-3)\pi-\pi\\ &=-(n-2)\pi. \end{aligned} \]

  So, \( \boxed{A-S=-(n-2)\pi}. \)

  Question (b).

  Given a vertex \(v\) of a polyhedron, define the solid angle \(\Omega_v\) of \(v\) as follows. Choose a positive real number \(r\) small enough so that the sphere \(\SS(v,r)\) centered at \(v\) with radius \(r\),

  \[ \SS(v,r) = \{w \in \RR^3: \dist(v,w) = r\}, \]

  only intersects the polyhedron at edges and faces that are adjacent to \(v\) (you may take it for granted that such a sphere exists). Let \(\sigma\) be the surface area of the part of \(\SS(v,r)\) that is in the interior of the polyhedron, and let \(\tau\) be the total surface area of \(\SS(v,r)\). Define \(\Omega_v = 4\pi \frac{\sigma}{\tau}\).

  Let \(M\) be the sum of all the solid angles of a regular polyhedron, and let \(D\) be the sum of all the dihedral angles of the edges. Prove that \(M - 2D = 2\pi(2 - F)\) where \(F\) is the number of faces of the regular polyhedron.

  You may take it for granted that in a regular polyhedron, all dihedral angles are equal and all solid angles are equal.

  Note: The solid angle is the 3-dimensional version of using radians to measure angle, can you see how?

  Solution (b).

  Let \(V,E,F\) be the numbers of vertices, edges, and faces of the regular polyhedron. Let \(q\) faces meet at each vertex, and let \(\delta\) be the common dihedral angle.

  Fix a vertex \(v\). The part of \(\mathbb{S}(v,r)\) lying inside the polyhedron is bounded by the \(q\) faces meeting at \(v\). After rescaling \(\mathbb{S}(v,r)\) to the unit sphere, this region becomes a spherical \(q\)-gon.

  Rescaling preserves the fraction of the sphere occupied by the region. Since the unit sphere has area \(4\pi\), the area of this spherical \(q\)-gon is \( 4\pi\frac{\sigma}{\tau}=\Omega_v. \)

  Each vertex of this spherical \(q\)-gon corresponds to an edge of the polyhedron incident to \(v\). Its interior angle is the angle between the two faces meeting along that edge, which is the dihedral angle \(\delta\). So the sum of the interior angles of the spherical \(q\)-gon is \(q\delta\).

  From the formula for a spherical \(q\)-gon,

  \[ A-S=-(q-2)\pi. \]

  Applying this to the spherical polygon at \(v\) gives

  \[ \Omega_v-q\delta=-(q-2)\pi. \]

  Because the polyhedron is regular, this equation is the same at every vertex. Summing over all \(V\) vertices gives

  \[ M-Vq\delta=-V(q-2)\pi. \]

  There are \(q\) edges incident to each vertex, while each edge has two endpoints. Counting vertex-edge incidences in two ways gives

  \[ Vq=2E. \]

  Also, since \(D\) is the sum of all the dihedral angles,

  \[ D=E\delta. \]

  As a result, \( Vq\delta=2E\delta=2D, \) and so \( M-2D=-V(q-2)\pi. \)

  Finally, using \(Vq=2E\),

  \[ V(q-2)=Vq-2V=2E-2V=2(E-V). \]

  Euler's formula gives

  \[ V-E+F=2, \]

  so

  \[ E-V=F-2. \]

  Thus,

  \[ \begin{aligned} M-2D &=-V(q-2)\pi\\ &=-2(E-V)\pi\\ &=-2(F-2)\pi\\ &=\boxed{2\pi(2-F)}. \end{aligned} \]

• An infinity of primes from pairwise coprime Fermat numbers

  MATH 135

  Question. For each nonnegative integer \(r\), define \(a_r=2^{2^r}+1\). (a) Prove that for every positive integer \(n\), \(a_n=2+\prod_{r=0}^{n-1}a_r\). (b) Use (a) to prove that \(a_i,a_j\) are coprime whenever \(0\leq i<j\). (c) Deduce that there are infinitely many primes.

  Here POMI denotes the principle of mathematical induction. GCD WR is the gcd remainder rule: \(\gcd(a,b)=\gcd(a,b-qa)\) for an integer \(q\).

  Solution.

  (a) We will prove by induction on \(n\).

  Define

  \[ P\left(n\right):a_{n}=2+\prod_{r=0}^{n-1}a_{r}. \]

  Base Case. We have \(P\left(1\right)\), which yields

  \[ a_{1}=2+a_{0}. \]

  Notice that \(a_{0}=2^{2^{0}}+1=3\) and \(a_{1}=2^{2^{1}}+1=5\). This gives us

  \[ a_{1}=2+3=5, \]

  which confirms that \(P\left(1\right)\) is true.

  Inductive Step. Let \(k\in{}\mathbb{N}\) be arbitrary and assume the inductive hypothesis \(P\left(k\right)\), that is

  \[ a_{k}=2+\prod_{r=0}^{k-1}a_{r}. \]

  We want to obtain \(P\left(k+1\right)\), which stands for

  \[ a_{k+1}=2+\prod_{r=0}^{k}a_{r}. \]

  Starting with the LHS, we have by the recursive definition that

  \[\begin{align*} a_{k+1}= & 2^{2^{k+1}}+1 \\ = & \left(2^{2^{k}}\right)^{2}+1 \\ a_{k+1}= & \left(a_{k}-1\right)^{2}+1. \end{align*}\]

  Then, by the inductive hypothesis,

  \[\begin{align*} a_{k+1}= & \left(a_{k}-1\right)\left(2+\prod_{r=0}^{k-1}a_{r}-1\right)+1 \\ a_{k+1}= & \left(a_{k}-1\right)\left(1+\prod_{r=0}^{k-1}a_{r}\right)+1. \end{align*}\]

  Expanding the product,

  \[\begin{align*} a_{k+1}= & \left(a_{k}+\left(a_{k}\prod_{r=0}^{k-1}a_{r}\right)-1-\prod_{r=0}^{k-1}a_{r}\right)+1 \\ a_{k+1}= & a_{k}+\left(a_{k}\prod_{r=0}^{k-1}a_{r}\right)-\prod_{r=0}^{k-1}a_{r}. \end{align*}\]

  Then, noticing that \(a_{k}\cdot{}\prod_{r=0}^{k-1}a_{r}=a_{0}\times{}a_{1}\times{}\cdots{}\times{}a_{k}=\prod_{r=0}^{k}a_{r}\) and that \(\prod_{r=0}^{k-1}a_{r}=a_{k}-2\), we have

  \[\begin{align*} a_{k+1}= & a_{k}+\left(\prod_{r=0}^{k}a_{r}\right)-\left(a_{k}-2\right) \\ = & a_{k}+\left(\prod_{r=0}^{k}a_{r}\right)-a_{k}+2 \\ a_{k+1}= & 2+\prod_{r=0}^{k}a_{r}, \end{align*}\]

  and so the result holds for \(n=k+1\) and thus for all \(n\in{}\mathbb{N}\) by the POMI. \(\square\)

  (b) If \(a_{i}\) and \(a_{j}\) are coprime, we must have \(gcd\left(a_{i},a_{j}\right)=1\).

  Notice that

  \[ a_{i} \mid \left(\prod_{r=0}^{j-1}a_{r}\right)\Longrightarrow{}a_{i}\mid{} \left(a_{j}-2\right)\Longrightarrow{}a_{j}-2=na_{i}\Longrightarrow{}a_{j}=a_{i}n+2, \]

  where \(n\in{}\mathbb{Z}\). Then, by GCD WR,

  \[\begin{align*} gcd\left(a_{i},a_{j}\right)=gcd\left(a_{j},a_{i}\right)= & gcd\left(a_{i},2\right). \end{align*}\]

  Similarly, notice that \(a_{i}=2^{2^{i}}+1=2\left(2^{2^{i}-1}\right)+1\) and so

  \[ gcd\left(a_{i},2\right)=gcd\left(2,1\right)=1, \]

  as required. \(\square\)

  (c) By Prime Factorization, every natural number \(n>1\) can be written as the product of primes. Since every term in the sequence \(\left\{a_{1},a_{2},a_{3},\ldots{}\right\}\) is coprime to every other term and thus do not share any divisors, we can conclude that an infinite amount of unique primes is needed to express every term in the infinite sequence. \(\square\)