Exercises

Skip to main content

\(\newcommand{\im}{{\mathrm{im}}} \newcommand{\given}{{\, :\,}} \newcommand{\hanoi}{\mathrm{hanoi}} \newcommand{\lcm}{{\mathrm{lcm}}} \newcommand{\ID}{{\mathrm{ID}}} \newcommand{\chr}{{\mathtt{chr}}} \newcommand{\ord}{{\mathtt{ord}}} \newcommand{\set}[1]{\left\lbrace #1 \right\rbrace} \newcommand{\seq}[2]{( #1 )_{#2}} \newcommand{\gr}[1]{\left( #1 \right)} \newcommand{\abs}[1]{\left| #1 \right|} \newcommand{\size}[1]{\# #1} \newcommand{\id}[1]{\mathrm{id}_{#1}} \newcommand{\ip}[1]{\left\langle #1 \right\rangle} \newcommand{\floor}[1]{\left\lfloor #1\right\rfloor} \newcommand{\ceiling}[1]{\left\lceil #1\right\rceil} \newcommand{\indemph}[1]{{\textbf{\emph{#1}}\index{#1}}} \renewcommand{\implies}{\to} \renewcommand{\iff}{\leftrightarrow} \newcommand{\lxor}{\oplus} \newcommand{\cP}{\wp} \newcommand{\pset}{\cP} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\NN}{\mathbb{N}} \newcommand{\CC}{\mathbb{C}} \newcommand{\RR}{\mathbb{R}} \newcommand{\barr}[1]{\overline{#1}} \newcommand{\sage}{\textsc{Sage}} \newcommand{\magma}{\textsc{Magma}} \newcommand{\bob}{\text{Bob}} \newcommand{\true}{\text{T}} \newcommand{\false}{\text{F}} \newcommand{\ahat}{\hat{a}} \newcommand{\ah}{\ahat} \newcommand{\bhat}{\hat{b}} \newcommand{\abar}{\bar{a}} \newcommand{\cA}{\mathcal{A}} \newcommand{\cF}{\mathcal{F}} \newcommand{\cW}{\mathcal{W}} \newcommand{\todo}[1]{{\color{red} TODO: #1}} \renewcommand{\div}{\operatorname{div}} \newcommand{\gexp}[3]{#1^{#2 #3}} \newcommand{\gexpp}[3]{\displaystyle\left(#1\right)^{#2 #3}} \newcommand{\glog}[3]{\log_{#1}^{#3}#2} \def\dbend{{!!!}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} \)

Exercises 5.3.4 Exercises

1.

Give the definition for these terms. Be sure to set up any notation that is required.

prime
🔗

🔗
composite
🔗

🔗
twin primes
🔗

🔗
greatest common divisor of integers
🔗

🔗
relatively prime or coprime integers
🔗

🔗
least common multiple
🔗

🔗
Euler phi function
🔗

🔗

2.

State precisely the Fundamental Theorem of Arithmetic. Be sure to set up any notation that is required.

3.

State precisely Bézout’s theorem. Be sure to set up any notation that is required.

4.

Compute \(\phi(15)\text{.}\)

5.

Compute \(\phi(24)\text{.}\)

6.

Which positive integers less than \(12\) are relatively prime to \(12\text{?}\)

7.

Which positive integers less than \(25\) are relatively prime to \(25\text{?}\)

8.

Determine whether these integers are prime.

\(\displaystyle 21\)
🔗

🔗
\(\displaystyle 100\)
🔗

🔗
\(\displaystyle 101\)
🔗

🔗
\(\displaystyle 253\)
🔗

🔗
\(\displaystyle 91\)
🔗

🔗

9.

Compute the greatest common divisor and least common multiple of the following integers.

\(131\) and \(19\)
🔗

🔗
\(260\) and \(77\)
🔗

🔗
\(46\) and \(34\)
🔗

🔗
\(132\) and \(192\)
🔗

🔗
\(293\) and \(37\)
🔗

🔗
\(15\) and \(87\)
🔗

🔗
\(57\) and \(93\)
🔗

🔗

10.

With the Euclidean algorithm compute the greatest common divisor and least common multiple of the following integers.

\(36503\) and \(5017\)
🔗

🔗
\(8479\) and \(12017\)
🔗

🔗
\(15089\) and \(16999\)
🔗

🔗
\(11371\) and \(10541\)
🔗

🔗
\(14453\) and \(26671\)
🔗

🔗

11.

With the Euclidean algroithm compute the greatest common divisor and least common multiple of the following integers.

\(3599\) and \(5917\)
🔗

🔗
\(9701\) and \(8633\)
🔗

🔗
\(23707\) and \(5809\)
🔗

🔗
\(8413\) and \(12709\)
🔗

🔗
\(19303\) and \(5917\)
🔗

🔗

12.

Show that \(\gcd(75,53) = 1\text{.}\) Find integers \(s\) and \(t\) such that

\begin{equation*} 75s + 53 t = 1. \end{equation*}

Use these to find an integral solution to

\begin{equation*} 75x + 53y = 13. \end{equation*}

Check your solutions by plugging back in.

13.

Show that \(\gcd(75,10) = 5\text{.}\) Use this to show that

\begin{equation*} 75x + 10y = 13 \end{equation*}

has no integral solutions.

14.

Explain why there are no integers \(s\) and \(t\) such that \(25 s + 30 t = 1\text{.}\)

15.

Find integers \(s\) and \(t\) such that \(2018s + 253t = 1\text{.}\)

16.

Use the Extended Euclidean Algorithm to find integers \(s\) and \(t\) such that

\begin{equation*} 4321s + 12367 t = 149. \end{equation*}

Check your solution by plugging back in.

17.

Use the Extended Euclidean Algorithm to find integers \(s\) and \(t\) such that

\begin{equation*} 5293s + 8509t = 67. \end{equation*}

Check your solution by plugging back in.

18.

Use the Extended Euclidean Algorithm to find integers \(s\) and \(t\) such that

\begin{equation*} 27263s + 44377t = 199. \end{equation*}

Check your solution by plugging back in. Use the Sieve of Eratosthenes to find primes up to \(100\text{.}\) (You should find \(25\) primes less than \(100\text{.}\))