2.E: Exercises
( \newcommand{\kernel}{\mathrm{null}\,}\)
Exercise 2.E.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.
- Define a relation R on A=Z by aRb if and only if 4∣(3a+b).
- Define a relation R on A=Z by aRb if and only if 3∣(a2−b2).
- Let A=R, If a.b∈R, define aRb if and only if a−b∈Z.
- Define a relation R on the set Z×Z by: (a,b)R(c,d) if and only if ac=bd.
- Define a relation R on Z by: aRb if and only if 5∣2a+3b.
- Define a relation R on Z by: aRb if and only if 2∣a2+b.
- Answer
-
1. i. We shall show that R is reflexive on A.
Proof:
Let a∈Z.
Since 3a+a=4a, 4∣(3a+a). Thus aRa.
Hence is reflexive on Z .
ii. We shall show that R is symmetric on A.
Proof:
Let a,b∈Z, such that aRb.
Then 4∣(3a+b). Thus 3a+b=4m, for some integer m.
We shall show that bRa. That means 4∣(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∈Z,4∣(3a+b).
Hence R is symmetric on Z.
iii. We shall show that R is not antisymmetric on Z.
Counterexample:
Choose a=4 and b=0 .
Then 3(4)+0=12 and 4∣12, so 4∣3a+b. Also 3(0)+4=12 and 4∣4, so 4∣3b+a.
However, 4≠0 , so a≠b
Hence R is not antisymmetric on Z.
iv. We shall show that R is transitive on Z.
Proof:
Let a,b,c∈Z, such that aRb and bRc. That means 4∣3a+b and 4∣3b+c.
Since 4∣3a+b, 3a+b=4m for some integer m , and Since 4∣3b+c, 3b+c=4n, for some integer n.
We shall show that aRc. That is 4∣3a+c.
Consider (3a+b)+(3b+c)=4m+4n⟹3a+c+4a+4b=4m+4n⟹3a+c=4(m+n−a−b).
Since m+n−a−b∈Z, 4∣3b+c. Thus, aRc.
Hence R is transitive on Z.
v. Since R is reflexive, symmetric and reflexive, aRb is an equivalence relation on Z.
Equivalence classes:
[0]={x∈Z∣x∼0}={x∈Z∣4∣(3x+0)}={x∈Z∣4m=3x,for some integer m}={0,±4,±8,⋯}.
[1]={x∈Z∣x∼1}={x∈Z∣4∣(3x+1)}={x∈Z∣4m=3x+1,for some integer m}={⋯,−3,1,5,⋯}.
[2]={x∈Z∣x∼2}={x∈Z∣4∣(3x+2)}={x∈Z∣4m=3x+2,for some integer m}={⋯,−2,2,6,⋯}.
[3]={x∈Z∣x∼3}={x∈Z∣4∣(3x+3)}={x∈Z∣4m=3x+3,for some integer m}={⋯,−1,3,7,⋯}.
6.
Proof of Reflexivity:
Let a∈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:
Since
,
.
Thus
.
Since a(a+1) is even,
is even.
Proof of Transitivity:
Having shown that
is reflexive, symmetric and transitive on
,
is an equivalence relation on
.◻
Exercise 2.E.2: Divides
Let a,b,c,d∈Z+.
- If a|b and a|c, is it necessarily true that a|(b+c)?
- If a|(b+c), is it necessarily true that a|b and a|c?
- If a|bc, is it necessarily true that a|b and a|c?
- If (a+b)|c, is it necessarily true that a|c and b|c?
- If a|c and b|c, is it necessarily true that (a+b)|c?
- If a3|b4, is it necessarily true that a|b.
- If a|b, is it necessarily true that a3∣b5?
- If c|a and d|b, is it necessarily true that cd|ab.
Exercise 2.E.3: Divisibility Rules
- Find all possible values for the missing digit if 12345X51234 is divisible by 3.
- Using divisibility tests, check if the number 355581 is divisible by 7
- 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,or9.
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 2.E.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|(a2+b2+c2+d2).
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 2.E.5: Middle digit
- In a 113-digit multiple of 13, the first 56 digits are all 5s and the last 56 digits are all 8s. What is the middle digit?
- In a 113-digit multiple of 7, the first 56 digits are all 8s and the last 56 digits are all 1s. What is the middle digit?
Exercise 2.E.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.
- If a|b then b|a.
- If a|bc then a|b and a|c.
- If a|b and a|c then a|bc.
- If a|b and a|c then a|(b+c) and a|(b−c).
- If a|(b+c) and a|(b−c) then a|b and a|c.
- If a|b and a|c then a|(b+c) and a|(2b+c).
- If a|(b+c) and a|(2b+c) then a|b and a|c
Exercise 2.E.7: Induction
Prove that for all integers n≥1,52n−25n is divisible by 7.
- Answer
-
use induction to prove the statement.
Exercise 2.E.8: Induction or by cases
Prove that for all integer n≥1,6 divides n3−n.
- Answer
-
use induction to prove the statement.
Exercise 2.E.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 2.E.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 2.E.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 2.E.12: Inequality
Solve 0<199m−335<100 for all integers m.
- Answer
-
m=2.