1E: Exercises
- Page ID
- 131034
\( \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}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)For every positive integer \(n\), prove that \(\frac{1}{(1)(2)}+\frac{1}{(2)(3)}+\cdots +\frac{1}{(n)(n+1)}=\frac{n}{n+1}\).
- Answer
-
We can rewrite each term as \(\frac{1}{k(k+1)} = \frac{k+1 - k}{k(k+1)} = \frac{1}{k} - \frac{1}{k+1}\). Therefore, the sum telescopes as follows: \begin{align*} &\frac{1}{1} - \frac{1}{2} + \frac{1}{2} - \frac{1}{3} + \cdots + \frac{1}{n} - \frac{1}{n+1} \\ &= 1 - \frac{1}{n+1} = \frac{n}{n+1}. \end{align*}
For any positive integer n, prove that \(2^n3^{2n}-1\) is always divisible by \(17\).
- Answer
-
By Fermat's Little Theorem, \(2^{16} \equiv 1 \pmod{17}$ and $3^{16} \equiv 1 \pmod{17}\). Therefore, \(2^{16n} \equiv 1 \pmod{17}\) and \(3^{32n} \equiv 1 \pmod{17}\). Hence, \(2^n3^{2n} - 1 \equiv 1 \cdot 1 - 1 \equiv 0 \pmod{17}\).
a. Let \(a, b, c \in \mathbb{Z}_+\). Show that \(\gcd(a, bc) = 1\) if and only if \(\gcd(a, b) = 1\) and \(\gcd(a, c) = 1\).
b. Let \(a,b,c,d \in \mathbb{Z}.\) If \(a|b\) and \(c|d\), show that \( gcd(a,c)|gcd(b,d).\)
Show that \(a^5 \equiv a \pmod{5}\) for all integers \(a\).
Using Euclidean algorithm to find \(\gcd(2520,154)\) and express \(\gcd(2520, 154)\) as an integer combination of \(2520\) and \(154\). Also,
Using the Euclidean algorithm to find \(\gcd(-2520,154)\) and express \(\gcd(-2520, 154)\) as an integer combination of \(-2520\) and \(154\).
For every positive integer \(n\), prove that \(n^3-n\) is divisible by \(3\).
For any \(k \in \mathbb{N}\) prove that \(\gcd(4k+3, 7k+5)=1\).
a) Use the Euclidean algorithm to find the \(\gcd(-29,571)\)?
b) Find integers \(x\) and \(y\) s.t. \(\gcd(-29,571)= -29(x)+571(y)\)?
Show that any two consecutive odd integers are relatively prime.
If \(m,n\) are any odd integers, show that \(m^2-n^2\) is divisible by \(8.\)
a) Prove that for all integers \( n\geq 1,\)
\( \frac{1}{2!}+ \frac{2}{3!} + \cdots +\frac{n}{(n+1)!} = 1-\frac{1}{(n+1)!}.\)
b) Prove that for all integers \( n\geq 1,\)
\( \frac{1}{\sqrt{1}}+ \frac{1}{\sqrt{2}} + \cdots + \frac{1}{\sqrt{n}} \geq \sqrt{n}.\)
For integer \(n\geq 1\), define
\(S_n=- {2 \choose 2}+{3 \choose 2}-{4 \choose 2}+{5 \choose 2}\cdots + {2n+1 \choose 2}.\)
-
Evaluate \(S_n\) for \(n=1,2,3,4 \) and \(5.\)
-
Use part (a) to guess a formula for \(S_n.\)
-
Use mathematical induction to prove your guess.
Find the remainder when \(8^{391} \) is divided by \(5.\)
For each of the following pairs of integers \(a\) and \(n.\) show that \(a\) and \(n\) are relatively prime, determine multuplicative inverse of \([a]\) in \(\mathbb{Z}_n,\) and Find all integers \(x\) for \(ax \cong 11 (mod \, n).\)
- \( a=16, n=35.\)
- \(a=69, n=89.\)
Find the remainder when \((201)(203)(205)(207)\) is divided by \(13.\)