Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Year 2 > Number Theory > Flashcards

Number Theory Flashcards

1
Q

When does a divide b

A

When there exists an integer c such that b = ac. We write a | b

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

When is an integer p prime

A

if the only divisors are 1, -1, p, -p

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

Theorem: There are infinitely many primes

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

Define the highest common factor

A

Let a,b (integers), at least one is non zero. The highest common factor is the largest natural number dividing both a and b

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

State Bezout’s Lemma

A

Let m,n be integers, both non-zero. There exists integers a,b such that am + bn = hcf(a,b)

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

State and prove Euclids Lemma

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

State the fundamental theorem of arithmetic

A

Every non-zero integer may be written as a product of prime factors, multiplied by 1 or -1. This prime factorisation is unique apart from the order by which we write the prime factors

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

Prove the fundamental theorem of arithmetic

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

Let R be a commutative ring. When is a subset I of R an ideal of R [3]

A

i) 0 is in I
ii) for any a,b in I, a + b and a - b are in I
iii) for any a in I and any r in R, ar is in I

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

What is a principal ideal

A

The ideal generated by a, ie {ar : r in R}

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

Define an integral domain

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

When is R a principal ideal domain

A

If it’s an integral domain and every ideal of R is principal

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

Proposition: Z is a principal ideal domain

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

State Fermat’s Last Theorem

A

For any integer n > 2, there are no solutions to the equation xn + yn = zn with x,y,z positive integers

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

Define a unit and associates

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

What is U(Z)

A

{-1, 1}

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

Define irreducible and prime in this sense

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

Lemma: In any integral domain R, every prime element is irreducible

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

Define factorisations that are essentially the same

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

When is an integral domain R a unique factorisation domain (UFD)

A

If every non-zero element a in R has a factorisation as a unit multiplied by a product of irreducibles, and all factorisations are essentially the same

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

How do we show a group isn’t a UFD

A

Find two factorisations and show the factors are irreducibles and not associates

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

State and prove the cancellation lemma

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

Define highest common factor

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

Lemma: Let R be a commutative ring, and suppose that d in R is a hcf of a,b in R. Then an element e in R is a hcf of a,b in R if and only if e is an associate of d

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

Show in Z[root(-5)] the hcf of 6 and 2 + root(-5) doesnt exist

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

Lemma: In any principal ideal domain R, every irreducible element is prime

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

Define a Euclidean domain

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

Theorem: Every Euclidean domain R is a Principal Ideal domain

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

Define congruence modulo m

A
30
Q

Proposition: The equation x2 + y2 + 3z2 has no integer solutions for x,y,z apart from the trivial solution x = y = z = 0

A
31
Q

Define Z/mZ

A

The set {0,1,……,m-1}, equipped with addition and multiplication modulo m

32
Q

What is (Z/mZ)X

A

The group of units of Z/mZ, which is the elements a such that hcf(a,m) = 1

33
Q

For a,b in Z and m in N, when is there a solution x in Z to the congruence ax = b mod m, and what is it

A
34
Q

How do we go about solving the linear congruence ax = b mod m

A

Find integers x0 and y such that ax0 + my = hcf(a,m) by euclidean algorithm. Since hcf(a,m) | b, we can multiply to get the desired value of x0

35
Q

Define the Euler Totient formula

A
36
Q

If p is prime, what is phi(p)

A

p - 1

37
Q

State and prove Euler’s theorem

A
38
Q

State Fermat’s little theorem

A
39
Q

Define quadratic residue mod m

A
40
Q

Define the legendre symbol

A
41
Q

State the two squareroots lemma

A
42
Q

State Wilson’s theorem

A

If p is prime, then (p-1)! = -1 mod p. If m > 5 is composite, then (m-1)! = 0 mod m

43
Q

State Eulers criterion

A
44
Q

When is -1 a quadratic residue or a quadratic non-residue mod p

A

quadratic residue if p = 1 mod 4, quadratic non-residue if p = 3 mod 4

45
Q

State the Chinese Remainder theorem

A
46
Q

How do we solve a problem using the chinese remainder theorem

A

Define Mi = product of mj excluding mi.

Find yi such that Miyi = 1 mod mi.

Then x is equal to the sum of aiMiYi for all i

47
Q
A
48
Q

When is a function f: N to C multiplicative

A

When f(mn) = f(m)f(n) if hcf(m,n) = 1

49
Q

Define the order of a mod m

A
50
Q

for any u in N, what is ordm(au) and what is the relationship between ordm(a) and phi(m)

A
51
Q

Define a primitive root

A
52
Q

Let p be a prime. For every natural number d such that d | (p-1) how many elements a are there such that ordp(a) = d

A

phi(d)

53
Q

Lemma: If g is a primitive root and u in N, gu is a primitive root if and only if hcf(u, p-1) = 1

A
54
Q

State and prove the dth roots lemma

A
55
Q

Give the equations for legendre symbol (2 / p) for an odd prime p

A
56
Q

State the theorem of quadratic reciprocity

A
57
Q

State Gauss’s Lemma

A
58
Q

When can a natural number n be written as a sum of two integer squares

A

if and only if in its prime factorisation, any prime that is = 3 mod 4 has an even exponent

59
Q

What are the only prime/ irreducible elements of Z[i]

A
60
Q
A
61
Q
A
62
Q

State Lagrange’s four squares theorem

A

Every natural number n may be written as the sum of four integer squares

63
Q

Define a lattice

A

We say a set L in Zn is a lattice in Zn if L is an additive subgroup

64
Q

Define symmetric and convex

A

A set S in Rn is symmetric if for all x in S we have -x in S. S in convex if for all x,y in S the line segment { tx + (1-t)y : 0 < t < 1} is in S

65
Q

State Minkowskis Theorem, weak form

A
66
Q

Define a pythagorean triple

A

We say (x,y,z) is a triple of natural numbers is a pythagorean triple if x2 + y2 = z2

67
Q

When is a pythagorean triple primitive

A

if there is no natural number d > 1 that divides all of x,y,z

68
Q

When is a triple (x,y,z) a pythagorean triple? (whats the parameterisation)

A

x = u2 - v2

y = 2uv

z = u2 + v2

for coprime u,v in N, not both odd

69
Q
A
70
Q

When does the Legendre equation have solutions

A

Year 2 (15 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions