algebra cards Flashcards
a|b
a is a factors of b/ a divides b/ b is divisible by a
b/a∈ℤ implies
a|b
composite numbers
any number greater than 1 that are not prime
Mersenne numbers
numbers of the form 2ⁿ-1
if n is composite then…
2ⁿ-1 is composite
how do you use the mersenne form to factor out composite numbers?
- write the number is the form 2ⁿ-1
- choose a,b∈ℕ s.t. ab=n
3.use the general factorisation
2ⁿ-1 = (2ᵇ-1)(1+2ᵇ+2²ᵇ+…+2⁽ᵃ⁻¹⁾⁽ᵇ⁾)
how do you how do you use the mersenne form to find the prime factorisation of numbers?
- write the number is the form 2ⁿ-1
- choose a,b∈ℕ s.t. ab=n
3.use the general factorisation
2ⁿ-1 = (2ᵇ-1)(1+2ᵇ+2²ᵇ+…+2⁽ᵃ⁻¹⁾⁽ᵇ⁾) - repeat with different a and b and them use the two sets of composite numbers to find the prime factorisation
twin primes conjecture
There are infinitely many pairs (p,p+2) where both p and p+2 are prime
The division theorem states…
a = qd + r. Where q is the quotient, r is the remainder when a is divided by d
hcf(a,b) =
hcf(b,a) = hcf(-a,-b) = hcf(-a,b) = hcf(a,-b)
The highest common factor is less than or equal to…
both the given values
The only common factors of coprimes are
+- 1
Bezouts lemma states…
you can write he highest common factos of a and b as a linear combination of a and b
All common factors of a and b are…
factors of the highest common factor
hcf(a,b).lcm(a,b) =
ab
the fundamental theorem of arithmetic states that
there is a unique prime factorisation for a n∈ℕ
what is the prime factorisation of 1 called
the empty product
a is congruent to bmodn if
n|a-b s.t. a=b+nx
reflexive property of congruences
a≡amodn
symmetric property of congruences
if a ≡bmodn then b≡amodn
how to work out remainders when we do division of large numbers (divisor a, dividend of the form b+nx)
1. find two congruences x≡z₁moda n≡z₂moda hence nx = (z₁z₂)moda 3. find a congruence b≡z₃moda hence b+nx = (z₁z₂+z₃)moda 4. so when b+nx is divded by a it leaves the remainder of (z₁z₂+z₃)
how to show divisibility by 3/9
- put number as a series of digits multiplied by a power of 10
- knowing 10≡1mod3 /10≡1mod9 substitute this into the series
- factor out the modulo. we know 3|a/9|a iff 9/9 is a factor of the series
- sum the series a₀+a₁+a₂+…+aᵣ₋₁+aᵣ, if the sum is divisible by 3/9 the conclude a is divisible by 3/9
how to show a number is a perfect square
- a≡bmodn so that a²≡b²modn
- make a table with b,b²,c where b²≡cmodn and b goes up to n
- find an expression for x≡mmodn where m is as small as possible
- if m∈c then x is a perfect square
linear congruence equation
an equation of the form ax≡bmodn
how to solve a linear congruence equation ax≡bmodn
- let x≡zmodn
- Then ax≡azmodn
- make a table with x ax and y where y≡axmodn
- The solutions are given in the column where y=b
Algorithm to solve linear congruence euqations ax≡bmodn
- calculate h= hcf(a,n)
- if h/|b then no solutions
else calculate a’x≡b’modn’ where a’ = a/h, b’ = b/h and n’ = n/h - find s s.t. a’s ≡b’modn’ the solutions are given by x≡smodn’
to find an s s.t. a’s ≡b’modn’
consider z s.t. a’z≡1modn’ and let z = zb (we can find z by euclidean algorithm or inspection)
how to solve a pair of linear congruences
x≡amodn
x≡bmodm
- from x≡amodn we have x=a+ny
- equate the equation a+ny = bmodm
- rearrange for ny ny = (b-a)modm
- find a solution y=k and sub into y=kmodm this gives y = k +mz. Sub this back into x
- solutions are given by x=a+n(k+mz) = (a+nk)modnmz
simplify a+ bx ≡ c modn
bx ≡ (c-a)modn
Congruence class of a modulo n
the set of integers that are congruent to a modulo n
[a]ₙ = {…,a-2n,a-n,a,a+n,a+2n,…}
congruence classes are equal
the sets are equal i.e. amodn≡bmodn
ring of integers modulo n
The set of congruence classes modulo n with defined addition and multiplication
fermats little theorem
is p doesn’t divide a then aᵖ⁻¹≡1modp
permuatation
the permutation of a set Ω is a bijection Ω->Ω
cycle
distinct elements of f:Ω->Ω that form a loop
why is cycle notation not unique
- a cycle can begin with any of its elements
- disjoint cycles can be rearranged
permutation group
G is a permuation group if G⊆Sym(Ω) and composition is closed, G contains an identity and G is closed under an inverse
symmetric group on Ω
Sym(Ω)
group
A set G with a binary operation * that satifies closure, associativity, existence of identity and existence of inverse
abelian group
a group where commutativity is satisfied
subgroup
group where set is subset of another group and binary operation is the same H≤G
cyclic group G
if G=
gʳ =
gg…*g r times (where * is the binary operation)
g⁻ʳ =
(g⁻¹)ʳ
smallest subgroup of G generated by x
= {xᵐ: m∈ℤ}
