Question 1

Let $A = \{ 2,3,4,5,6,7,8 \}$ and define a relation $R$ on $A$ as follows: for all $x , y \in A$,
$x R y \Leftrightarrow 3 \mid ( x - y ) .$
(a) Is $7 R 2$ ? Is $13 R 4$ ? Is $2 R 5$ ? Is $8 R 8$ ?
(b) Draw the directed graph of $R$.

Accepted Answer

a. $7 R 2$ because $7 - 2 = 5$ and $3 \nmid 5 ; \quad 13 R 4$ because $13 - 4 = 9$ and $3 \mid 9$;
$2 R 5$ because $2 - 5 = - 3$ and $3 \mid - 3 ; \quad 8 R 8$ because $8 - 8 = 0$ and $3 \mid 0$.
b. Draw the directed graph of $R$.

Question 2

An RSA cipher has public key pq = 65 and e = 7.
(a) Translate the message YES into its numeric equivalent, and use the formula $C = M ^ { e }$  (mod pq) to encrypt the message.
(b) Decrypt the ciphertext 50 16 and translate the result into letters of the alphabet to discover the message.

Accepted Answer

a. The numeric equivalents of $\mathrm { Y } , \mathrm { E }$, and $\mathrm { S }$ are 25,5 , and 19 . So to encrypt these letters, the following quantities must be computed: $25 ^ { 7 } \bmod 65,5 ^ { 7 } \bmod 65$, and $19 ^ { 7 } \bmod 65$.
Y: $25 ^ { 7 } \bmod 65 = 25 \quad$ E: $5 ^ { 7 } \bmod 65 = 60 \quad$ S: $19 ^ { 7 } \bmod 65 = 59$
Therefore, the encrypted message is 25 60 59 .
b. Because $p q = 65 = 5 \cdot 13$ and because both 5 and 13 are prime numbers, $( p - 1 ) ( q - 1 ) =$ $4 \cdot 12 = 48$. The decryption key $d$ is the solution to the congruence $7 d \equiv 1 ( \bmod 48 )$. Using either trial-and-error or the solution to problem 18 gives that $d = 7$. So to decrypt the message, the following quantities must be computed: $50 ^ { 7 } \bmod 65$, and $41 ^ { 7 } \bmod 65$.
Since $50 ^ { 7 } \bmod 65 = 15$ and $16 ^ { 7 } \bmod 65 = 16$, and since 15 corresponds to $\mathrm { N }$ and 16 corresponds to $\mathrm { O }$ the decrypted message is NO .

Question 3

Find a positive inverse for 7 modulo 48. (That is, ﬁnd a positive integer n such that 7n ≡ 1 (mod 48).

Accepted Answer

Step 1: $48 = 7 \cdot 6 + 6$, and so $6 = 48 - 7 \cdot 6$.
Step 2: $7 = 6 \cdot 1 + 1$, and so $1 = 7 - 6 \cdot 1$.
Step 3: $1 = 1 \cdot 0 + 1$, and so $\operatorname { gcd } ( 48,7 ) = 1$.
Substitute back through steps $2 - 1$ :
$1 = 7 - ( 6 \cdot 1 ) = 7 - 6 = 7 - ( 48 - 7 \cdot 6 ) = 7 \cdot 7 - 48 \text {. }$
Thus $7 \cdot 7 \equiv 1 ( \bmod 48 )$, and so 7 is an inverse for 7 modulo 48 .

Question 4

Let $B = \{ 0,1,2,3 \}$ and define a relation $U$ on $B$ by
$$U = \{ ( 0,2 ) , ( 0,3 ) , ( 2,0 ) , ( 2,1 ) \}$$
Is $U$ transitive? Justify your answer.

Accepted Answer

The answer of Let $B = \{ 0,1,2,3 \}$ and...

Question 5

Let S be the set of all strings of 0's and 1's of length 3. Deﬁne a relation R on S as follows: for all strings s and t in S,

(a) Prove that R is an equivalence relation on S.
(b) Find the distinct equivalence classes of R.

Accepted Answer

The answer of Let S be the set of all...

Question 6

Let R be the relation deﬁned on the set of all integers Z as follows: for all integers m and n, $$m R n \Longleftrightarrow m - n \text { is divisible by } 5 \text {. }$$ 
(a) Is R reﬂexive? Prove or give a counterexample.
(b) Is R symmetric? Prove or give a counterexample.
(c) Is R transitive? Prove or give a counterexample.

Accepted Answer

The answer of Let R be the relation deﬁned on...

Question 7

Define a relation $R$ from $\{ a , b , c \}$ to $\{ u , v \}$ as follows: $R = \{ ( a , v ) , ( b , u ) \}$.
(a) Draw an arrow diagram for $R$.
(b) Is $R$ a function? Why or why not?

Accepted Answer

The answer of Define a relation $R$ from \(\{ a...

Question 8

Deﬁne a relation S on the set of positive integers as follows: for all positive integers m and n, $$m S n \Leftrightarrow m \mid n$$ 
(a) Is S reﬂexive? Justify your answer.
(b) Is S symmetric? Justify your answer.

Accepted Answer

The answer of Deﬁne a relation S on the set...

Question 9

$\text { Use the fact that } 29 = 16 + 8 + 4 + 1 \text { to compute } 18 ^ { 29 } \bmod 65 \text {. }$

Accepted Answer

The answer of \(\text { Use the fact that }...

Question 10

Let $A = \{ 0,1,2,3 \}$ and define a relation $R$ on $A$ as follows: $R = \{ ( 0,2 ) , ( 0,3 ) , ( 2,0 ) , ( 2,1 ) \}$.
(a) Draw the directed graph of $R$.
(b) Is $R$ reflexive? Explain.
(c) Is $R$ symmetric? Explain.
(d) Is $R$ transitive? Explain.

Accepted Answer

The answer of Let $A = \{ 0,1,2,3 \}$ and...

Question 11

Let A = {1, 2, 3, 4}. The following relation R is an equivalence relation on A:
R = {(1, 1), (1, 3), (1, 4), (2, 2), (3, 1), (3, 3), (3, 4), (4, 1), (4, 3), (4, 4)}.
(a) Draw the directed graph of R.
(b) Find the distinct equivalence classes of R.

Accepted Answer

The answer of Let A = {1, 2, 3, 4}....

Question 12

Define a relation $R$ from $\{ a , b , c \}$ to $\{ u , v \}$ as follows: $R = \{ ( a , u ) , ( b , u ) , ( c , v ) \}$.
(a) Draw an arrow diagram for $R$.
(b) Is $R$ a function? Why or why not?

Accepted Answer

The answer of Define a relation $R$ from \(\{ a...

Question 13

Define a relation $T$ from $\mathbf { R }$ to $\mathbf { R }$ as follows: for all $( x , y ) \in \mathbf { R } \times \mathbf { R } , x T y \Leftrightarrow y > x + 1$.
(a) Is $( 1,0 ) \in T ?$ Is $( 0,1 ) \in T ?$ Is $( - 2,5 ) \in T ?$ Is $( - 3 , - 4 ) \in T ?$
(b) Sketch the graph of $T$ in the Cartesian plane.

Accepted Answer

The answer of Define a relation $T$ from \(\mathbf {...

Question 14

Prove directly from the definition of congruence modulo $n$ that if $a , c$, and $n$ are integers, $n > 1$, and $a \equiv c ( \bmod n )$, then $a ^ { 3 } \equiv c ^ { 3 } ( \bmod n )$.

Accepted Answer

The answer of Prove directly from the definition of congruence...

Question 15

Define a relation $R$ from $\{ a , b , c \}$ to $\{ u , v \}$ as follows: $R = \{ ( a , v ) , ( b , u ) , ( b , v ) , ( c , u ) \}$.
(a) Draw an arrow diagram for $R$.
(b) Is $R$ a function? Why or why not?

Accepted Answer

The answer of Define a relation $R$ from \(\{ a...

Question 16

Define a relation $R$ on the set $\{ 1,2,3,4 \}$ as follows:
$$R = \{ ( 1,4 ) , ( 2,3 ) , ( 2,4 ) , ( 4,1 ) , ( 2,1 ) , ( 1,2 ) , ( 3,2 ) \}$$
(a) Is $R$ symmetric? Justify your answer.
(b) Is $R$ transitive? Justify your answer.

Accepted Answer

The answer of Define a relation $R$ on the set...

Question 17

Define a relation $T$ on $\mathbf { R }$ as follows: for all $x$ and $y$ in $\mathbf { R } , x T y$ if and only if $x ^ { 2 } = y ^ { 2 }$. Then $T$ is an equivalence relation on $\mathbf { R }$. 
(a) Prove that T is an equivalence relation on R.
(b) Find the distinct equivalence classes of T.

Accepted Answer

The answer of Define a relation $T$ on \(\mathbf {...

Question 18

Let $B = \{ 0,1,2,3 \}$ and define a relation $U$ on $B$ by
$$U = \{ ( 0,2 ) , ( 0,3 ) , ( 1,2 ) \} .$$ 
Is U transitive? Justify your answer.

Accepted Answer

The answer of Let $B = \{ 0,1,2,3 \}$ and...

Question 19

Let $A = \{ 3,4,5,6,7 \}$ and define a relation $R$ on $A$ as follows: for all $x , y \in A$,
$$x R y \Leftrightarrow 2 \mid ( x - y ) .$$ 
(a) Is 6 R 3? Is 4 R 6?
(b) Draw the directed graph of R.

Accepted Answer

The answer of Let $A = \{ 3,4,5,6,7 \}$ and...

Quiz 8: Relations

Let $A = \{ 2,3,4,5,6,7,8 \}$ and define a relation $R$ on $A$ as follows: for all $x , y \in A$ , $x R y \Leftrightarrow 3 \mid ( x - y ) .$ (a) Is $7 R 2$ ? Is $13 R 4$ ? Is $2 R 5$ ? Is $8 R 8$ ? (b) Draw the directed graph of $R$ .

An RSA cipher has public key pq = 65 and e = 7. (a) Translate the message YES into its numeric equivalent, and use the formula $C = M ^ { e }$ (mod pq) to encrypt the message. (b) Decrypt the ciphertext 50 16 and translate the result into letters of the alphabet to discover the message.

Find a positive inverse for 7 modulo 48. (That is, ﬁnd a positive integer n such that 7n ≡ 1 (mod 48).

Let $B = \{ 0,1,2,3 \}$ and define a relation $U$ on $B$ by $U = \{ ( 0,2 ) , ( 0,3 ) , ( 2,0 ) , ( 2,1 ) \}$ Is $U$ transitive? Justify your answer.

Let S be the set of all strings of 0's and 1's of length 3. Deﬁne a relation R on S as follows: for all strings s and t in S, (a) Prove that R is an equivalence relation on S. (b) Find the distinct equivalence classes of R.

Define a relation $R$ from $\{ a , b , c \}$ to $\{ u , v \}$ as follows: $R = \{ ( a , v ) , ( b , u ) \}$ . (a) Draw an arrow diagram for $R$ . (b) Is $R$ a function? Why or why not?

Deﬁne a relation S on the set of positive integers as follows: for all positive integers m and n, $m S n \Leftrightarrow m \mid n$ (a) Is S reﬂexive? Justify your answer. (b) Is S symmetric? Justify your answer.

$\text { Use the fact that } 29 = 16 + 8 + 4 + 1 \text { to compute } 18 ^ { 29 } \bmod 65 \text {. }$

Let $A = \{ 0,1,2,3 \}$ and define a relation $R$ on $A$ as follows: $R = \{ ( 0,2 ) , ( 0,3 ) , ( 2,0 ) , ( 2,1 ) \}$ . (a) Draw the directed graph of $R$ . (b) Is $R$ reflexive? Explain. (c) Is $R$ symmetric? Explain. (d) Is $R$ transitive? Explain.

Let A = {1, 2, 3, 4}. The following relation R is an equivalence relation on A: R = {(1, 1), (1, 3), (1, 4), (2, 2), (3, 1), (3, 3), (3, 4), (4, 1), (4, 3), (4, 4)}. (a) Draw the directed graph of R. (b) Find the distinct equivalence classes of R.

Define a relation $R$ from $\{ a , b , c \}$ to $\{ u , v \}$ as follows: $R = \{ ( a , u ) , ( b , u ) , ( c , v ) \}$ . (a) Draw an arrow diagram for $R$ . (b) Is $R$ a function? Why or why not?

Prove directly from the definition of congruence modulo $n$ that if $a , c$ , and $n$ are integers, $n > 1$ , and $a \equiv c ( \bmod n )$ , then $a ^ { 3 } \equiv c ^ { 3 } ( \bmod n )$ .

Define a relation $R$ from $\{ a , b , c \}$ to $\{ u , v \}$ as follows: $R = \{ ( a , v ) , ( b , u ) , ( b , v ) , ( c , u ) \}$ . (a) Draw an arrow diagram for $R$ . (b) Is $R$ a function? Why or why not?

Define a relation $R$ on the set $\{ 1,2,3,4 \}$ as follows: $R = \{ ( 1,4 ) , ( 2,3 ) , ( 2,4 ) , ( 4,1 ) , ( 2,1 ) , ( 1,2 ) , ( 3,2 ) \}$ (a) Is $R$ symmetric? Justify your answer. (b) Is $R$ transitive? Justify your answer.

Define a relation $T$ on $\mathbf { R }$ as follows: for all $x$ and $y$ in $\mathbf { R } , x T y$ if and only if $x ^ { 2 } = y ^ { 2 }$ . Then $T$ is an equivalence relation on $\mathbf { R }$ . (a) Prove that T is an equivalence relation on R. (b) Find the distinct equivalence classes of T.

Let $B = \{ 0,1,2,3 \}$ and define a relation $U$ on $B$ by $U = \{ ( 0,2 ) , ( 0,3 ) , ( 1,2 ) \} .$ Is U transitive? Justify your answer.

Let $A = \{ 3,4,5,6,7 \}$ and define a relation $R$ on $A$ as follows: for all $x , y \in A$ , $x R y \Leftrightarrow 2 \mid ( x - y ) .$ (a) Is 6 R 3? Is 4 R 6? (b) Draw the directed graph of R.

Quiz 8: Relations

An RSA cipher has public key pq = 65 and e = 7. (a) Translate the message YES into its numeric equivalent, and use the formula C=MeC = M ^ { e }C=Me (mod pq) to encrypt the message. (b) Decrypt the ciphertext 50 16 and translate the result into letters of the alphabet to discover the message.

Find a positive inverse for 7 modulo 48. (That is, ﬁnd a positive integer n such that 7n ≡ 1 (mod 48).

Let B={0,1,2,3}B = \{ 0,1,2,3 \}B={0,1,2,3} and define a relation UUU on BBB by U={(0,2),(0,3),(2,0),(2,1)}U = \{ ( 0,2 ) , ( 0,3 ) , ( 2,0 ) , ( 2,1 ) \}U={(0,2),(0,3),(2,0),(2,1)} Is UUU transitive? Justify your answer.

Let S be the set of all strings of 0's and 1's of length 3. Deﬁne a relation R on S as follows: for all strings s and t in S, (a) Prove that R is an equivalence relation on S. (b) Find the distinct equivalence classes of R.

Define a relation RRR from {a,b,c}\{ a , b , c \}{a,b,c} to {u,v}\{ u , v \}{u,v} as follows: R={(a,v),(b,u)}R = \{ ( a , v ) , ( b , u ) \}R={(a,v),(b,u)} . (a) Draw an arrow diagram for RRR . (b) Is RRR a function? Why or why not?

Deﬁne a relation S on the set of positive integers as follows: for all positive integers m and n, mSn⇔m∣nm S n \Leftrightarrow m \mid nmSn⇔m∣n (a) Is S reﬂexive? Justify your answer. (b) Is S symmetric? Justify your answer.

Use the fact that 29=16+8+4+1 to compute 1829 mod 65. \text { Use the fact that } 29 = 16 + 8 + 4 + 1 \text { to compute } 18 ^ { 29 } \bmod 65 \text {. } Use the fact that 29=16+8+4+1 to compute 1829mod65.

Let A = {1, 2, 3, 4}. The following relation R is an equivalence relation on A: R = {(1, 1), (1, 3), (1, 4), (2, 2), (3, 1), (3, 3), (3, 4), (4, 1), (4, 3), (4, 4)}. (a) Draw the directed graph of R. (b) Find the distinct equivalence classes of R.

Define a relation RRR from {a,b,c}\{ a , b , c \}{a,b,c} to {u,v}\{ u , v \}{u,v} as follows: R={(a,u),(b,u),(c,v)}R = \{ ( a , u ) , ( b , u ) , ( c , v ) \}R={(a,u),(b,u),(c,v)} . (a) Draw an arrow diagram for RRR . (b) Is RRR a function? Why or why not?

Prove directly from the definition of congruence modulo nnn that if a,ca , ca,c , and nnn are integers, n>1n > 1n>1 , and a≡c( mod n)a \equiv c ( \bmod n )a≡c(modn) , then a3≡c3( mod n)a ^ { 3 } \equiv c ^ { 3 } ( \bmod n )a3≡c3(modn) .

Define a relation RRR from {a,b,c}\{ a , b , c \}{a,b,c} to {u,v}\{ u , v \}{u,v} as follows: R={(a,v),(b,u),(b,v),(c,u)}R = \{ ( a , v ) , ( b , u ) , ( b , v ) , ( c , u ) \}R={(a,v),(b,u),(b,v),(c,u)} . (a) Draw an arrow diagram for RRR . (b) Is RRR a function? Why or why not?

Let B={0,1,2,3}B = \{ 0,1,2,3 \}B={0,1,2,3} and define a relation UUU on BBB by U={(0,2),(0,3),(1,2)}.U = \{ ( 0,2 ) , ( 0,3 ) , ( 1,2 ) \} .U={(0,2),(0,3),(1,2)}. Is U transitive? Justify your answer.

Let A={3,4,5,6,7}A = \{ 3,4,5,6,7 \}A={3,4,5,6,7} and define a relation RRR on AAA as follows: for all x,y∈Ax , y \in Ax,y∈A , xRy⇔2∣(x−y).x R y \Leftrightarrow 2 \mid ( x - y ) .xRy⇔2∣(x−y). (a) Is 6 R 3? Is 4 R 6? (b) Draw the directed graph of R.

An RSA cipher has public key pq = 65 and e = 7. (a) Translate the message YES into its numeric equivalent, and use the formula $C = M ^ { e }$ (mod pq) to encrypt the message. (b) Decrypt the ciphertext 50 16 and translate the result into letters of the alphabet to discover the message.

Let $B = \{ 0,1,2,3 \}$ and define a relation $U$ on $B$ by $U = \{ ( 0,2 ) , ( 0,3 ) , ( 2,0 ) , ( 2,1 ) \}$ Is $U$ transitive? Justify your answer.

Define a relation $R$ from $\{ a , b , c \}$ to $\{ u , v \}$ as follows: $R = \{ ( a , v ) , ( b , u ) \}$ . (a) Draw an arrow diagram for $R$ . (b) Is $R$ a function? Why or why not?

Deﬁne a relation S on the set of positive integers as follows: for all positive integers m and n, $m S n \Leftrightarrow m \mid n$ (a) Is S reﬂexive? Justify your answer. (b) Is S symmetric? Justify your answer.

$\text { Use the fact that } 29 = 16 + 8 + 4 + 1 \text { to compute } 18 ^ { 29 } \bmod 65 \text {. }$

Define a relation $R$ from $\{ a , b , c \}$ to $\{ u , v \}$ as follows: $R = \{ ( a , u ) , ( b , u ) , ( c , v ) \}$ . (a) Draw an arrow diagram for $R$ . (b) Is $R$ a function? Why or why not?

Prove directly from the definition of congruence modulo $n$ that if $a , c$ , and $n$ are integers, $n > 1$ , and $a \equiv c ( \bmod n )$ , then $a ^ { 3 } \equiv c ^ { 3 } ( \bmod n )$ .

Define a relation $R$ from $\{ a , b , c \}$ to $\{ u , v \}$ as follows: $R = \{ ( a , v ) , ( b , u ) , ( b , v ) , ( c , u ) \}$ . (a) Draw an arrow diagram for $R$ . (b) Is $R$ a function? Why or why not?

Let $B = \{ 0,1,2,3 \}$ and define a relation $U$ on $B$ by $U = \{ ( 0,2 ) , ( 0,3 ) , ( 1,2 ) \} .$ Is U transitive? Justify your answer.

Let $A = \{ 3,4,5,6,7 \}$ and define a relation $R$ on $A$ as follows: for all $x , y \in A$ , $x R y \Leftrightarrow 2 \mid ( x - y ) .$ (a) Is 6 R 3? Is 4 R 6? (b) Draw the directed graph of R.