Unit 5 (DNF) Flashcards
What is the smallest possible integer n such that n = ax + by?
gcd(a, b)
Definition of relatively prime (coprime)
a, b are only coprime iff gcd(a, b) = 1.
a \equiv b (mod m)
if and only if m | (a - b)
Definition of a | b
There exists an integer k such that b = ka.
Definition of a function
Let A and B be sets. A function f from A to B, denoted f : A → B, is a
subset f ⊆ A × B in which, for every a ∈ A, there exists exactly one b ∈ B
such that (a, b) ∈ f.
When is a function invalid?
When there exists b ∈ B with more than one preimage
Definition of injective
iff every element of B is the second component of at most one element of an ordered pair in f.
Definition of surjective
For every b ∈ B, there exists a preimage a ∈ A such that f(a) = b
When are two functions equal?
Two functions f and g are equal iff
- they have the same domain
- they have the same codomain (target)
- f(x) = g(x) for all x in the domain
Supposition for proving injectivity
Suppose f(x) = f(y). Then, prove that x = y.
Supposition for proving surjectivity
Take any y ∈ range. If y = f(x) then solve for x. If all x is in domain, then for all f(x), f(x) = y.
Identity function of any set A
The identity function on A is the function ιA : A → A defined by ιA(a) = a for every a ∈ A
Def. of inverse functions
functions f : A → B and g : B → A to be inverses if f(a) = b ⇔ g(b) = a. Equivalently, f : A → B and g : B → A are inverses if g ◦ f = ιA and f ◦ g = ιB.
When can a function f have an inverse?
Iff f is bijective.
f : A → B and g : B → A and f and g are inverses. g ◦ f = ?
ιA (identity function of domain A)
