algebra cards

Question 1

a|b

Answer 1

a is a factors of b/ a divides b/ b is divisible by a

Question 2

b/a∈ℤ implies

Answer 2

a|b

Question 3

composite numbers

Answer 3

any number greater than 1 that are not prime

Question 4

Mersenne numbers

Answer 4

numbers of the form 2ⁿ-1

Question 5

if n is composite then…

Answer 5

2ⁿ-1 is composite

Question 6

how do you use the mersenne form to factor out composite numbers?

Answer 6

1. write the number is the form 2ⁿ-1
2. choose a,b∈ℕ s.t. ab=n
   3.use the general factorisation
   2ⁿ-1 = (2ᵇ-1)(1+2ᵇ+2²ᵇ+…+2⁽ᵃ⁻¹⁾⁽ᵇ⁾)

Question 7

how do you how do you use the mersenne form to find the prime factorisation of numbers?

Answer 7

1. write the number is the form 2ⁿ-1
2. choose a,b∈ℕ s.t. ab=n
   3.use the general factorisation
   2ⁿ-1 = (2ᵇ-1)(1+2ᵇ+2²ᵇ+…+2⁽ᵃ⁻¹⁾⁽ᵇ⁾)
3. repeat with different a and b and them use the two sets of composite numbers to find the prime factorisation

Question 8

twin primes conjecture

Answer 8

There are infinitely many pairs (p,p+2) where both p and p+2 are prime

Question 9

The division theorem states…

Answer 9

a = qd + r. Where q is the quotient, r is the remainder when a is divided by d

Question 10

hcf(a,b) =

Answer 10

hcf(b,a) = hcf(-a,-b) = hcf(-a,b) = hcf(a,-b)

Question 11

The highest common factor is less than or equal to…

Answer 11

both the given values

Question 12

The only common factors of coprimes are

Answer 12

+- 1

Question 13

Bezouts lemma states…

Answer 13

you can write he highest common factos of a and b as a linear combination of a and b

Question 14

All common factors of a and b are…

Answer 14

factors of the highest common factor

Question 15

hcf(a,b).lcm(a,b) =

Answer 15

ab

Question 16

the fundamental theorem of arithmetic states that

Answer 16

there is a unique prime factorisation for a n∈ℕ

Question 17

what is the prime factorisation of 1 called

Answer 17

the empty product

Question 18

a is congruent to bmodn if

Answer 18

n|a-b s.t. a=b+nx

Question 19

reflexive property of congruences

Answer 19

a≡amodn

Question 20

symmetric property of congruences

Answer 20

if a ≡bmodn then b≡amodn

Question 21

how to work out remainders when we do division of large numbers (divisor a, dividend of the form b+nx)

Answer 21

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₃)

Question 22

how to show divisibility by 3/9

Answer 22

1. put number as a series of digits multiplied by a power of 10
2. knowing 10≡1mod3 /10≡1mod9 substitute this into the series
3. factor out the modulo. we know 3|a/9|a iff 9/9 is a factor of the series
4. sum the series a₀+a₁+a₂+…+aᵣ₋₁+aᵣ, if the sum is divisible by 3/9 the conclude a is divisible by 3/9

Question 23

how to show a number is a perfect square

Answer 23

1. a≡bmodn so that a²≡b²modn
2. make a table with b,b²,c where b²≡cmodn and b goes up to n
3. find an expression for x≡mmodn where m is as small as possible
4. if m∈c then x is a perfect square

Question 24

linear congruence equation

Answer 24

an equation of the form ax≡bmodn

Question 25

how to solve a linear congruence equation ax≡bmodn

Answer 25

1. let x≡zmodn 2. Then ax≡azmodn 3. make a table with x ax and y where y≡axmodn 4. The solutions are given in the column where y=b

Question 26

Algorithm to solve linear congruence euqations ax≡bmodn

Answer 26

1. calculate h= hcf(a,n) 2. if h/|b then no solutions else calculate a'x≡b'modn' where a' = a/h, b' = b/h and n' = n/h 3. find s s.t. a's ≡b'modn' the solutions are given by x≡smodn'

Question 27

to find an s s.t. a's ≡b'modn'

Answer 27

consider z s.t. a'z≡1modn' and let z = zb (we can find z by euclidean algorithm or inspection)

Question 28

how to solve a pair of linear congruences x≡amodn x≡bmodm

Answer 28

1. from x≡amodn we have x=a+ny 2. equate the equation a+ny = bmodm 3. rearrange for ny ny = (b-a)modm 4. find a solution y=k and sub into y=kmodm this gives y = k +mz. Sub this back into x 5. solutions are given by x=a+n(k+mz) = (a+nk)modnmz

Question 29

simplify a+ bx ≡ c modn

Answer 29

bx ≡ (c-a)modn

Question 30

Congruence class of a modulo n

Answer 30

the set of integers that are congruent to a modulo n | [a]ₙ = {...,a-2n,a-n,a,a+n,a+2n,...}

Question 31

congruence classes are equal

Answer 31

the sets are equal i.e. amodn≡bmodn

Question 32

ring of integers modulo n

Answer 32

The set of congruence classes modulo n with defined addition and multiplication

Question 33

fermats little theorem

Answer 33

is p doesn't divide a then aᵖ⁻¹≡1modp

Question 34

permuatation

Answer 34

the permutation of a set Ω is a bijection Ω->Ω

Question 35

cycle

Answer 35

distinct elements of f:Ω->Ω that form a loop

Question 36

why is cycle notation not unique

Answer 36

- a cycle can begin with any of its elements | - disjoint cycles can be rearranged

Question 37

permutation group

Answer 37

G is a permuation group if G⊆Sym(Ω) and composition is closed, G contains an identity and G is closed under an inverse

Question 38

symmetric group on Ω

Answer 38

Sym(Ω)

Question 39

group

Answer 39

A set G with a binary operation * that satifies closure, associativity, existence of identity and existence of inverse

Question 40

abelian group

Answer 40

a group where commutativity is satisfied

Question 41

subgroup

Answer 41

group where set is subset of another group and binary operation is the same H≤G

Question 42

cyclic group G

Answer 42

if G=

Question 43

gʳ =

Answer 43

g*g*...*g r times (where * is the binary operation)

Question 44

g⁻ʳ =

Answer 44

(g⁻¹)ʳ

Question 45

smallest subgroup of G generated by x

Answer 45

= {xᵐ: m∈ℤ}