# 2.E: Exercises

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

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

$$\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{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#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}$$: Equivalence relation

Determine whether or not each of the following binary relations $$R$$ on the given set $$A$$ is reflexive, symmetric,
antisymmetric, or transitive. If a relation has a certain property, prove this is so; otherwise, provide a counterexample
to show that it does not. If $$R$$ is an equivalence relation, describe the equivalence classes of $$A$$.

1. Define a relation $$R$$ on $$A={\mathbb Z}$$ by $$a \,R\, b$$ if and only if $$4 \mid (3a+b).$$
2. Define a relation $$R$$ on $$A={\mathbb Z}$$ by $$a \, R \, b$$ if and only if $$3 \mid (a^2-b^2).$$
3. Let $$A=\mathbb{R}$$, If $$a.b \in \mathbb{R}$$, define $$a \, R \, b$$ if and only if $$a-b \in \mathbb{Z}.$$
4. Define a relation $$R$$ on the set $${\mathbb Z} \times{\mathbb Z}$$ by: $$(a,b)\, R \,(c,d) \mbox{ if and only if } ac=bd.$$
5. Define a relation $$R$$ on $${\mathbb Z}$$ by: $$a R b$$ if and only if $$5 \mid 2a+3b.$$
6. Define a relation $$R$$ on $${\mathbb Z}$$ by: $$a R b$$ if and only if $$2 \mid a^2+b.$$

1.  i.    We shall show that $$R$$  is reflexive on $$A$$.

Proof:

Let $$a \in {\mathbb Z}.$$

Since $$3a+a=4a$$, $$4 \mid (3a+a).$$ Thus $$a R a$$.

Hence  is reflexive on $${\mathbb Z}$$ .

ii.    We shall show that   $$R$$  is symmetric on $$A$$.

Proof:

Let $$a, b \in {\mathbb Z}$$, such that $$a R b$$.

Then $$4 \mid (3a+b)$$. Thus $$3a+b=4m$$, for some  integer $$m.$$

We shall show that  $$b R a$$. That means $$4 \mid (3a+b).$$

Consider  $$3a+b=4m$$

$$(3a+b)+(3b+a)=4m +(3b+a)$$

$$(4b+4a)=4m +(3b+a)$$

$$3b+a=-4m +4b+4a=4(-m+b+a).$$

Since $$m+b+a \in {\mathbb Z}, 4 \mid (3a+b).$$

Hence $$R$$ is symmetric on $${\mathbb Z}.$$

iii.    We shall show that $$R$$ is not antisymmetric on $${\mathbb Z}.$$

Counterexample:

Choose $$a=4$$ and $$b=0$$  .

Then $$3(4)+0=12$$ and  $$4 \mid 12$$, so $$4 \mid 3a+b.$$ Also $$3(0)+4=12$$ and  $$4 \mid 4$$, so $$4 \mid 3b+a.$$

However, $$4 \ne 0$$ , so $$a \ne b$$

Hence $$R$$ is not antisymmetric on $${\mathbb Z}.$$

iv.    We shall show that  $$R$$  is transitive on  $${\mathbb Z}.$$

Proof:

Let  $$a, b, c \in {\mathbb Z}$$, such that $$a R b$$ and $$b R c$$. That means $$4 \mid 3a+b$$ and  $$4 \mid 3b+c$$.

Since $$4 \mid 3a+b$$,  $$3a+b =4 m$$ for some integer $$m$$ , and Since $$4 \mid 3b+c$$,  $$3b+c =4 n$$, for some  integer $$n$$.

We shall show that $$a R c$$. That is $$4 \mid 3a+c.$$

Consider  $$(3a+b)+(3b+c) =4 m+4n \implies 3a+c+4a+4b=4m+4n \implies 3a+c=4(m+n-a-b).$$

Since $$m+n-a-b \in {\mathbb Z}$$, $$4 \mid 3b+c$$. Thus, $$a R c$$.

Hence $$R$$ is transitive on $${\mathbb Z}.$$

v.     Since $$R$$ is  reflexive, symmetric and reflexive, $$a R b$$ is an equivalence relation on $${\mathbb Z}.$$

Equivalence classes:

$$[0]=\{ x \in {\mathbb Z} \mid x \sim 0 \} = \{ x \in {\mathbb Z} \mid 4 \mid (3x+0) \}= \{ x \in {\mathbb Z} \mid 4m=3x, \text{for some integer } m \}=\{ 0, \pm 4, \pm 8, \cdots \}.$$

$$[1]=\{ x \in {\mathbb Z} \mid x \sim 1 \} = \{ x \in {\mathbb Z} \mid 4 \mid (3x+1) \}= \{ x \in {\mathbb Z} \mid 4m=3x+1, \text{for some integer } m\} =\{ \cdots, -3, 1, 5, \cdots \}.$$

$$[2]=\{ x \in {\mathbb Z} \mid x \sim 2 \} = \{ x \in {\mathbb Z} \mid 4 \mid (3x+2) \}= \{ x \in {\mathbb Z} \mid 4m=3x+2, \text{for some integer } m\} =\{ \cdots, -2, 2, 6, \cdots \}.$$

$$[3]=\{ x \in {\mathbb Z} \mid x \sim 3 \} = \{ x \in {\mathbb Z} \mid 4 \mid (3x+3) \}= \{ x \in {\mathbb Z} \mid 4m=3x+3, \text{for some integer } m\} =\{ \cdots, -1, 3, 7, \cdots \}.$$

6.

Proof of Reflexivity:

Let .

We shall show that .

We can show this directly or using cases:

Directly:

Since , and are consecutive integers,

is even. Thus  is reflexive on .

Proof of Symmetry:

Let s.t. .

We will show that .

Since

.

Thus

.

Since a(a+1) is even,

is even.

Thus is symmetric on .

Proof of Transitivity:

Let s.t. and .

We will show that .

Consider and .

Further, consider that .

Since is reflexive on

Thus .

Thus is transitive on .

Having shown that is reflexive, symmetric and transitive on , is an equivalence relation on .◻

Let , then .

Case :

.

Case :

.

## Exercise $$\PageIndex{2}$$: Divides

Let $$a, b,c, d \in \bf Z_+.$$

1. If $$a|b$$ and $$a|c$$, is it necessarily true that $$a|(b + c)?$$
2. If $$a|(b + c)$$, is it necessarily true that $$a|b$$ and $$a|c$$?
3. If $$a|bc$$, is it necessarily true that $$a|b$$ and $$a|c$$?
4. If $$(a+b)|c$$, is it necessarily true that $$a|c$$ and $$b|c$$?
5. If $$a|c$$ and $$b|c$$, is it necessarily true that $$(a+b)|c?$$
6. If $$a^3|b^4$$, is it necessarily true that $$a|b.$$
7. If $$a|b$$, is it necessarily true that $$a^3 \mid b^5?$$
8. If $$c|a$$ and $$d|b$$, is it necessarily true that $$cd|ab$$.

## Exercise $$\PageIndex{3}$$: Divisibility Rules

1. Find all possible values for the missing digit if $$12345X51234$$ is divisible by $$3.$$
2. Using divisibility tests, check if the number $$355581$$ is divisible by $$7$$
3. Using divisibility tests, check if the number $$824112284$$ is divisible by $$5, 4,$$ and $$8.$$

1. An integer (q) is divisible by 3 iff i=0ndiis divisible by 3, where di is the ith digit of q. Thus, the sum of the digits of 12345X51234 must be divisible by 3.

Simplifying, 3 | (30 + X).

Since 3 | 30, 3 must divide X in order to satisfy 3 |12345X51234.

Thus $$X ∈ { 0, 3, 6, or 9}.$$

2.

An integer (q) is divisible by 7 iff 7 | (a - 2b), where b is the last digit of q and a is the remaining digits.

Step 1: a = 35558, b = 1.

Thus, a - 2b = 35556.

Step 2: a = 3555, b = 6.

Thus, a - 2b = 3543.

Note at this point it is clear that 7 ∤ 355581, since 7 ∤ 3543. However, for practice, we will continue on.

Step 3: a = 354, b = 3.

Thus, a - 2b = 348.

Step 4: a = 34, b = 8.

Thus a - 2b = 18.

Since 7 ∤ 18, 7 ∤ 355581.

3.

An integer (q), is divisible by 5 iff its last digits ∈ {0, 5}.

Since 4 ∉ {0, 5}, 5 ∤ 824112284.

An integer (q) is divisible by 8 iff q’s last three digits are divisible by 8.

Since 8 ∤ 284, 8 ∤ 824112284.

An integer (q) is divisible by 4 iff q’s last two digits are divisible by 4.

Since 4 ∣ 84, 4 ∣ 824112284.

## Exercise $$\PageIndex{4}$$: Divisiblity

1. Let $$a$$ be a positive integer such that $$3|(a+1)$$. Show that $$3|(7a+4)$$.

2. Let $$a$$ and $$b$$ be positive integers such that $$7|(a+2b-2)$$ and $$7|(b-9).$$ Prove that $$7|(a+b).$$

3. Let $$a$$, $$b$$, $$c$$ and $$d$$ be positive integers such that $$4|(abc+d)$$, $$4|(adc+b)$$, $$4|(abd+c)$$ and $$4|(bcd+a)$$. Prove that $$4|(a^2+b^2+c^2+d^2).$$

4. Let $$a$$, $$b$$, $$c$$ and $$d$$ be positive integers such that $$ad-bc >1$$. Show that at least of these four integers is not divisible by $$ad-bc$$.

## Exercise $$\PageIndex{5}$$: Middle digit

1. In a $$113$$-digit multiple of $$13$$, the first $$56$$ digits are all $$5$$s and the last $$56$$ digits are all $$8$$s. What is the middle digit?
2. In a $$113$$-digit multiple of $$7$$, the first $$56$$ digits are all $$8$$s and the last $$56$$ digits are all $$1$$s. What is the middle digit?

## Exercise $$\PageIndex{6}$$: True or False

Prove the statements that are true and give counterexamples to disprove those that are false.
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$$

## Exercise $$\PageIndex{7}$$: Induction

Prove that for all integers $$n\geq 1, \,5^{2n}-2^{5n}$$ is divisible by $$7.$$

use induction to prove the statement.

## Exercise $$\PageIndex{8}$$: Induction or by cases

Prove that for all integer $$n\geq 1, \,6$$ divides $$n^3-n.$$

use induction to prove the statement.

## Exercise $$\PageIndex{9}$$: True or false

Which of the following statements are true. Prove the statement(s) that are true and give a counterexample for the statement(s) that are false.

If $$a,b,c$$ and $$d$$ are integers such that $$a < b$$ and $$c < d,$$ then $$ac < bd$$.

If $$a,b,c$$ and $$d$$ are integers such that $$a < 0 < b$$ and $$c < 0 < d,$$ then $$ac < bd$$.

If $$a,b,c$$ and $$d$$ are integers such that $$0 < a < b$$ and $$c < 0 < d,$$ then $$ac < bd$$.

If $$a,b,c$$ and $$d$$ are integers such that $$a < b$$ and $$c < d,$$ then $$a-d < b-c.$$

TBD

## Exercise $$\PageIndex{10}$$ Tip?

There are 9 waiters and 1 busboy working at a restaurant. The tips are always in whole number of dollars. At the end of the day, the waiters share the tips equally among themselves as far as possible, each getting a whole number of dollars. The busboy gets what is left. How much does he get on a day when the total amount of the tips is $980. Answer 980 (mod 9) ≡ 8 (mod 9), thus, the busboy would receive$ 8 when the total tip for the day was \$ 980.

## Exercise $$\PageIndex{11}$$ Day of the week

March 1 on some year is a Friday. On what day of the week will Christmas be that year?

Christmas falls on December 25th in any given year. The number of days from March 1 till Christmas (430)+(631) -7=299. Note: We consider March 1 as day zero and there are 6 days from December 25 to December 31, thus seven days must be subtracted from the total number of days. Since 299 = 7(42) + 5 and March 1 is a Friday, Christmas will fall five days after Friday, which is a Wednesday. Thus, if in a given year, March 1 is a Friday, Christmas will fall on a Wednesday that year.

## Exercise $$\PageIndex{12}$$: Inequality

Solve $$0<199m-335<100$$ for all integers $$m$$.

$$m=2$$.