1E: Exercises

Last updated
Save as PDF

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

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}\).
For any positive integer n, prove that \(2^n3^{2n}-1\) is always divisible by \(17\).
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\).
Show that \(a^5 \equiv a \pmod{5}\) for all integers \(a\).
For every positive integer \(n\), prove that \(n^3-n\) is divisible by \(3\).
Determine the value \(\phi(n)\) for each integer \(n \le 30\). For \(n \in \mathbb{N}\), \(\phi(n)\) is defined to be the number of positive integers less than \(n\) that are relatively prime to \(n\).
Using Euclidean algorithm to find \(\gcd(2520,154)\) and express \(\gcd(2520, 154)\) as an integer combination of \(2520\) and \(154\).
Using the Euclidean algorithm to find \(\gcd(-2520,154)\) and express \(\gcd(-2520, 154)\) as an integer combination of \(-2520\) and \(154\).
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.\)

Prove that for all integers \( n\geq 1,\)

\( \frac{1}{2!}+ \frac{2}{3!} + \cdots +\frac{n}{(n+1)!} = 1-\frac{1}{(n+1)!}.\)

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.

16. Let \(a,b,c,d \in \mathbb{Z}.\) If \(a|b\) and \(c|d\), show that \( gcd(a,c)|gcd(b,d).\)

17. Find the remainder when \(8^{391} \) is divided by \(5.\)