Number Theory Flashcards
Composite
An integer >= 2 that is not prime
Highest common factor
The largest integer which is a factor of both a and b is the hcf(a,b)
Coprime
Two integers a,b are congruent modulo n Id a-b is a multiple of n
Invertible
- An element a in Z/n is invertible modulo n if there exists b in Z/n s.t. ab=1modn.
- The set of invertible elements in Z/n is written(Z/n)^x.
- This is a group with operation of multiplication.
Euler-Totient Function
The number of invertible elements in Z/n, ie. The order of the group (Z/n)^x
The number of positive integers less than n, coprime to n
Primitive Root (modp)
An element a ∈ F^xp is a primitive root modulo p if a generates the multiplicative group F^xp ie. Every element of F^xp is a power of a
Prime Number
An integer p>=2 is a prime if the only factors of p are ±1 and ±p
Chinese Remainder Theorem
Let n,m be coprime.
Given a ∈ Z/n and b ∈Z/m
There is a unique x ∈ Z/mm s.t. X = a modn and X = b modm
CRT proof
Existence: since n and m are coprime, by Euclid’s algorithm there is a h,k s.t. 1=hn + LM
Let x=hnb + kma
We can check X=a(n) X=b(m)
a = hnb + kma (n)
=(1-hn)a = 1 x a = a(n)
Similarly b(m)
Fermat’s Little Theorem
A ∈Fp^x and this is a group with p-1 elements
Let n be the order of a in this group IR. The smallest natural number s.t. a^n = 1 modp
Proof:
By Lagrange’s theorem: n divides the order of a which is p-1, so n is a factor of p-1
Therefore p-1 =nm for some m∈Z
Then a^p-1 = a^nm =(a^n)^m = 1^m = 1 modp
Berzout’s Lemma
Given a, b ∈Z, and a, b not zero, Ε h,k ∈ Z s.t ha + kb = hcf (a, b)
- use Euclid’s algorithm to find h and k
- to find a^-1 : find ha + kn = 1 by euclids then h is a^-1 mod n
There are infinitely many prime numbers
Assume that there are only finitely many primes; p1,p2,…..,pn
Let N = p1•p2…•pn +1
Since N >= 2 there is at least one prime which divides N
So pi | N ie. N = 0 (pi)
But clearly N = 1 modpi
Therefore contradiction!
And N doesn’t have a prime factor and must be a prime
Unique factorisation of integers
For any positive integer n, there is a factorisation n=p1….pr
This factorisation is unique up to reordering the primes pi….pr
Euler’s Theorem
If a is invertible mod(n), ie. a ∈(Z/n)^x then a^@(n) =1 mod(n)
Proof:
Let a ∈(Z/n)^x and let d be the order of a in this group, ie. Smallest d > 0 st. a^d = 1 (n)
By Lagrange’s theorem, d|@(n) ie. @(n) = d x e
a^d = 1 (n) therefore a^@(n) = a^(de) = (a^d)^e = 1^e = 1 (n)
Eratostene’s Sieve
Test for n primes
Testing for primitive roots
Let p be a prime a ∈Fˣp
To test if α is a quadratic residue mod p:
1. Find the primes q | p-1
2. For each q, calculate a^(p-1)/q mod p
If none of these are 1 modp ⇒ a is a primitive root
Cyclic group
A group G is cyclic if ∃ an element g∈G s.t. G = {g^i : i∈ℤ}
Generator
The element g∈G is called the generator of G
Primitive Root
A primitive root modulo p is a generator of Fp ( an element of Fo order p-1)
Gauss’ Theorem
For every prime number p, ∃ a primitive root modulo p. There are φ(p-1) of them.
If P is prime, then Fp is a cyclic group.
Quadratic Reciprocity
Let p be an odd prime number and a∈Fˣp coprime to p
a is a quadratic residue of x² = a mod p has solutions
Legendre Symbol
(a/p)
=1 is a is a quadratic residue
=-1 if a is a quadratic non-residue
=0 if p|a
Quadratic reciprocity law
If p and q are distinct odd primes, then (p/q) = (-1)^((p-1)(q-1)/4)(q/p)
First Nebensatz
If p=1 mod4 then (-1/p) = 1 and if p =-1 mod p then (-1/p) =(-1)^(p-1)/2
Second Nebensatz
If p = ±1 mod 8 then (2/p)=1
If p= ±3 mod 8 then (2/p)=(-1)^((p^2 -1)/8)
Gauss Sum
Let p be an odd prime.
The Guass Sun G(p) is: sum from p=1 to 0-1 of (a/p) e^2πi/p
Valuation
Valuation of x at p
For a non-zero integer n and prime p:
Vp(n) = a
Where a is the largest power s.t. P^a is a factor of n
Vp(0) = ∞
Vp(n/m) = vp(n) - vp(m)
Hensel’s Lemma
Let p be a prime number and let f∈ℤp[x] be a polynomial
Suppose there is an a₀∈ℤp[x] St. f(a₀) = 0 modp^2c+1 where c = Vp(f’(a₀))
P-adic
Congruence modulo p^n where p is a prime number and n is large
Proposition
Let p be an odd prime and let a be an integer coprime to p
If x²≡a (p) has solutions mod p then it has solutions mod p^n for all n
Proposition
Le a be an odd number.
If the congruence x₂≡a (8) has solutions mod 8, then it has solutions mod(2^n) for all n>0
True iff. a≡1mod8
Teichmuller lift
The teichmuller lift of a to ,ℤ/pn is defined to be T(a) = a^(p^n-1) ∈ℤ/pn
If T(x) = a modp^n then T(x) ≡ a^p modp^n+1
To calculate T(x) mod p^n
First calculate T(x) modp^n-1 and then raise it to the power p
Every element of (ℤ/p^n)^x can be written uniquely:
T(x) exp(py)
Where x∈Fp and y ∈ℤ/p^n-1
Py = log(aT⁻¹(x))
a=T(x)exp(py)
ℤp
Ring of p-adic integers
The set of all p-adic integers
P-Adic integer
Let p be any prime;
p-adic integer means a p-adically convergent series ∑ai where Vp(ai) →∞
P-adic integer
A p-adic integer is a p-adically convergent series
- 2 p-Adic integers are equal if they are congruent mod p^n for every n
-the set of p-adic integers ℤp is a ring since sums and products of p-adically convergent series are also p-adically convergent series
Square-free
An integer d is caller square-free if the only factor of d which is a square is 1
Unit / invertible elements in a ring
A unit is an element in a ring with an inverse
Ie. U in a ring R, is a unit of there exists an element U⁻¹ in R St. UU⁻¹ =1
Irreducible
An element P in R is irreducible if P is not a unit and for all factorisations; P =AB and either A is a unit or B is a unit
Norm-Euclidean Quadratic Rings
A quadratic ring ℤ[α] is norm Euclidean if:
For every A, B ∈ℤ[α] with B ≠ 0 ∃ Q, R ∈ℤ[α st:
- A = QB + R
- |N(R)|
Irreducible element
An element P ∈ℤ[α] is called irreducible if:
- P is not a unit
- If P =AB with A, B ∈ℤ[α] then either A or B is a unit
- Says that the only factors of P are units and unit multiples of P
