1E: Exercises
- Page ID
- 131034
-
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.\)