1E: Exercises

Exercise \(\PageIndex{1}\)

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

Answer

1. Apply the Euclidean algorithm:
\begin{align*}
2520 &= (16)(154) + 56 \\
154 &= (2)(56) + 42 \\
56 &= (1)(42) + 14 \\
42 &= (3)(14) + 0
\end{align*}
Thus, \(\gcd(2520, 154) = 14\). Express \(14\) as a linear combination:
\begin{align*}
14 &= 56 + (-1)(42) \\
&= 56 + (-1)(154 + (-2)(56)) = (3)(56) + (-1)(154) \\
&= (3)(2520 + (-16)(154)) + (-1)(154) = (3)(2520) + (-49)(154)
\end{align*}
So, \(\gcd(2520, 154) = 14 = (3)(2520) + (-49)(154)\).

2. Since \(\gcd(2520, 154) = 14= (3)(2520) + (-49)(154), \gcd(-2520, 154) = 14= (-3)(-2520) + (-49)(154)\). 

Exercise \(\PageIndex{2}\)

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

Answer

a) Since \(\gcd(29, -571) = \gcd(29, 571)\):
\begin{align*}
571 &= (19)(29) + 20 \\
29 &= (1)(20) + 9 \\
20 &= (2)(9) + 2 \\
9 &= (4)(2) + 1 \\
2 &= (2)(1) + 0
\end{align*}
Thus, \(\gcd(29, -571) = 1\).

b) Working backward:
\begin{align*}
1 &= 9 + (-4)(2) \\
&= 9 + (-4)(20 + (-2)(9)) = (9)(9) + (-4)(20) \\
&= (9)(29 - 20) + (-4)(20) = (9)(29) + (-13)(20) \\
&= (9)(29) + (-13)(571 + (-19)(29)) = (256)(29) + (-13)(571)
\end{align*}
Rewriting in terms of \(-571\):
\(
1 = (29)(256) + (-571)(13)
\)
Thus, \(x = 256\) and \(y = 13\).

 

Exercise \(\PageIndex{3}\)

Determine whether each integer is prime.

1. \(2026\)

2. \(233\)

3. \(341\)

Answer

1. Since \(2026\) is even and greater than \(2\), so it is composite (\(2026 = (2)(1013)\)).

2. Since \(\sqrt{233} \approx 15.26\), the primes to check are \(2, 3, 5, 7, 11, 13\). None divide \(233\). Thus, \(233\) is prime.

3. \(341 = (11)(31)\), so it is composite.

Exercise \(\PageIndex{4}\)

Find the prime factorization of

1. \(7560\)

2. \( 1351\)

Answer

 1. \(7560 = (10)(756) = (2)(5)(4)(189) = (2^3)(3^3)(5)(7)\).

2. \(1351 = (7)(193)\) (\(193\) is prime)(check!).

Exercise \(\PageIndex{5}\)

Compute \( \gcd(2^5 3^2 5^3, \;2^3 3^4 5^2), 
lcm(2^5 3^2 5^3,\;2^3 3^4 5^2).
\)

Answer

\(\gcd(2^5 3^2 5^3, \;2^3 3^4 5^2) =2^3 3^2 5^2\) and \(lcm(2^5 3^2 5^3,\;2^3 3^4 5^2)=2^5 3^4 5^3.\)

Exercise \(\PageIndex{6}\)

Prove the true statements and provide counterexamples for the false ones.
Let \(a,b\) and \(c\) be integers.

1. If \(a|b\) then \(b|a\).
2. If \(a|bc\) then \(a|b\) and \(a|c.\)
3. If \(a|b\) and \(a|c\) then \(a|bc\).
4. If \(a|b\) and \(a|c\) then \(a|(b+c)\) and \(a|(b-c)\).
5. If \(a|(b+c)\) and \(a|(b-c)\) then \(a|b\) and \(a|c\).
6. If \(a|b\) and \(a|c\) then \(a|(b+c)\) and \(a|(2b+c)\).
7. If \(a|(b+c)\) and \(a|(2b+c)\) then \(a|b\) and \(a|c\).
8. If \(a|b\) and \(a|c\) then \(a|(b + c)\).
9. If \(a|(b + c)\) then \(a|b\) and \(a|c\).
10. If \(a|bc\) then \(a|b\) and \(a|c\).
11. If \((a+b)|c\) then \(a|c\) and \(b|c\).
12. If \(a|c\) and \(b|c\) then \((a+b)|c\).
13. If \(a^3|b^4\) then \(a|b.\)
14. If \(a|b\) then \(a^3 \mid b^5\).
15. If \(c|a\) and \(d|b\) then \(cd|ab\).

Answer

1. False: \(2 \mid 4\) but \(4 \nmid 2\).

2. false: \(6\mid(2)(3)\) but \(6 \nmid 2\).

Exercise \(\PageIndex{7}\)

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

Exercise \(\PageIndex{8}\)

Show that any two consecutive odd integers are relatively prime.

Exercise \(\PageIndex{9}\)

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

Complete the multiplication table modulo \(5\) for the nonzero residue classes. Use the table to find all multiplicative inverses.
\[
\begin{array}{c|cccc}
\cdot &1&2&3&4\\ \hline
1&&&&\\
2&&&&\\
3&&&&\\
4&&&&
\end{array}
\]

 

Exercise \(\PageIndex{11}\)

1. Let \(n\geq2\) and suppose \(a^2\equiv1\pmod n. \)
Prove that \(a\) is invertible modulo \(n\) and determine its inverse.

2. Give an example modulo \(8\) showing that \(a^2\equiv1\pmod n\) does not necessarily imply \(a\equiv1\) or \(a\equiv-1\pmod n\).

Exercise \(\PageIndex{12}\)

 If possible, find the multiplicative inverse of the following:

1. \(6\pmod{11}\)
2. \(8\pmod{12}\)
3.  \(9\pmod{16}\)
4.  \(14\pmod{21}\)
5. \(15\pmod{26}\)
6.  \(11\pmod{28}\)
7. \(17\pmod{43}\)
8.  \(23\pmod{60}\)
9.  \(29\pmod{71}\)
10.  \(37\pmod{101}\)
11. \(251 \pmod{997}\)

Exercise \(\PageIndex{13}\)

1.Show that \(a^5 \equiv  a \pmod{5}\) for all integers \(a\).

2. Let \(a,b\) and \(c\) be integers. Suppose
\(
ab\equiv1\pmod n
\quad\text{and}\quad
bc\equiv1\pmod n.
\)
Prove that
\(
a\equiv c\pmod n.
\)

Exercise \(\PageIndex{14}\)

For every positive integer \(n\), prove that \(\dfrac{1}{(1)(2)}+\dfrac{1}{(2)(3)}+\cdots +\dfrac{1}{(n)(n+1)}=\dfrac{n}{n+1}\).

Answer

Let \(n\) be a positive integer. We can rewrite each term as \(\dfrac{1}{k(k+1)} = \dfrac{k+1 - k}{k(k+1)} = \dfrac{1}{k} - \dfrac{1}{k+1}\). Therefore, the sum telescopes as follows: \begin{align*} &\dfrac{1}{1} - \dfrac{1}{2} + \dfrac{1}{2} - \dfrac{1}{3} + \cdots + \dfrac{1}{n} - \dfrac{1}{n+1} \\ &= 1 - \dfrac{1}{n+1} = \dfrac{n}{n+1}. \end{align*}

Exercise \(\PageIndex{15}\)

1. For every positive integer \(n\), prove that \(n^3-n\) is divisible by \(3\).
2.  If \(m,n\) are any odd integers, show that \(m^2-n^2\) is divisible by \(8.\)
3. For any positive integer n, prove that \(2^n3^{2n}-1\) is always divisible by \(17\).

Answer

Let \(n\) be a positive integer. 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{16}\)

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

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

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

Exercise \(\PageIndex{19}\)

Determine whether each congruence has a solution. If it does, list all incongruent solutions.

1. \(
    3x\equiv 4\pmod 7
    \)

2.  \(
    5x\equiv 9\pmod{13}
    \)

3. \(
    7x\equiv 3\pmod{11}
    \)

4. \(
    11x\equiv 7\pmod{19}
    \)

5. \(
6x\equiv 8\pmod{14}
\)

6. \(
9x\equiv 12\pmod{15}
\)

7. \(
14x\equiv 21\pmod{35}
\)

8. \(6x\equiv 5\pmod{15}
\)

9. \(
8x\equiv 6\pmod{14}
\)

10. \(
12x\equiv 15\pmod{18}
\)

11. \(
15x\equiv 25\pmod{35}
\)

12. \(
18x\equiv 30\pmod{42}.
\)

13. \(
35x\equiv 17\pmod{22}
\)

14. \(
38x\equiv 7\pmod{101}
\)

15. \(
29x\equiv 11\pmod{73}.
\)

 

Exercise \(\PageIndex{20}\)

For each of the following pairs of integers \(a\) and \(n.\) show that \(a\) and \(n\) are relatively prime, determine the  multiplicative inverse of \([a]\) in \(\mathbb{Z}_n,\) and Find all integers \(x\) for \(ax \equiv 11 (mod \, n).\)

1.  \( a=16, n=35.\)
2. \(a=69, n=89.\)

Exercise \(\PageIndex{21}\)

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

Exercise \(\PageIndex{22}\)

A student argues that
\(
6x\equiv 6y\pmod{15}
\)
implies
\(
x\equiv y\pmod{15}
\)
because the factor \(6\) can be canceled from both sides.

Is the argument valid?

If not, determine the strongest congruence involving \(x\) and \(y\) that follows
from
\(
6x\equiv6y\pmod{15}.
\)