Number Theory

Question 1

When does a divide b

Answer 1

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

Question 2

When is an integer p prime

Answer 2

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

Question 3

Theorem: There are infinitely many primes

Answer 3

Question 4

Define the highest common factor

Answer 4

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

Question 5

State Bezout’s Lemma

Answer 5

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

Question 6

State and prove Euclids Lemma

Answer 6

Question 7

State the fundamental theorem of arithmetic

Answer 7

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

Question 8

Prove the fundamental theorem of arithmetic

Answer 8

Question 9

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

Answer 9

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

Question 10

What is a principal ideal

Answer 10

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

Question 11

Define an integral domain

Answer 11

Question 12

When is R a principal ideal domain

Answer 12

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

Question 13

Proposition: Z is a principal ideal domain

Answer 13

Question 14

State Fermat’s Last Theorem

Answer 14

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

Question 15

Define a unit and associates

Answer 15

Question 16

What is U(Z)

Answer 16

{-1, 1}

Question 17

Define irreducible and prime in this sense

Answer 17

Question 18

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

Answer 18

Question 19

Define factorisations that are essentially the same

Answer 19

Question 20

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

Answer 20

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

Question 21

How do we show a group isn’t a UFD

Answer 21

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

Question 22

State and prove the cancellation lemma

Answer 22

Question 23

Define highest common factor

Answer 23

Question 24

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

Answer 24

Question 25

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

Answer 25

Question 26

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

Answer 26

Question 27

Define a Euclidean domain

Answer 27

Question 28

Theorem: Every Euclidean domain R is a Principal Ideal domain

Answer 28

Question 29

Define congruence modulo m

Answer 29

Question 30

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

Answer 30

Question 31

Define Z/mZ

Answer 31

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

Question 32

What is (Z/mZ)^X

Answer 32

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

Question 33

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

Answer 33

Question 34

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

Answer 34

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

Question 35

Define the Euler Totient formula

Answer 35

Question 36

If p is prime, what is phi(p)

Answer 36

p - 1

Question 37

State and prove Euler's theorem

Answer 37

Question 38

State Fermat's little theorem

Answer 38

Question 39

Define quadratic residue mod m

Answer 39

Question 40

Define the legendre symbol

Answer 40

Question 41

State the two squareroots lemma

Answer 41

Question 42

State Wilson's theorem

Answer 42

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

Question 43

State Eulers criterion

Answer 43

Question 44

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

Answer 44

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

Question 45

State the Chinese Remainder theorem

Answer 45

Question 46

How do we solve a problem using the chinese remainder theorem

Answer 46

# Define M_i = product of mj excluding m_i. Find y_i such that M_iy_i = 1 mod m_i. Then x is equal to the sum of a_iM_iY_i for all i

Question 47

Answer 47

Question 48

When is a function f: N to C multiplicative

Answer 48

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

Question 49

Define the order of a mod m

Answer 49

Question 50

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

Answer 50

Question 51

Define a primitive root

Answer 51

Question 52

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

Answer 52

phi(d)

Question 53

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

Answer 53

Question 54

State and prove the d^th roots lemma

Answer 54

Question 55

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

Answer 55

Question 56

State the theorem of quadratic reciprocity

Answer 56

Question 57

State Gauss's Lemma

Answer 57

Question 58

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

Answer 58

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

Question 59

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

Answer 59

Question 60

Answer 60

Question 61

Answer 61

Question 62

State Lagrange's four squares theorem

Answer 62

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

Question 63

Define a lattice

Answer 63

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

Question 64

Define symmetric and convex

Answer 64

A set S in Rⁿ 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

Question 65

State Minkowskis Theorem, weak form

Answer 65

Question 66

Define a pythagorean triple

Answer 66

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

Question 67

When is a pythagorean triple primitive

Answer 67

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

Question 68

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

Answer 68

x = u² - v² y = 2uv z = u² + v² for coprime u,v in N, not both odd

Question 69

Answer 69

Question 70

When does the Legendre equation have solutions

Answer 70