4.E: Exercises

Last updated
Save as PDF

Page ID: 7558

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$ \newcommand{\dsum}{\displaystyle\sum\limits} $

$ \newcommand{\dint}{\displaystyle\int\limits} $

$ \newcommand{\dlim}{\displaystyle\lim\limits} $

$ \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]{\| #1 \|}$

$ \newcommand{\inner}[2]{\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]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\AA}{\unicode[.8,0]{x212B}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$\newcommand{\longvect}{\overrightarrow}$

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$\newcommand{\ket}[1]{\left| #1 \right>}$
$\newcommand{\bra}[1]{\left< #1 \right|}$
$\newcommand{\braket}[2]{\left< #1 \vphantom{#2} \right| \left. #2 \vphantom{#1} \right>}$
$\newcommand{\braopket}[3]{\left< #1 \vphantom{#2}\vphantom{#3} \right| #2 \vphantom{#1}\vphantom{#3} \left| #3 \vphantom{#1}\vphantom{#2} \right>}$
$\newcommand{\qmvec}[1]{\mathbf{\vec{#1}}}$
$\newcommand{\op}[1]{\hat{\mathbf{#1}}}$
$\newcommand{\expect}[1]{\langle #1 \rangle}$
$\newcommand{\dfn}[1]{\emph{\textbf{#1}}}$

$\newcommand{\avec}{\mathbf a}$ $\newcommand{\bvec}{\mathbf b}$ $\newcommand{\cvec}{\mathbf c}$ $\newcommand{\dvec}{\mathbf d}$ $\newcommand{\dtil}{\widetilde{\mathbf d}}$ $\newcommand{\evec}{\mathbf e}$ $\newcommand{\fvec}{\mathbf f}$ $\newcommand{\nvec}{\mathbf n}$ $\newcommand{\pvec}{\mathbf p}$ $\newcommand{\qvec}{\mathbf q}$ $\newcommand{\svec}{\mathbf s}$ $\newcommand{\tvec}{\mathbf t}$ $\newcommand{\uvec}{\mathbf u}$ $\newcommand{\vvec}{\mathbf v}$ $\newcommand{\wvec}{\mathbf w}$ $\newcommand{\xvec}{\mathbf x}$ $\newcommand{\yvec}{\mathbf y}$ $\newcommand{\zvec}{\mathbf z}$ $\newcommand{\rvec}{\mathbf r}$ $\newcommand{\mvec}{\mathbf m}$ $\newcommand{\zerovec}{\mathbf 0}$ $\newcommand{\onevec}{\mathbf 1}$ $\newcommand{\real}{\mathbb R}$ $\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$ $\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$ $\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$ $\newcommand{\laspan}[1]{\text{Span}\{#1\}}$ $\newcommand{\bcal}{\cal B}$ $\newcommand{\ccal}{\cal C}$ $\newcommand{\scal}{\cal S}$ $\newcommand{\wcal}{\cal W}$ $\newcommand{\ecal}{\cal E}$ $\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$ $\newcommand{\gray}[1]{\color{gray}{#1}}$ $\newcommand{\lgray}[1]{\color{lightgray}{#1}}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\row}{\text{Row}}$ $\newcommand{\col}{\text{Col}}$ $\renewcommand{\row}{\text{Row}}$ $\newcommand{\nul}{\text{Nul}}$ $\newcommand{\var}{\text{Var}}$ $\newcommand{\corr}{\text{corr}}$ $\newcommand{\len}[1]{\left|#1\right|}$ $\newcommand{\bbar}{\overline{\bvec}}$ $\newcommand{\bhat}{\widehat{\bvec}}$ $\newcommand{\bperp}{\bvec^\perp}$ $\newcommand{\xhat}{\widehat{\xvec}}$ $\newcommand{\vhat}{\widehat{\vvec}}$ $\newcommand{\uhat}{\widehat{\uvec}}$ $\newcommand{\what}{\widehat{\wvec}}$ $\newcommand{\Sighat}{\widehat{\Sigma}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\newcommand{\amp}{&}$ $\definecolor{fillinmathshade}{gray}{0.9}$

Exercise $\PageIndex{1}$:

Find the $\gcd$ of:

1. $10$ and $75$
2. $48$ and $360$

3. $9357$ and $5864$

Answer: $GCD(9357,5864).png$

Find the lcm of:

1. $10$ and $75$
2. $48$ and $360$

3. $9357$ and $5864$

Exercise $\PageIndex{2}$:

Using GCD determine how many packages of hotdogs and hotdog buns are needed to have an equal amount if the hotdog package contains 10 hotdogs, and the hotdog bun package contains 12 buns.

Exercise $\PageIndex{3}$:

Using Euclidean Algorithm, find the gcd of 1716 and 1260, and the LCM of 1716 and 1260.

Exercise $\PageIndex{4}$:

Use the Euclidean algorithm to find $\gcd (270, 504).$. Find integers $x$ and $y$ such that $\gcd (270, 504) =270 x+504 y.$
Use the Euclidean algorithm to find $\gcd (-270, 504).$, Find integers $x$ and $y$ such that $\gcd (-270, 504) =-270 x+504 y.$

Exercise $\PageIndex{5}$:

Suppose $a$ and $b$ are relatively prime integers and $c$ is an integer such that $a|c$ and $b|c.$ Prove that $ab|c.$

Exercise $\PageIndex{6}$:

Suppose $a$ and $b$ are relatively prime integers and $c$ is an integer such that $a|bc$. Prove that $a|c.$

Exercise $\PageIndex{7}$:

Let $a$ and $b$ be non-zero integers with least common multiple $l$. Let $m$ be any common multiple of $a$ and $b$. Prove that $l|m.$
Prove that if $a, b$ and $c$ are natural numbers, $\gcd(a, c)=1$ and $b \mid c$, then $\gcd(a, b)=1$.
Suppose $a$ and $c$ are relatively prime integers and $b$ is an integer such that $b|c.$ Prove that $gcd(a, b)=1.$

Exercise $\PageIndex{8}$:

Prove that for any positive integer $k$, $7k+5$ and $4k+3$ are relatively prime.

Exercise $\PageIndex{9}$:

Let $a$, $b$,$c$ and $d$ be non-zero integers. Then determine whether the following statements are true or false. Justify your answers.

1. If $\gcd(a,b)= \gcd(a,c)$, then $b=c$.

2. If $lcm(a,b)= lcm(a,c)$, then $b=c$.

3. $lcm(\gcd(a,b),c)=\gcd(lcm(a,b),c)$.

4. If $\gcd(a,b)= \gcd(c,d)$ and $lcm(a,b)=lcm(c,d)$, then $a=b$ and $c=d$.

5. $ \gcd(c,a+b)=\gcd(c,a)+gcd(c,b)$.

6. $ \gcd(c,ab)=\gcd(c,a) \gcd(c,b)$.

7. $\gcd(\gcd(a,b),c)=\gcd(a,\gcd(b,c))$.

Exercise $\PageIndex{10}$:

Let $a$, $b$ and $c$ be non-zero integers. Prove the following statements:

1. $\gcd(a,b)=\gcd(a, b-a)=\gcd(a,a+b)=\gcd(\pm a,\pm b)$.

2. $\gcd(a,b)=\gcd(a,b-ac)$.

3. $\gcd(ac,bc)=\gcd(a,b) |c|$

Exercise $\PageIndex{11}$:

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

16. $3x \equiv 1( \, mod\, 6)$.

17. $16x \equiv 11( \, mod\, 35)$.

18. $2x \equiv 13( \, mod\, 13).$

Exercise $\PageIndex{12}$

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

Exercise $\PageIndex{1}$

1. Solve the system
$
\begin{cases}
x\equiv2\pmod5,\\
x\equiv3\pmod7.
\end{cases}
$

Give the complete solution as a single congruence.

2. Solve
$
\begin{cases}
x\equiv2\pmod3,\\
x\equiv3\pmod5,\\
x\equiv2\pmod7.
\end{cases}
$

Find the smallest positive solution and express the complete set of solutions
as a congruence.

Search

Text Color

Text Size

Margin Size

Font Type

Exercise \(\PageIndex{1}\):

Exercise \(\PageIndex{2}\):

Exercise \(\PageIndex{3}\):

Exercise \(\PageIndex{4}\):

Exercise \(\PageIndex{5}\):

Exercise \(\PageIndex{6}\):

Exercise \(\PageIndex{7}\):

Exercise \(\PageIndex{8}\):

Exercise \(\PageIndex{9}\):

Exercise \(\PageIndex{10}\):

Exercise \(\PageIndex{11}\):

Exercise \(\PageIndex{12}\)

Exercise \(\PageIndex{1}\)