Number Theory

Question 1

Composite

Answer 1

An integer >= 2 that is not prime

Question 2

Highest common factor

Answer 2

The largest integer which is a factor of both a and b is the hcf(a,b)

Question 3

Coprime

Answer 3

Two integers a,b are congruent modulo n Id a-b is a multiple of n

Question 4

Invertible

Answer 4

• 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.

Question 5

Euler-Totient Function

Answer 5

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

Question 6

Primitive Root (modp)

Answer 6

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

Question 7

Prime Number

Answer 7

An integer p>=2 is a prime if the only factors of p are ±1 and ±p

Question 8

Chinese Remainder Theorem

Answer 8

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

Question 9

CRT proof

Answer 9

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)

Question 10

Fermat’s Little Theorem

Answer 10

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

Question 11

Berzout’s Lemma

Answer 11

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

Question 12

There are infinitely many prime numbers

Answer 12

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

Question 13

Unique factorisation of integers

Answer 13

For any positive integer n, there is a factorisation n=p1….pr
This factorisation is unique up to reordering the primes pi….pr

Question 14

Euler’s Theorem

Answer 14

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)

Question 15

Eratostene’s Sieve

Answer 15

Test for n primes

Question 16

Testing for primitive roots

Answer 16

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

Question 17

Cyclic group

Answer 17

A group G is cyclic if ∃ an element g∈G s.t. G = {g^i : i∈ℤ}

Question 18

Generator

Answer 18

The element g∈G is called the generator of G

Question 19

Primitive Root

Answer 19

A primitive root modulo p is a generator of Fp ( an element of Fo order p-1)

Question 20

Gauss’ Theorem

Answer 20

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.

Question 21

Quadratic Reciprocity

Answer 21

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

Question 22

Legendre Symbol

Answer 22

(a/p)

=1 is a is a quadratic residue
=-1 if a is a quadratic non-residue

=0 if p|a

Question 23

Quadratic reciprocity law

Answer 23

If p and q are distinct odd primes, then (p/q) = (-1)^((p-1)(q-1)/4)(q/p)

Question 24

First Nebensatz

Answer 24

If p=1 mod4 then (-1/p) = 1 and if p =-1 mod p then (-1/p) =(-1)^(p-1)/2

Question 25

Second Nebensatz

Answer 25

If p = ±1 mod 8 then (2/p)=1 | If p= ±3 mod 8 then (2/p)=(-1)^((p^2 -1)/8)

Question 26

Gauss Sum

Answer 26

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

Question 27

Valuation Valuation of x at p

Answer 27

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)

Question 28

Hensel's Lemma

Answer 28

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₀))

Question 29

P-adic

Answer 29

Congruence modulo p^n where p is a prime number and n is large

Question 30

Proposition

Answer 30

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

Question 31

Proposition

Answer 31

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

Question 32

Teichmuller lift

Answer 32

The teichmuller lift of a to ,ℤ/pn is defined to be T(a) = a^(p^n-1) ∈ℤ/pn

Question 33

If T(x) = a modp^n then T(x) ≡ a^p modp^n+1

Answer 33

To calculate T(x) mod p^n | First calculate T(x) modp^n-1 and then raise it to the power p

Question 34

Every element of (ℤ/p^n)^x can be written uniquely:

Answer 34

T(x) exp(py) Where x∈Fp and y ∈ℤ/p^n-1 Py = log(aT⁻¹(x)) a=T(x)exp(py)

Question 35

ℤp

Answer 35

Ring of p-adic integers The set of all p-adic integers

Question 36

P-Adic integer

Answer 36

Let p be any prime; | p-adic integer means a p-adically convergent series ∑ai where Vp(ai) →∞

Question 37

P-adic integer

Answer 37

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

Question 38

Square-free

Answer 38

An integer d is caller square-free if the only factor of d which is a square is 1

Question 39

Unit / invertible elements in a ring

Answer 39

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

Question 40

Irreducible

Answer 40

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

Question 41

Norm-Euclidean Quadratic Rings

Answer 41

A quadratic ring ℤ[α] is norm Euclidean if: For every A, B ∈ℤ[α] with B ≠ 0 ∃ Q, R ∈ℤ[α st: 1. A = QB + R 2. |N(R)|

Question 42

Irreducible element

Answer 42

An element P ∈ℤ[α] is called irreducible if: 1. P is not a unit 2. If P =AB with A, B ∈ℤ[α] then either A or B is a unit 2. Says that the only factors of P are units and unit multiples of P