157 lines
4.9 KiB
Markdown
157 lines
4.9 KiB
Markdown
Page 515
|
|
|
|
**Test Yourself**
|
|
|
|
1. If $R$ is a relation from $A$ to $B$, $x \in A$, and $y \in B$, the notation
|
|
$x R y$ means that ____.
|
|
|
|
$x$ is related to $y$ by $R$
|
|
|
|
2. If $R$ is a relation from $A$ to $B$, $x \in A$, and $y \in B$, the notation
|
|
$x \cancel{R} y$ means that ____.
|
|
|
|
$x$ is not related to $y$ by $R$.
|
|
|
|
3. If $R$ is a relation from $A$ to $B$, $x \in A$, and $y \in B$, the notation
|
|
$(y, x) \in R^{-1}$ if, and only if, ____.
|
|
|
|
$$ (x, y) \in R $$
|
|
|
|
4. A relation on a set $A$ is a relation from ____ to ____.
|
|
|
|
$A$; $A$
|
|
|
|
5. If $R$ is a relation on a set $A$, the directed graph of $R$ has an arrow
|
|
from $x$ to $y$ if, and only if, ____.
|
|
|
|
$x$ is related to $y$ by $R$
|
|
|
|
---
|
|
|
|
Page 526
|
|
|
|
**Test Yourself**
|
|
|
|
1. For a relation $R$ on a set $A$ to be reflexive means that ____.
|
|
|
|
$\forall x \in A, x R x$
|
|
|
|
2. For a relation $R$ on a set $A$ to be symmetric means that ____.
|
|
|
|
$\forall x, y \in A, x R y \to y R x$
|
|
|
|
3. For a relation $R$ on a set $A$ to be transitive means that ____.
|
|
|
|
$\forall x, y, z \in A, (x R y \wedge y R z) \to x R z$
|
|
|
|
4. To show that a relation $R$ on an infinite set $A$ is reflexive, you suppose
|
|
that ____ and you show that ____.
|
|
|
|
$x \in A$; $x R x$
|
|
|
|
5. To show that a relation $R$ on an infinite set $A$ is symmetric, you suppose
|
|
that ____ and you show that ____.
|
|
|
|
$\forall x, y \in A, x R y$; $y R x$
|
|
|
|
6. To show that a relation $R$ on an infinite set $A$ is transitive, you suppose
|
|
that ____ and you show that ____.
|
|
|
|
$\forall x, y, z \in A, x R y \wedge y R z$; $x R z$
|
|
|
|
7. To show that a relation $R$ on a set $A$ is not reflexive, you ____.
|
|
|
|
$\exists x \in A, x \cancel{R} x$
|
|
|
|
8. To show that a relation $R$ on a set $A$ is not symmetric, you ____.
|
|
|
|
$\exists x, y \in A, x R y \to y \cancel{R} x$
|
|
|
|
9. To show that a relation $R$ on a set $A$ is not transitive, you ____.
|
|
|
|
$\exists x, y, z \in A, (x R y \wedge y R z) \to x \cancel{R} z$
|
|
|
|
10. Given a relation $R$ on a set $A$, the transitive closure of $R$ is the
|
|
relation $R^t$ on $A$ that satisfies the following three properties: ____,
|
|
____, and ____.
|
|
|
|
$R^t$ is transitive; $R \subseteq R^t$; if $S$ is any other transitive relation
|
|
that contains $R$, then $R^t \subseteq S$
|
|
|
|
---
|
|
|
|
Page 543
|
|
|
|
**Test Yourself**
|
|
|
|
1. For a relation on a set to be an equivalence relation, it must be ____.
|
|
|
|
reflexive, symmetric, and transitive
|
|
|
|
2. The notation $m \equiv n (\mod d)$ is read "____" and means that ____.
|
|
|
|
$m$ is congruient to $n$ modulo $d$; $d$ divides $m - n$
|
|
|
|
3. Given an equivalence relation $R$ on a set $A$ and given an element $a$ in
|
|
$A$, the equivalence class of $a$ is denoted ____ and is defined to be ____.
|
|
|
|
$[a]$; the set of all elements $x \in A$ such that $x R a$
|
|
|
|
4. If $A$ is a set, $R$ is an equivalence relation on $A$, and $a$ and $b$ are
|
|
elements of $A$, then either $[a] = [b]$ or ____.
|
|
|
|
$[a] \cap [b] = \emptyset$
|
|
|
|
5. If $A$ is a set and $R$ is an equivalence relation on $A$, then the distinct
|
|
equivalence classes of $R$ form ____.
|
|
|
|
a partition of $A$
|
|
|
|
6. Let $A = \mathbb{Z} \times (\mathbb{Z} - \{0\})$, and define a relation $R$
|
|
on $A$ by specifying that for every $(a, b)$ and $(c, d)$ in $A$,
|
|
$(a, b) R (c, d)$ if, and only if, $ad = bc$. Then there is exactly one
|
|
equivalence class of $R$ for each ____.
|
|
|
|
rational number
|
|
|
|
---
|
|
|
|
Page 566
|
|
|
|
**Test Yourself**
|
|
|
|
1. When letters of the alphabet are encrypted using the Caesar cipher, the
|
|
encrypted version of the letter is ____.
|
|
|
|
2. If $a$, $b$, and $n$ are integers with $n > 1$, all of the following are
|
|
different ways to express the fact that $n | (a - b)$: ____, ____, ____,
|
|
____.
|
|
|
|
3. If $a$, $b$, $c$, $d$, $m$, and $n$ are integers with $n > 1$ and if
|
|
$a \equiv c(\mod n)$ and $b \equiv d(\mod n)$, then $a + b \equiv$ ____,
|
|
$a - b \equiv$ ____, $ab \equiv$ ____, and $a^m \equiv$ ____
|
|
|
|
4. If $a$, $n$, and $k$ are positive integers with $n > 1$, an efficient way to
|
|
compute $a^k(\mod n)$ is to write $k$ as a ____ and use the facts about
|
|
computing products and powers modulo $n$.
|
|
|
|
5. To express a greatest common divisor of two integers as a linear combination
|
|
of the integers, use the extended version of the ____ algorithm.
|
|
|
|
6. To find an inverse for a positive integer $a$ modulo an integer $n$ with
|
|
$n > 1$, you express the number $1$ as ____.
|
|
|
|
7. To encrypt a message $M$ using RSA cryptography with public key $pq$ and $e$,
|
|
you use the formula ____, and to decrypt a message $C$, you use the formula
|
|
____, where ____.
|
|
|
|
8. Euclid's lemma says that for all integers $a$, $b$, and $c$ if
|
|
$\text{gcd}(a, c) = 1$ and $a | bc$, then ____.
|
|
|
|
9. Fermat's little theorem says that if $p$ is any prime number and $a$ is any
|
|
integer such that $p | a$, then ____.
|
|
|
|
10. The crux of the proof that the RSA cipher works is that if (1) $p$ and $q$
|
|
are distinct large prime numbers, (2) $M < pq$, (3) $M$ is relatively prime
|
|
to $pq$, (4) $e$ is relatively prime to $(p - 1)(q - 1)$, and (5) $d$ is a
|
|
positive inverse for $e$ modulo $(p - 1)(q - 1)$, then $M =$ ____.
|