Sem 1 Liebeck Flashcards
1
Q
equality
A
exactly same elements
2
Q
P=>Q
A
P implies Q
if P then Q
Q if P
P only if Q
3
Q
negation p bar
A
If P=>Q
then Q bar => P bar
4
Q
negation of for all
A
there exists
5
Q
for all x statements in the empty set
A
always true
6
Q
there exists an x statements in the empty set
A
always false
7
Q
number systems rules
A
a+b = b+a
a+(b+c)=(a+b)+c
a(b+c)=ab+ac
8
Q
between any 2 rationals…
A
there is another rational
9
Q
if a is rational and b is irrational
A
a+b irrational
if a does not =0, ab irrational
10
Q
if x does not = 1, then x + x^2 + x^3 +…+ x^n=
A
x(1-x^n) / 1-x
11
Q
if -1<x<1, then x + x^2 + x^3 +… =
A
x / 1-x
12
Q
if -1< x <1, then x + x^2 + x^3 +…=
A
1 / 1-x
13
Q
every real number has decimal expression of form
A
x=a0.a1a2a3…
14
Q
rational form of decimal steps
A
express as fractions over a power of 10
take out common factor to leave expression for geometric series
15
Q
inequalities rules
A
- 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
16
Q
how to find x in equations with modulus steps
A
- 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
17
Q
triangle inequality
A
|x+y| </= |x| + |y|
18
Q
dividing complex numbers
A
multiply fraction by complex conjugate of denominator
19
Q
how many complex roots does every quadratic have?
A
2
20
Q
what is |z|
A
modulus of complex number
distance to origin
21
Q
argument of complex number
A
angle between the positive x axis and line from z to the origin
22
Q
polar form of a complex number
A
z=|z|(cosθ+isinθ)
adding multiples of 2pik does not change
23
Q
principle argument
A
arg(z) between negative pi and positive pi
24
Q
de moivre
A
z1z2=r1r2((cosθ1+θ2)+isin(θ1+θ2)
=r1r2e^i(θ1+θ2)
25
z^n=...
r^n(cosnθ+isinnθ)
26
z^-n
r^-n(cosnθ-isinnθ)
27
i theta form of complex numbers
z=re^iθ
e^iθ=e^i(θ+2kpi)
28
nth roots of unity
Zs that satisfy z^n=1
29
fundamental theorem of algebra
every polynomial equation of degree at least 1 has a root in C
30
polynomial of degree n factors into...
n linear equations
n roots in C
31
every real polynomial factorisies as a product of...
real linear and real quadratic polynomials
32
the non-real roots always...
come in complex conjugate pairs
33
(x-alpha)(x-beta)=
x^2-(alpha+beta)x + alphabeta
alpha+beta=-a
alphabeta=b
34
(x-alpha)(x-beta)(x-gamma)=
x^3+ax^2+bx+c
alpha+beta+gamma=-a
alphabeta+alphagamma+betagamma=b
alphabetagamma=c
35
p(n) true for all positive integers if
1. p(n) true
2. for all n,if p(n) true, p(n+1) also true
assume p(n) true, consider p(n+1)
36
PMI II
(don't need to start at 1)
1. p(k) true
2. for all n>/=k, p(n) true, p(n+1) true, then p(n) is true for all integers n>/=k
37
strong mathematical induction
1. p(k) true
2. for all n, if p(k), p(k+1),...p(n) are true, p(n+1) true
3. p(n) true for all n >/=k
38
recurrence relation
terms defined as function of previous term
39
convex
connect two points on surface together, line is contained inside polyhedron
**platonic solids are all convex**
40
euler's formula
V-E+F=2
for connected plane graph
v-e+f=1
41
plane graph
collection of points, edges joining points.
no two edges cross
42
connected plane graph
can go from any vertex to any vertex
43
drawing plane graphs for platonic solids
imagine looking through a face
44
regular polygon
all sides equal lengths, internal angels equal
faces are all same and each vertex belongs to the same number of edges
45
platonic solids
tetrahedron
cube
octahedron
dodecahedron
icosahedron
46
faces of platonic solids
cube - squares
tetrahedron, octahedron and icosahedron - triangles
dodecahedron - pentagon
47
what are n and r for platonic solids?
n=number of sides on a face
r=number of edges each vertex belongs to
48
what are the only regular convex polygons?
platonic solids
49
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
50
quotient and remainder
b=quotient a + remainder
51
if d divides a and d divides b then
d divides ma+nb
52
coprime
hcf(a,b)=1
53
if a and c are coprime and c divides ab, then
c divides b
54
if p is prime and p divides ab then
either p divides a or p divides b
55
fundamental theorem of arithmetic
integers greater than or equal to 2 are a product of primes and this prime factorisation is unique
56
hcf(a,b) using prime factorisation
p1^min(a1,b1)p2min(a2,b2)
57
lcm(a,b) using prime factorisation
p1^max(a1,b1)p2max(a2,b2)
ab/hcf(a,b)
58
root n rational if and only if
n=m^2 for some m
59
if a and b are coprime and ab a square
both a and b squares
60
a and b coprime and ab is an nth power for some n (natural number),
both a and b also nth powers
61
diophantinc equation
polynomial in two or more variables in which only integer solutions considered
eg: x^3=y^2
62
how to approach diophantinc equations
does euclid help?
can you factor?
can you apply FTA?
63
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
64
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
65
every integer greater than 2 is...
the sum of two prime numbers
66
every odd integer greater than 5 is...
the sum of three prime numbers
67
if m divides b-a
a congruent to b mod m
68
suppose a≡b(mod m) and c≡d(mod m)
a+c≡b+d (mod m)
ac≡bd (mod m)
69
if a≡b(mod m) and n +ve
a^n≡b^n(mod m)
70
method of successive squaring
keep squaring
make power up using indices
multiply congruences
71
rule of nines
n divisible by 9 if sum of digits divisible by 9
72
a and m coprime, x,y integers then
xa≡ya(mod m)
x≡y(mod m)
73
form of congruence equations
ax≡b(mod m)
74
condition for congruence equation to have solution
if and only if hcf(a,m) divides b
75
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
76
Zm=
{0,1,...,m-1}
77
adding in Zm
a+b=a+b(mod m)
78
multiplying in Zm
a.b=a.b(mod m)
79
Zm for low numbers
can check all possibilities using table
(sub different x values into expression and then evaluate in modulo m)
80
Fermat's little theorem
*a not divisible by p*
a^p-1≡1(mod p)
can use to check if a number is prime
81
if p and q are distinct primes, a an integer not divisible by p or q
a^(p-1)(q-1)≡1(mod pq)
82
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
83
if k is coprime to p-1
1. positive integer s such that sk≡1(mod p-1)
2. 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)
84
RSA encoding setting up
two large prime p and q
1. multiply so N=pq
2. find m=(p-1)(q-1)
3. find e coprume to M
whole message broken into chunks
85
RSA encoding for each segment x
compute y≡x^e(modN)
using successive squaring
send y value and repeat
86
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
