# 1E: Exercises

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\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 \|}$$ $$\newcommand{\inner}{\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 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

1. 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}$$.

2. For any positive integer n, prove that $$2^n3^{2n}-1$$ is always divisible by $$17$$.

3. 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$$.

4. Show that $$a^5 \equiv a \pmod{5}$$ for all integers $$a$$.

5. For every positive integer $$n$$, prove that $$n^3-n$$ is divisible by $$3$$.

6. 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$$.

7. Using Euclidean algorithm to find $$\gcd(2520,154)$$ and express $$\gcd(2520, 154)$$ as an integer combination of $$2520$$ and $$154$$.

8. Using the Euclidean algorithm to find $$\gcd(-2520,154)$$ and express $$\gcd(-2520, 154)$$ as an integer combination of $$-2520$$ and $$154$$.

9. For any $$k \in \mathbb{N}$$ prove that $$\gcd(4k+3, 7k+5)=1$$.

10. 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)$$?

1. Show that any two consecutive odd integers are relatively prime.

1.  If $$m,n$$ are any odd integers, show that $$m^2-n^2$$ is divisible by $$8.$$

1. Prove that for all integers $$n\geq 1,$$

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

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}.$$

1. 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}.$$

1. Evaluate $$S_n$$ for $$n=1,2,3,4$$ and $$5.$$

2. Use part (a) to guess a formula for $$S_n.$$

3. 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.$$

This page titled 1E: Exercises is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Pamini Thangarajah.