algebra cards Flashcards

1
Q

a|b

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

b/a∈ℤ implies

A

a|b

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

composite numbers

A

any number greater than 1 that are not prime

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Mersenne numbers

A

numbers of the form 2ⁿ-1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

if n is composite then…

A

2ⁿ-1 is composite

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A
  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⁽ᵃ⁻¹⁾⁽ᵇ⁾)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A
  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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

twin primes conjecture

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

The division theorem states…

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

hcf(a,b) =

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

The highest common factor is less than or equal to…

A

both the given values

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

The only common factors of coprimes are

A

+- 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Bezouts lemma states…

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

All common factors of a and b are…

A

factors of the highest common factor

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A

ab

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

the fundamental theorem of arithmetic states that

A

there is a unique prime factorisation for a n∈ℕ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

what is the prime factorisation of 1 called

A

the empty product

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

a is congruent to bmodn if

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

reflexive property of congruences

A

a≡amodn

20
Q

symmetric property of congruences

A

if a ≡bmodn then b≡amodn

21
Q

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

A
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₃)
22
Q

how to show divisibility by 3/9

A
  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
23
Q

how to show a number is a perfect square

A
  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
24
Q

linear congruence equation

A

an equation of the form ax≡bmodn

25
Q

how to solve a linear congruence equation ax≡bmodn

A
  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
26
Q

Algorithm to solve linear congruence euqations ax≡bmodn

A
  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’
27
Q

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

A

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

28
Q

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

A
  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
29
Q

simplify a+ bx ≡ c modn

A

bx ≡ (c-a)modn

30
Q

Congruence class of a modulo n

A

the set of integers that are congruent to a modulo n

[a]ₙ = {…,a-2n,a-n,a,a+n,a+2n,…}

31
Q

congruence classes are equal

A

the sets are equal i.e. amodn≡bmodn

32
Q

ring of integers modulo n

A

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

33
Q

fermats little theorem

A

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

34
Q

permuatation

A

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

35
Q

cycle

A

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

36
Q

why is cycle notation not unique

A
  • a cycle can begin with any of its elements

- disjoint cycles can be rearranged

37
Q

permutation group

A

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

38
Q

symmetric group on Ω

A

Sym(Ω)

39
Q

group

A

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

40
Q

abelian group

A

a group where commutativity is satisfied

41
Q

subgroup

A

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

42
Q

cyclic group G

A

if G=

43
Q

gʳ =

A

gg…*g r times (where * is the binary operation)

44
Q

g⁻ʳ =

A

(g⁻¹)ʳ

45
Q

smallest subgroup of G generated by x

A

= {xᵐ: m∈ℤ}