Number Theory

Question 1

State bezouts lemma

Answer 1

Let a and b be integers (not both 0). Then there exists integers u and v such that gcd(a,b)=au+bv

Question 2

What does it mean for two integers to be coprime?

Answer 2

the gcd of the two numbers is 1

Question 3

define least common multiples

Answer 3

if a and b are integers then a common multiple of a and b is an integer c such that a|c and b|c. If a and b are both non-zero, the least common multiple of a and b is defined to be the smallest positive integer lcm(a,b) which is a common multiple of a and b.

Question 4

What does b|a mean?

Answer 4

b divides a - a=qb for some q

Question 5

define greatest common divisor

Answer 5

the largest divisor d of a and b such that d|a and d|b => gcd(a,b)=d

Question 6

Euclidean algoritm

Answer 6

basically if a=qb+r then gcd(a,b)=gcd(b,r)

Question 7

gcd(a,b)lcm(a,b)=?

Answer 7

|ab|

Question 8

when does the linear diophantine equations ax+by=c have solutions?

Answer 8

only has solutions when c is a multiple of d=gcd(a,b)

Question 9

How do you solve the linear diophantine equation ax+by=c?

Answer 9

(1) find x0, y0, gcd, using the euclidean algorithm a(x0)+b(y0)=d=gcd(a,b)
(2) the full set of solutions is x=x0+k.(b/g), y=y0+k(a/g) for all k∈ℤ

Question 10

define a prime number

Answer 10

An integer p>1 is called a prime number if it has no positive divisors other than 1 and p.

Question 11

fundamental theorem of arithmetic

Answer 11

every integer n>1 can be expressed uniquely (up to reordering) as a product of primes.

Question 12

state euclids theorem and describe how the proof would go

Answer 12

there are infinitely many primes.
Proof by contradiction:
- assume there are finitely many primes
- there is an integer N such that N≥p for all primes p
- consider the integer n=N!+1=1x2x..x(N-1)xN +1
- by the fundamental theorem of arithmetic there is a prime p with p|n
- since p≤N we also have p|N!
- but 1=n-N! so that implies p|1 which is impossible

Question 13

define congruence

Answer 13

let m be a non-zero integer, and let a,b∈ℤ. We say that a is congruent to b modulo m if m|(a-b).

Question 14

define a multiplicative group

Answer 14

the multiplicative group of integers modulo m which is defined by:
ℤx(m)={ [a]m∈ℤ(m): a,m are coprime}

Question 15

Hensels lemma

Answer 15

Let f(x)=a0+a1x+...+anx^n be a polynomial with integer coefficients, let p be a prime and let r be a positive integer. We let f'(x) be the derivative of f(x), so f'(x)=a1+2a2x+...+nanx^(n-1). suppose xr is an integer with 
f(xr)=0 (mod p^r)
and f'(xr)≠0 (mod p)
Then there exists x(r+1)∈ℤ satisfying
f(x(r+1))=0 (mod p^(r+1)) and
x(r+1)=xr (mod p^r)
moreover the x(r+1) satisfying these properties is unique modulo p^(r+1) and we can take x(r+1)=xr-f(xr)u
where u is an inverse of f'(xr) (modp).

Question 16

Define the eulers function 𝜙(m)

Answer 16

the number of integers a such that 1≤a≤m and gcd(a,m)=1

equivalently 𝜙(m)=|ℤx(m)|

Question 17

p is a prime number

𝜙(p)=?

Answer 17

p-1

Question 18

𝜙(p^i)

Answer 18

p^(i-1)(p-1)=p^i-p^(i-1)

Question 19

fermat-euler theorem

Answer 19

Let a∈ℤ and let m be a positive integer which is coprime to p. Then a^𝜙(m)=1 (mod m)

Question 20

Fermats little theorem

Answer 20

Let p be a prime and let a∈ℤ be an integer which is coprime to p. Then a^(p-1)=1 (mod p) ⇒ a^p=a (mod p)

Question 21

order of an element g

Answer 21

the smallest positive integer i such that g^i=e

Question 22

Quadratic residue modulo p

Answer 22

Let p be an odd prime and a an integer coprime to p. We say that a is a quadratic residue modulo p if the equation
x^2=a (mod p)
has a solution for x and we say that a is a quadratic non-residue modulo p otherwise.

Question 23

Define primitive root

Answer 23

m is a positive integer. An integer a, which is coprime to m is called a primitive root mod m if the order of an integer modulo m is euler(m)

Question 24

What is an algebraic number?

Answer 24

A complex number is called algebraic if it is a root of a non-zero polynomial with rational coefficients

Question 25

What is a transcendental number

Answer 25

One that is not algebraic - ie is not the root of a non-zero polynomial with rational coefficients

Question 26

How do you know if an integer is the sum of two squares?

Answer 26

A positive integer n is the sum of two squares iff the exponent of every prime number which is congruent to 3 (mod 4) in the prime factorisation of n is even.