1E: Exercises

Exercise $\PageIndex{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}$.

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

Exercise $\PageIndex{2}$

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

Exercise $\PageIndex{3}$

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

Exercise $\PageIndex{4}$

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

Exercise $\PageIndex{5}$

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

Exercise $\PageIndex{6}$

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

Exercise $\PageIndex{7}$

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

Exercise $\PageIndex{8}$

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

Exercise $\PageIndex{9}$

Show that any two consecutive odd integers are relatively prime.

 

Exercise $\PageIndex{10}$

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

 

Exercise $\PageIndex{11}$

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

 

 

Exercise $\PageIndex{12}$

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.

Exercise $\PageIndex{13}$

Find the remainder when $8^{391}$ is divided by $5.$

Exercise $\PageIndex{14}$

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

1.  $a=16, n=35.$
2. $a=69, n=89.$

Exercise $\PageIndex{15}$

Find the remainder when $(201)(203)(205)(207)$ is divided by $13.$