Math 533 Flashcards

well ordering principle

every nonempty subset of N has a least element

for n,k in Z, 0≤k≤n we have

n choose k = (n!)/(k!(n-k)!)

Fibonacci numbers

Define F₀=0 and F₁=1 and F_n+2=F_n+F_n+1

Lucas numbers in terms of L

Define L₁=1 and L₂=3 and L_n+2=L_n+L_n+1

Lucas numbers in terms of Fibonacci

L_n=F_n-1+F_n+1

a|b

for a,b ∈ Z with a≠0, we write a|b if ∃n∈Z s.t. b=an

a|b in statements

b is divisible by a; a divides b; b is a multiple of a

a^m||b

if a^m|b but a^m+1|b (m is the largest power of a that divides b)

reflexive

a|a

transitive

if a|b and b|c then a|c

asymmetric

if a|b and b|a then a=b

divisibility is a partial order on N

if it is reflexive, transitive and asymmetric (or symmetric?)

tip when solving for reflexive, transitive, and asymmetric

create integers to plug in; if a|b then “create” n s.t. b=an; then use algebra to solve

division algorithm

suppose a∈Z and b∈N then there are unique q,r ∈ Z s.t. a=bq+r with 0≤r<b

d is a common divisor of a and b

if d|a and d|b

d is the gcd(a,b)

if when c|a and c|b then c|d for some c∈Z

Bezout’s theorem

Suppose a,b ∈ Z with at least one ≠0, then ∃x,y ∈ Z s.t. gcd(a,b)=ax+by

theorem 2.2/ linear combination property; gcd multiple

suppose a,b,x,y ∈ Z then ax+by is a multiple of d=gcd(a,b)

theorem 2.4/relatively prime characterization

Let a,b ∈ Z, not both zero, then a and b are relatively prime IFF ∃x,y ∈ Z s.t. ax+by=1

Euclid’s lemma

If a|bc with gcd(a,b)=1 then a|c

Euclidean Algorithm Property/Lemma gcd with remainder

If a=qb+r, then gcd(a,b)=gcd(b, r); from div alg

Euclidean Algorithm

suppose a,b ∈ N with a>b then gcd(a,b)=r_k ; r_k-2=r_k-1q_k+r_k

extended euclidean algorithm steps

find gcd via euclidean algorithm; “reverse” it and find the remainder for each in terms of the top variables

prime def

we say p>1 is prime if its only divisors are 1 and p

composite def

not prime; can be written as n=ab for n,a,b ∈ N with 1<a,b<n

Fundamental Theorem of Arithmetic

∀n>1, the factorization of n into primes is unique (up to permutation)

theorem 3.1 (p,a,b)

if p|ab then either p|a or p|b

existence part of the FTA

every n>1 can be written as a product of primes

generalized euclid’s lemma

if p is prime and p|(a₁a₂...a_m) then p|a_j for some 1≤j≤m

corollary of FTA; prime divides prime

if p,q₁…q_n are all primes and p|(q₁q₂…q_n) then p=q_k for some 1≤k≤n

add corollary about the exponent stuff

note to self

Euclid’s Theorem (theorem 3.4)

There are infinitely many prime numbers

goldenbach conjecture

every even natural number greater than 2 is the sum of two prime numbers

modular arithmetic def

for n∈N and a,b ∈ Z, a≡b(mod n) if n|(a-b)

theorem 4.1 (mod remainder equivalence)

for a,b ∈ Z, a≡b(mod n) iff a and b have the same remainder when dividing by n

for n∈N and a,b,c,d ∈ Z, if a≡c(mod n) and b≡d(mod n)

then (a+b)≡(c+d)(mod n) and ab≡cd(mod n)

for n∈N and a,b,d ∈ Z, if a≡b(mod n) and d|n

then a≡b(mod d)

for n∈N and a,b ∈ Z, if a≡b(mod n) and c∈N

then ac≡bc(mod nc)

for n∈N and a,b,c,d ∈ Z, if a≡b(mod n), (exponent)

then a^k≡b^k(mod n)

for n∈N and a,b ∈ Z, if a≡b(mod n) and c∈N

then (a+c)≡(b+c)(mod n) and ac≡bc(mod n)

theorem 4.3 (cancellation law for congruences) (gcd)

if ca≡cb(mod n) then a≡b(mod n/d) where d=gcd(c,n)

expansion of N

given an integer b>1, any positive integer N can be written uniquely in terms of powers of b: b^ma_m+ b^m-1a_m-1+…+a₀

base 10 expansion of N

10^ma_m+ 10^m-1a_m-1+…+a₀

linear congruence theorem (theorem 4.7)

The linear congruence ax≡b(mod n) has a solution iff d|b, where d=gcd(a,n); If d|b, then it has d mutually incongruent solutions modulo n

incongruent solutions def

answers to a modular math problem that do not equal each other under that specific modulo

steps to solve linear congruence

check if solution exists (gcd(a,n)|b and gcd(a,n) solutions exist); put in ax₀+ny₀=gcd(a,n) form; find a single “seed” solution for x₀ and y₀; rewrite in mod form ax₀≡(gcd(a,n))(mod n); multiply whole equation by integer to get gcd(a,n) equal to b; get x_m=x₀+m(n/d); solve for all m=0 to m=((gcd(a,n))-1)

chinese remainder theorem

Let n₁,n₂,…,n_k ∈ N be s.t. gcd(n_i,n_j)=1 ∀i≠j and suppose a₁,a₂,…,a_k ∈ Z, then [(x≡a₁(mod n₁))…(x≡a_k(mod n_k))] has a unique solution modulo N=n₁n₂…n_k

steps to using chinese remainder theorem (solving system of linear congruences)

check gcd of every value with each other is 1; if not, reduce as needed; let N=n₁n₂…n_k; set N₁=N/n₁ and repeat for all n; solve inverse for each x, start with x₁≡N₁^-1(mod n₁) and reduce N₁^-1 and repeat for every x; x₁=reduced value of N₁^-1 from x₁≡N₁^-1(mod n₁), same for all other x; x=(a₁x₁n₁)+…+(a_kx_kn_k); answer is x(mod N), reduce as needed

splitting up mod

if x≡a(mod nm) then x≡a(mod n) and x≡a(mod m) ; (n and m MIGHT have to be prime, check for iff version)

fermat’s little theorem

Let p be prime and a∈Z s.t. p|a then a^p-1≡1(mod p)

theorem 4.9 (system of linear congruences addition solution)

The system of linear congruences (ax+by)≡r(mod n) and (cx+dy)≡s(mod n) has a unique solution modulo n whenever gcd((ad-bc), n)=1

corollary of fermat’s theorem

if p is prime then a^p≡a(mod p) for any a∈Z

wilson’s theorem

p is prime iff (p-1)!≡(-1)(mod p)

didn’t add

lemma self study num 14; last theorem on self study num 14; some stuff in textbook; SIEVE OF ERATOSTHENES