3.6 Exercises

Exercise \(\PageIndex{1}\)

Which of the following equations have integer solutions?

1. \(1137 = 69x + 39y\).
2. \(1138 = 69x + 39y\).
3. \(-64 = 147x + 84y\).
4. \(-63 = 147x + 84y\).

Exercise \(\PageIndex{2}\)

Let \(l\) be the line in \(\mathbb{R}^2\) given by \(y = \rho x\), where \(\rho \in \mathbb{R}\).

1. Show that \(l\) intersects \(\mathbb{Z}^2\) if and only if \(\rho\) is rational.
2. Given a rational \(\rho > 0\), find the intersection of \(l\) with \(\mathbb{Z}^2\). (Hint: set \(\rho = r_{1}\) and use Proposition 3.5.)

Exercise \(\PageIndex{3}\)

Apply the Euclidean algorithm to find the greatest common divisor of the following number pairs. (Hint: replace negative numbers by positive ones. For the division algorithm applied to these pairs, see exercise 2.1)

1. \(110, 7\).
2. \(51, -30\).
3. \(-138 , 24\).
4. \(272 , 119\).
5. \(2378 , 1769\).
6. \(270 , 175, 560\).

Exercise \(\PageIndex{4}\)

This problem was taken (and reformulated) from [1].

1. Tile a \(188\) by \(158\) rectangle by squares using what is called a greedy algorithm. The first square is \(158\) by \(158\). The remaining rectangle is \(158\) by \(30\). Now the optimal choice is five \(30\) by \(30\) squares. What remains is an \(30\) by \(8\) rectangle, and so on. Explain how this is a visualization of equation (3.3).
2. Consider equation (3.1) or (3.2) and use a) to show that \[r_{1}r_{2} = \sum_{i=2}^{n} q_{i} r_{i}^2 \nonumber\] (Hint: assume that \(r_{1} > r_{2} > 0, r_{n} \ne 0\), and \(r_{n+1} = 0\).)

Exercise \(\PageIndex{5}\)

Determine if the following Diophantine equations admit a solution for \(x\) and \(y\). If yes, find a (particular) solution. (Hint: Use one of the algorithms in Section 3.2.)

1. \(110x+7y = 13\).
2. \(110x+7y = 5\).
3. \(51x-30y = 6\).
4. \(51x-30y = 7\).
5. \(-138x+24y = 7\).
6. \(-138x + 24y = 6\).
7. \(272x + 119y = 54\).
8. \(272x + 119y = 17\).
9. \(2378x + 1769y = 300\).
10. \(2378x + 1769y = 57\).
11. \(270x + 175, 560y = 170\).
12. \(270x + 175, 560y = 150\).

Exercise \(\PageIndex{6}\)

Find the solutionsn for \(x\) and \(y\) of the following (homogeneous) Diophantine equations. If yes, find a (particular) solution. (Hint: Use one of the algorithms in Section 3.2.)

1. \(110x+7y = 0\).
2. \(51x-30y = 0\).
3. \(-138x + 24y = 0\).
4. \(272x + 119y = 0\).
5. \(2378x + 1769y = 0\).
6. \(270x + 175, 560y = 0\).

Exercise \(\PageIndex{7}\)

Find all solutions for \(x\) and \(y\) in all problems of exercise 3.5 that admit a solution.

Exercise \(\PageIndex{8}\)

Use Corollary 3.11 to express the successive remainders \(r_{i}\) in each of the items in exercise 3.3 as \(r_{1}x_{i}+r_{2}y_{i}\).

Exercise \(\PageIndex{9}\)

Use Corollary 3.12 to express \(x_{i}\) and \(y_{i}\) in the successive remainders \(r_{i}\) in each of the items in exercise 3.3.

Exercise \(\PageIndex{10}\)

Consider the line \(l\) in \(\mathbb{R}\) defined by \(l(\xi) = \begin{pmatrix} {r_{1}}\\ {r_{2}}\\ {r_{3}} \end{pmatrix}\xi\), where \(\xi \in \mathbb{R}\) and the \(r_{i}\) are integers.

1. Show that \(l(\xi) \in \mathbb{Z}^3 \backslash \{\vec{0}\}\) if and only if \(\xi = \frac{t}{\gcd(r_{1}, r_{2}, r_{3})}\) and \(t \in \mathbb{Z}\).
2. Show that this implies that if any of the \(r_{i}\) is irrational, then l has no non-zero points in common with \(\mathbb{Z}^3\).

Exercise \(\PageIndex{11}\)

For this exercise, see exercises 2.2 and 2.3. Given three polynomials \(p_{1}\) and \(p_{2}\) with coefficients in \(\mathbb{Q}, \mathbb{R}\), or \(\mathbb{C}\). Define \(\gcd(p_{1}, p_{2})\) as the highest degree polynomial that is a divisor of both \(p_{1}\) and \(p_{2}\). (Remark: if you do this very carefully, you will realize that in this problem you really need to consider equivalence classes of polynomials, in the sense that two polynomials \(p\) and \(q\) are equivalent if there is a non-zero constant \(c \in \mathbb{R}\) such that \(p = cq\). While we are not pursuing the details here, it is good to keep this in the back of your mind.)

1. Describe an algorithm based on the division algorithm for polynomials to determine the greatest common divisor \(d(x)\) of \(p_{1}(x)\) and \(p_{2}(x)\). (Hint: see the Euclidean algorithm of Section 3.1. To see how to apply the division algorithm to polynomials, see exercise 2.2.)
2. Give a necessary and sufficient criterion for the existence of two polynomials \(g(x)\) and \(h(x)\) satisfying \[p_{1}(x)g(x)+p_{2}(x)h(x) = d(x) \nonumber\] (Hint: the same as Be ́zout’s lemma.)
3. Apply the trick of “backward” solving in Section 3.2 to determine an algorithm find polynomials \(g(x)\) and \(h(x)\) satisfying \[p_{1}(x)g(x)+p_{2}(x)h(x) = d(x) \nonumber\] where now \(d = \gcd(p_{1}, p_{2})\). This is the particular solution.
4. Find the general solution of \[p_{1}(x)g(x)+p_{2}(x)h(x) = 0 \nonumber\] (Hint: see Proposition 3.5.)
5. Find the general solution of \[p_{1}(x)g(x)+p_{2}(x)h(x) = e(x) \nonumber\] where now \(e\) is a polynomial times \(\gcd(p_{1}, p_{2})\). (Hint: see Corollary 3.10.)
6. Apply the above to \(p_{1}(x) = x^7-x^2+1, p_{2}(x) = x^3+x^2\), and \(e(x) = 2-x\). (Hint: We list the steps of the Euclidean algorithm:

\[(x^7-x^2+1) = (x^3+x^2)(x^4-x^3+x^2-x+1)+ (-2x^2+1) \nonumber\]

\[(x^3+x^2) = (-2x^2+1)(-\frac{1}{2}x-\frac{1}{2})+(\frac{1}{2}x+\frac{1}{2}) \nonumber\]

\[(-2x^2+1) = (\frac{1}{2}x+\frac{1}{2})(-4x+4)+(-1) \nonumber\]

\[(\frac{1}{2}x+\frac{1}{2}) = (-1)(-\frac{1}{2}x-\frac{1}{2}) \nonumber\]

Thus \(\gcd(p_{1}, p_{2}) = 1\), or in other words, \(p_{1}(x)\) and \(p_{2}(x)\) are relatively prime.)

Exercise \(\PageIndex{12}\)

Let \(p(x)\) be a polynomial and \(p′(x)\) its derivative.

1. Show that if \(p(x)\) has a multiple root \(\lambda\) of order \(k > 1\), then \(p′(x)\) has that same root of order \(k-1\). (Hint: Differentiate \(p(x) = h(x)(x-\lambda)^k \).)
2. Use exercise 3.11, to give an algorithm to find a polynomial \(q(x)\) that has the same roots as \(p(x)\), but all roots are simple (i.e. no multiple roots). (Hint: you need to divide \(p\) by \(\gcd(p, p′)\).)

Theorem 3.13 (Fundamental Theorem of Algebra)

A polynomial in \(\mathbb{C}[x]\) (the set of polynomials with complex coefficients) of degree \(d \ge 1\) has exactly \(d\) roots, counting multiplicity.

Exercise \(\PageIndex{13}\)

Assume that every polynomial \(f\) of degree \(d \ge 1\) has at least \(1\) root, prove the fundamental theorem of algebra. (Hint: let \(\rho\) be a root and use the division algorithm to write \(f(x) = (x-\rho)q(x)+r\) where \(r\) has degree \(0\).)

Exercise \(\PageIndex{14}\)

Let \(f\) and \(g\) be polynomials in \(\mathbb{Q}[x]\) with root \(\rho\) and suppose that \(g\) is minimal (Definition 1.13). Show that \(g | f\). (Hint: use the division algorithm of exercises 2.2 and 2.3 to write \(f(x) = g(x)q(x)+r(x)\) where \(r\) has degree less than \(g\).)

Definition 3.14

The sequence \(\{F_{i}\}^{\infty}_{i=0}\) of Fibonacci numbers \(F_{i}\) is defined as follows

\[\begin{array} {ccc} {F_{0} = 0,}&{F_{1} = 1,}&{\forall i > 1 : F_{i+1} = F_{i}+F_{i-1}} \nonumber \end{array}\]

Exercise \(\PageIndex{15}\)

Denote the golden mean, or \(\frac{1+\sqrt{5}}{2} \approx 1.618\), by \(g\).

1. Show that \(g^2 = g+1\) and thus \(g^{n+1} = g^n +g^{n-1}\).
2. Show that \(F_{3} \ge g^1\) and \(F_{2} \ge g^0\).
3. Use induction to show that \(F_{n+2} \ge g^{n}\) for \(n > 0\).
4. Use the fact that \(5 \log_{10} \frac{1+\sqrt{5}}{2} \approx 1.045\), to show that \(F_{5k+2} > 10^k\) for \(k \ge 0\).

Exercise \(\PageIndex{16}\)

Consider the equations in (3.1) and assume that \(r_{n+2} = 0\) and \(r_{n+1} > 0\).

1. Show that \(r_{n+1} \ge F_{2} = 1\) and \(r_{n} \ge F_{3} = 2\). (Hint: \(r(i)\) is strictly increasing.)
2. Show that \(r_{1} \ge F_{n+2}\).
3. Suppose \(r_{1}\) and \(r_{2}\) in \(\mathbb{N}\) and \(\mbox{max} \{r_{1}, r_{2}\} < F_{n+2}\). Show that the Euclidean Algorithm to calculate \(\gcd (r_{1}, r_{2})\) takes at most \(n-1\) iterates of the division algorithm.

Exercise \(\PageIndex{17}\)

Use exercises 3.15 and 3.16 to show that the Euclidean Algorithm to calculate \(\gcd(r_{1}, r_{2})\) takes at most \(5k-1\) iterates where \(k\) is the number of decimal places of \(\mbox{max}\{r_{1}, r_{2}\}\). (This is known as Lame ́’s theorem.)

Exercise \(\PageIndex{18}\)

1. Write the numbers \(287\), \(513\), and \(999\) in base \(2\), \(3\), and \(7\), using the division algorithm. Do not use a calculating device. (Hint: start with base \(10\). For example, \[287 = 28 \cdot 10+7 \nonumber\]\[28 = 2 \cdot 10+8 \nonumber\]\[2 = 0 \cdot 10+2 \nonumber\]Hence the number of in base \(10\) is \(2 \cdot 10^2+8 \cdot 10^1+3 \cdot 10^0\).)
2. Show that to write \(n\) in base \(b\) takes about \(\mbox{log}_{b} n\) divisions.

Exercise \(\PageIndex{19}\)

Suppose \(\{b_{i}\}_{i=1}^{n}\) are positive integers such that \(\gcd (b_{i}, b_{j}) = 1\) for \(i \ne j\). We want to know all \(z\) that satisfy

\[\begin{array} {ccc} {z = b_{i} c_{i}}&{for}&{i \in \{1, \cdots, m\}} \nonumber \end{array}\]

1. Set \(B = \prod_{i=1}^{n} b_{i}\) and show that the homogeneous problem is solved by \[z = _{B} 0 \nonumber\] (Hint: use corollary 3.10)
2. Check that \[z = \sum_{i=1}^{n} \frac{B}{b_{i}} x_{i} c_{i} \nonumber\] is a particular solution.
3. Find the general solution \[z = B \sum_{i=1}^{n} \frac{B}{b_{i}} x_{i} c_{i} \nonumber\] This is known as the Chinese Remainder Theroem.

Exercise \(\PageIndex{20}\)

Use exercise 3.19 to solve

\[z = _{2} 1 \nonumber\]

\[z = _{3} 2 \nonumber\]

\[z = _{5} 3 \nonumber\]

\[z = _{7} 5 \nonumber\]

Exercise \(\PageIndex{21}\)

Assume \(\gcd (F_{n}, F_{n+1}) = 1\). Use Exercise 3.19 to solve:

\[z = _{F_{n}} F_{n-1} \nonumber\]

\[z = _{F_{n+1}} F_{n} \nonumber\]

where \(F_{n}\) are the Fibonacci numbers of Definition 3.14.

Exercise \(\PageIndex{22}\) (The Chinese remainder theorem generalized)

Suppose \(\{b_{i}\}_{i=1}^{n}\) are positive integers. We want to know all \(z\) that satisfy

\[\begin{array} {ccc} {z = b_{i} c_{i}}&{for}&{i \in \{1, \cdots, m\}} \nonumber \end{array}\]

1. Set \(B = \mbox{lcm} (b_{1}, b_{2}, \cdots, b_{n})\) and show that the homogeneous problem is solved by \[z = _{B} 0 \nonumber\]
2. Show that if there is a particular solution then \[\forall i \ne j : c_{i} = _{\gcd (b_{i},b_{j})} c_{j} \nonumber\]
3. Formulate the general solution when the condition in b) holds.

Exercise \(\PageIndex{23}\)

Assume \(\gcd (F_{n}, F_{n+1}) = 1\). Use Exercise 3.21 to solve:

\[z = _{6} 15 \nonumber\]

\[z = _{10} 6 \nonumber\]

\[z = _{15} 10 \nonumber\]

See also exercise 2.6.