7.6: Exercises

Last updated
Save as PDF

Page ID: 99095

Bob Dumas and John E. McCarthy
University of Washington and Washington University in St. Louis

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

EXERCISE 7.1. Let \(n \in \mathbb{N}\). Prove that if \(n\) is not prime then \(n\) has a prime factor \(p \leq \sqrt{n}\).

EXERCISE \(7.2\). Are \(15,462,227\) and \(15,462,229\) relatively prime?

EXERCISE 7.3. If \(n \in \mathbb{N}\), under what conditions are \(n\) and \(n+2\) relatively prime?

EXERCISE 7.4. Prove that every natural number may be written as the product of a power of 2 and an odd number.

EXERCISE 7.5. Find \(\operatorname{gcd}(8243235,453169)\).

EXERCISE 7.6. Find \(\operatorname{gcd}(15570555,10872579)\).

EXERCISE 7.7. Let \(a\) and \(b\) be integers and \(m=\operatorname{gcd}(a, b)\). Prove that \(\frac{a}{m}\) and \(\frac{b}{m}\) are relatively prime integers.

EXERCISE 7.8. Let \(a\) and \(b\) be positive integers with prime decomposition given by \[a=\prod_{n=1}^{N} p_{n}^{r_{n}}\] and \[b=\prod_{n=1}^{N} p_{n}^{s_{n}}\] where \(p_{n}, r_{n}, s_{n} \in \mathbb{N}\) and \(p_{n}\) is prime for \(1 \leq n \leq N\). Prove that if \(t_{n}=\min \left(r_{n}, s_{n}\right)\) for \(1 \leq n \leq N\), then \[\operatorname{gcd}(a, b)=\prod_{n=1}^{N} p_{n}^{t_{n}} .\] EXERCISE 7.9. In the statement of Lemma 7.14, suppose that \(\operatorname{gcd}(a, n) \neq\) 1. Prove that the function \(\phi_{a}\) is not a permutation of \(\mathbb{Z}_{n}^{*}\). EXERCISE 7.10. Prove Proposition 7.16.

EXERCISE 7.11. Is 4757 prime?

EXERCISE 7.12. Define an ideal of \(\mathbb{Z}\) in the natural way: A set \(I \subseteq \mathbb{Z}\) is an ideal of \(\mathbb{Z}\) if for any \(m, n \in I\) and \(c \in \mathbb{Z}\),

\(m+n \in I\)

and

\(m c \in I\).

If \(a, b \in \mathbb{Z}\), prove that the set of integer combinations of \(a\) and \(b\) are an ideal of \(\mathbb{Z}\).

EXERCISE 7.13. Prove that every ideal of \(\mathbb{Z}\) is principal. (Hint: find the generator of the ideal.)

EXERCISE 7.14. Let \(p\) be prime and \(\mathbb{Z}_{p}[x]\) be the set of polynomials with coefficients in \(\mathbb{Z}_{p}\). What can you say about the roots of the polynomial \(x^{p-1}-[1]\) in \(\mathbb{Z}_{p}\) ? (We say that \([a] \in \mathbb{Z}_{p}\) is a root of a polynomial \(f \in \mathbb{Z}_{p}[x]\) if \(\left.f([a])=[0] .\right)\)

EXERCISE 7.15. Prove that 0 is the additive identity in \(\mathbb{R}[x]\) and 1 is the multiplicative identity in \(\mathbb{R}[x]\). Use the formal definitions of addition and multiplication in \(\mathbb{R}[x]\).

EXERCISE 7.16. Prove that the degree of the product of polynomials is equal to the sum of the degrees of the polynomials. Use the formal definition of multiplication in \(\mathbb{R}[x]\).

EXERCISE 7.17. Let \(p \in \mathbb{R}[x]\). Prove that \(p\) has an additive inverse in \(\mathbb{R}[x]\). Prove that \(p\) has a multiplicative inverse iff \(p\) has degree 0 . Use the formal definitions of addition and multiplication in \(\mathbb{R}[x]\).

EXERCISE 7.18. Prove that addition and multiplication in \(\mathbb{R}[x]\) are associative and commutative, and that the distributive property holds. Use the formal definitions of addition and multiplication in \(\mathbb{R}[x]\).

EXERCISE 7.19. For \(0 \leq n \leq N\), let \(a_{n} \in \mathbb{R}\). If \(f=\sum_{n=0}^{N} a_{n} x^{n}\) and \(g(x)=x-1\), find the unique quotient and remainder where \(f\) is the dividend and \(g\) is the divisor. EXERCISE 7.20. Let \(f, g, q \in \mathbb{R}[x], g \neq 0\). Suppose that \(f\) is the dividend, \(g\) the divisor and \(q\) the quotient. Prove that the sum of the degree of \(g\) and the degree of \(q\) equals the degree of \(f\).

EXERCISE 7.21. Is there a version of the Euclidean Algorithm for \(\mathbb{R}[x]\) ?