Number Theory Flashcards
When does a divide b
When there exists an integer c such that b = ac. We write a | b
When is an integer p prime
if the only divisors are 1, -1, p, -p
Theorem: There are infinitely many primes
Define the highest common factor
Let a,b (integers), at least one is non zero. The highest common factor is the largest natural number dividing both a and b
State Bezout’s Lemma
Let m,n be integers, both non-zero. There exists integers a,b such that am + bn = hcf(a,b)
State and prove Euclids Lemma
State the fundamental theorem of arithmetic
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
Prove the fundamental theorem of arithmetic
Let R be a commutative ring. When is a subset I of R an ideal of R [3]
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
What is a principal ideal
The ideal generated by a, ie {ar : r in R}
Define an integral domain
When is R a principal ideal domain
If it’s an integral domain and every ideal of R is principal
Proposition: Z is a principal ideal domain
State Fermat’s Last Theorem
For any integer n > 2, there are no solutions to the equation xn + yn = zn with x,y,z positive integers
Define a unit and associates
What is U(Z)
{-1, 1}
Define irreducible and prime in this sense
Lemma: In any integral domain R, every prime element is irreducible
Define factorisations that are essentially the same
When is an integral domain R a unique factorisation domain (UFD)
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 do we show a group isn’t a UFD
Find two factorisations and show the factors are irreducibles and not associates
State and prove the cancellation lemma
Define highest common factor
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
Show in Z[root(-5)] the hcf of 6 and 2 + root(-5) doesnt exist
Lemma: In any principal ideal domain R, every irreducible element is prime
Define a Euclidean domain
Theorem: Every Euclidean domain R is a Principal Ideal domain
Define congruence modulo m
Proposition: The equation x2 + y2 + 3z2 has no integer solutions for x,y,z apart from the trivial solution x = y = z = 0
Define Z/mZ
The set {0,1,……,m-1}, equipped with addition and multiplication modulo m
What is (Z/mZ)X
The group of units of Z/mZ, which is the elements a such that hcf(a,m) = 1
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
How do we go about solving the linear congruence ax = b mod m
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
Define the Euler Totient formula
If p is prime, what is phi(p)
p - 1
State and prove Euler’s theorem
State Fermat’s little theorem
Define quadratic residue mod m
Define the legendre symbol
State the two squareroots lemma
State Wilson’s theorem
If p is prime, then (p-1)! = -1 mod p. If m > 5 is composite, then (m-1)! = 0 mod m
State Eulers criterion
When is -1 a quadratic residue or a quadratic non-residue mod p
quadratic residue if p = 1 mod 4, quadratic non-residue if p = 3 mod 4
State the Chinese Remainder theorem
How do we solve a problem using the chinese remainder theorem
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
When is a function f: N to C multiplicative
When f(mn) = f(m)f(n) if hcf(m,n) = 1
Define the order of a mod m
for any u in N, what is ordm(au) and what is the relationship between ordm(a) and phi(m)
Define a primitive root
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
phi(d)
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
State and prove the dth roots lemma
Give the equations for legendre symbol (2 / p) for an odd prime p
State the theorem of quadratic reciprocity
State Gauss’s Lemma
When can a natural number n be written as a sum of two integer squares
if and only if in its prime factorisation, any prime that is = 3 mod 4 has an even exponent
What are the only prime/ irreducible elements of Z[i]
State Lagrange’s four squares theorem
Every natural number n may be written as the sum of four integer squares
Define a lattice
We say a set L in Zn is a lattice in Zn if L is an additive subgroup
Define symmetric and convex
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
State Minkowskis Theorem, weak form
Define a pythagorean triple
We say (x,y,z) is a triple of natural numbers is a pythagorean triple if x2 + y2 = z2
When is a pythagorean triple primitive
if there is no natural number d > 1 that divides all of x,y,z
When is a triple (x,y,z) a pythagorean triple? (whats the parameterisation)
x = u2 - v2
y = 2uv
z = u2 + v2
for coprime u,v in N, not both odd
When does the Legendre equation have solutions
