Theorems
By definition of the pigeonhole principle, if you have n+1 objects into n boxes, what does that imply?
At least 2 objects must go in 1 box
8 mod 5
3
AC∩BC
x ∈ ℤ
x in the integers
P(n,r) = ?
n!/(n-r)!
For all a,m in the integers, m>0, there exists a q,r in the integers such that a = mq+r, 0≤r<m.
The Division Algorithm
33 mod 17
16
Suppose A,B are sets. What does A ⊆ B mean and what is its definition?
A is a subset of B: every element of A is an element of B
What does a|b imply?
b=ak for some k in integers
|AxB| = ?
|A||B|
53 mod 21
20
Suppose A is a set. What does |A| mean?
The cardinality of A: the number of elements in A
𝒫(A)
Powerset of A
How many outfits can you make with 3 shirts, 2 pants, 5 socks, 3 shoes?
3*2*5*3 = 90 outfits
For a,b positive integers, there exists k,l in integers such that gcd(a,b) = ak + bl
Bezout's Theorem
φ(17)
16
Give the name of this definition:
AxB = {(a,b)|a∈A, b∈B}
The Cartesian Product
U\A = {x ∉ A}
AC (Complement)
If a password consists of 3 digits, how many passwords are needed to guarantee two people with the same password?
103 + 1
For a in integers, p prime, p∤a, then ap-1 ≡ 1 mod p
Fermat's Lil Theorem
611 mod 11
6
610 mod 11 = 1 (FLT), 1*6=6
Give 𝒫(A) where A = {1,2,3}
{∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}
In the definition of modular arithmetic, what does
a ≡ b mod m imply?
m|(a-b)
5*4*3 = 60