FP2 Flashcards
Division Algorithm
take a,b
find a/b floor that is q
r=a-bq
a=bq+r
Euclidean algorithm finds
HCF/GCD
How to euclidean algorithm
take number and apply division algorithm
take second number and apply DA with remainder
when r=0, the previous remainder is the GCD
What is Bezouts identity
Unique integer solution to gcd=ax+by
How to solve ax+by
Make sure equal to GCD of a,b
use euclids algorithm
back substitution
how to write a=b modm
a=b + km
4 mod rules
if a=b and c=d modm a+/-c = b+/-d ac=bd ka=kb a^n=b^n
Trick for solving modular stuff
make equal to power of 1
4 divisibility test
last 2 digits divisible by 4
If you want to divide in mod arithmetic
must divide modulus by gcd of m and divisor
What do you do to solve ax=b modm if gcd(a,m) does not divide b
find multiplicative inverse note gcd(a,m) = 1
how to find multiplicative inverse
use bezouts identity with a and m to find an expression of the form ap +mq = 1
multiply by p as ap = 1 mod m
fermats little theorem
a^p = a modp if p is prime
4 axioms of a group
closure
identity
inverse
associativity
Find closure
cayley table
find identity
e in group st ae=ea=a
check both
find inverse
ab=ba=e
associativity
a(bc)=(ab)c
what a symmetric group
group of all possible permutations on an object
what notation is useful for group permutations
two row notation
What is a cyclic group
a group where every element is repeated by applying the operation to the generator
what is a dihedral group
group of symmetries of a n sided regular polygon
What is the order of a group
number of distinct elements
what is the order of an element
smallest k st a^k=identity
condition for a cyclic group
|a| | |G|
what is the order of the identity
1
what is difference between a proper subgroup and a subgroup
a subgroup can be the whole group
How to find subgroups
cayley table will only show elements from that subgroup
notation for element that generates a subgroup
pointy brackets
What is Lagrange’s theorem
if H is a subgroup of G
|H| | |G|
How to show group is isophorphic
set up one to one function
show group operation is conserved
isomorphic symbol
= with ~ on top
solve homogenous 1st order
back substiution
non homogenous first order a=1
un = u(0) + sum of g(r) from 1 to n
non homogenous first order
Find CF of homogenous
choose appropriate PS
sum
use inital condition
2nd order
use coefficents to form AE (assume solution is Ar^n)
use PS
What do you have to do in reccurance PS
make sure you havent already got a term
how to find eigenvalue
det (A-lamda I )
how to find eigenvector
sub in lambda and find relationship between a and x
what is a normalised eigenvector
unit eigenvector
what if not relationship between x and y with eigenvalue
eigen vectors are 1,0 and 0,1
How to find diagonal form
Find eigens of A
combine to make P
find P-1
D= P-1AP
when can you use orthogonal diagonalisation
when A=A^t
what is true in orthogonal diagonalisation
D=P^TAP
What is cayley hamilton theorem
every square matrix satisfies its own characteristic equation
what is a characteristic equation
this is the equation to find eigenvalue
Operation of transformation composition
p . q means q then p
major arc
theta less than pi/2
minor arc
theta more than pi/2
