2.E: Exercises

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

Answer

 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 \(a \in \mathbb{Z}\).

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

Answer

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.

Solution:

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

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

Solution:

 

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

Answer

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

Answer

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

Answer

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?

Answer

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

Answer

\(m=2\).