Sem 1 Liebeck Flashcards
equality
exactly same elements
P=>Q
P implies Q
if P then Q
Q if P
P only if Q
negation p bar
If P=>Q
then Q bar => P bar
negation of for all
there exists
for all x statements in the empty set
always true
there exists an x statements in the empty set
always false
number systems rules
a+b = b+a
a+(b+c)=(a+b)+c
a(b+c)=ab+ac
between any 2 rationals…
there is another rational
if a is rational and b is irrational
a+b irrational
if a does not =0, ab irrational
if x does not = 1, then x + x^2 + x^3 +…+ x^n=
x(1-x^n) / 1-x
if -1<x<1, then x + x^2 + x^3 +… =
x / 1-x
if -1< x <1, then x + x^2 + x^3 +…=
1 / 1-x
every real number has decimal expression of form
x=a0.a1a2a3…
rational form of decimal steps
express as fractions over a power of 10
take out common factor to leave expression for geometric series
inequalities rules
- if x is a real number either x>0 or x<0 or x=0 and just one of these is true
- if x>y then -x<-y
- if x>y and c is a real number then x+c>y+c
- if x>0, y>0 then xy>0
- if x>y, y>z then x>z
how to find x in equations with modulus steps
- where does the modulus change?
- list cases for between each change
- case for both +ve, one +ve and one -ve and both -ve - evaluate inequality for each
- reach overall range based on cases
triangle inequality
|x+y| </= |x| + |y|
dividing complex numbers
multiply fraction by complex conjugate of denominator
how many complex roots does every quadratic have?
2
what is |z|
modulus of complex number
distance to origin
argument of complex number
angle between the positive x axis and line from z to the origin
polar form of a complex number
z=|z|(cosθ+isinθ)
adding multiples of 2pik does not change
principle argument
arg(z) between negative pi and positive pi
de moivre
z1z2=r1r2((cosθ1+θ2)+isin(θ1+θ2)
=r1r2e^i(θ1+θ2)
z^n=…
r^n(cosnθ+isinnθ)
z^-n
r^-n(cosnθ-isinnθ)
i theta form of complex numbers
z=re^iθ
e^iθ=e^i(θ+2kpi)
nth roots of unity
Zs that satisfy z^n=1
fundamental theorem of algebra
every polynomial equation of degree at least 1 has a root in C
polynomial of degree n factors into…
n linear equations
n roots in C
every real polynomial factorisies as a product of…
real linear and real quadratic polynomials
the non-real roots always…
come in complex conjugate pairs
(x-alpha)(x-beta)=
x^2-(alpha+beta)x + alphabeta
alpha+beta=-a
alphabeta=b
(x-alpha)(x-beta)(x-gamma)=
x^3+ax^2+bx+c
alpha+beta+gamma=-a
alphabeta+alphagamma+betagamma=b
alphabetagamma=c
p(n) true for all positive integers if
- p(n) true
- for all n,if p(n) true, p(n+1) also true
assume p(n) true, consider p(n+1)
PMI II
(don’t need to start at 1)
- p(k) true
- for all n>/=k, p(n) true, p(n+1) true, then p(n) is true for all integers n>/=k
strong mathematical induction
- p(k) true
- for all n, if p(k), p(k+1),…p(n) are true, p(n+1) true
- p(n) true for all n >/=k
recurrence relation
terms defined as function of previous term
convex
connect two points on surface together, line is contained inside polyhedron
platonic solids are all convex
euler’s formula
V-E+F=2
for connected plane graph
v-e+f=1
plane graph
collection of points, edges joining points.
no two edges cross
connected plane graph
can go from any vertex to any vertex
drawing plane graphs for platonic solids
imagine looking through a face
regular polygon
all sides equal lengths, internal angels equal
faces are all same and each vertex belongs to the same number of edges
platonic solids
tetrahedron
cube
octahedron
dodecahedron
icosahedron
faces of platonic solids
cube - squares
tetrahedron, octahedron and icosahedron - triangles
dodecahedron - pentagon
what are n and r for platonic solids?
n=number of sides on a face
r=number of edges each vertex belongs to
what are the only regular convex polygons?
platonic solids
only regular convex polygons are platonic solids proof
lemma: 2E=nF
lemma 2: 2E=rV
lemma 3: 1/r+1/n=1/2+1/E
lemma 4: either n=3 or r=3 comparing possibilities gives all the platonic solids
quotient and remainder
b=quotient a + remainder
if d divides a and d divides b then
d divides ma+nb
coprime
hcf(a,b)=1
if a and c are coprime and c divides ab, then
c divides b
if p is prime and p divides ab then
either p divides a or p divides b
fundamental theorem of arithmetic
integers greater than or equal to 2 are a product of primes and this prime factorisation is unique
hcf(a,b) using prime factorisation
p1^min(a1,b1)p2min(a2,b2)
lcm(a,b) using prime factorisation
p1^max(a1,b1)p2max(a2,b2)
ab/hcf(a,b)
root n rational if and only if
n=m^2 for some m
if a and b are coprime and ab a square
both a and b squares
a and b coprime and ab is an nth power for some n (natural number),
both a and b also nth powers
diophantinc equation
polynomial in two or more variables in which only integer solutions considered
eg: x^3=y^2
how to approach diophantinc equations
does euclid help?
can you factor?
can you apply FTA?
how to check if a number is prime
check if p divides n for all prime numbers from 2 to root n
if not, n is prime
let pi(n) be the number of primes up to n
ratio of pi(n) and n/loge(n)…
tends to 1 as n tends to infinity
every integer greater than 2 is…
the sum of two prime numbers
every odd integer greater than 5 is…
the sum of three prime numbers
if m divides b-a
a congruent to b mod m
suppose a≡b(mod m) and c≡d(mod m)
a+c≡b+d (mod m)
ac≡bd (mod m)
if a≡b(mod m) and n +ve
a^n≡b^n(mod m)
method of successive squaring
keep squaring
make power up using indices
multiply congruences
rule of nines
n divisible by 9 if sum of digits divisible by 9
a and m coprime, x,y integers then
xa≡ya(mod m)
x≡y(mod m)
form of congruence equations
ax≡b(mod m)
condition for congruence equation to have solution
if and only if hcf(a,m) divides b
finding solutions for congruence equations
kd=b
d=sa+tm
b=kd=k(sa+tm)
aks=b-k+m≡b(mod m)
setting x=ks gives solution
Zm=
{0,1,…,m-1}
adding in Zm
a+b=a+b(mod m)
multiplying in Zm
a.b=a.b(mod m)
Zm for low numbers
can check all possibilities using table
(sub different x values into expression and then evaluate in modulo m)
Fermat’s little theorem
a not divisible by p
a^p-1≡1(mod p)
can use to check if a number is prime
if p and q are distinct primes, a an integer not divisible by p or q
a^(p-1)(q-1)≡1(mod pq)
for x^k≡b(mod m)
solution x are called kth roots of b modulo m
looking for x such that x^k≡b in Zm
if k is coprime to p-1
- positive integer s such that sk≡1(mod p-1)
- for any b not divisible by p
x^k≡b(mod p)
has unique solution for x modulo p
solution: x≡b^s(mod p)
RSA encoding setting up
two large prime p and q
- multiply so N=pq
- find m=(p-1)(q-1)
- find e coprume to M
whole message broken into chunks
RSA encoding for each segment x
compute y≡x^e(modN)
using successive squaring
send y value and repeat
RSA decoding
find d such that de≡1(mod(p-1)(q-1))
use Euclid to find d such that 1=ed+(p-1)(q-1)t
let x=y^d(mod pq) and use successive squaring
