the euclidean algorithm and primes

Question 1

euclidean division:

Answer 1

let a and b be integers with b!=0, then there is a unique pair of integers m and r such that a=mb+r and 0<=r<|b|

Question 2

b|a:

Answer 2

let a and b be integers, if there is an integer c with a=bc, we say b divides a or a is a multiple of b, written b|a

Question 3

common divisor:

Answer 3

if d|a and d|b, d is a common divisor of a and b, D(a,b) is the set of all common divisors of a and b

Question 4

greatest common divisor:

Answer 4

if at least one of a and b is nonzero, D(a,b) is finite, so it has a greatest element, denoted gcd(a,b)

Question 5

coprime:

Answer 5

two integers a and b are coprime if gcd(a,b)=1, so no prime factors in common

Question 6

a=mb+r and common divisors:

Answer 6

if a=mb+r, D(a,b)=D(b,r), and if at least one of a and b is nonzero then gcd(a,b)=gcd(b,r)

Question 7

euclidean algorithm:

Answer 7

given two integers a0 and a1 with a1!=0, gcd(a0,a1) can be found by:
1 - apply euclidean division to write a0=m1a0+r1, where m1,r1 are integers and 0<=r1<|a1|. if r1=0, return gcd(a0,a1)=a1, otherwise proceed
k - set ak=r↓(k-1), apply euclidean division to write a↓(k-1)=mkak+rk, where mk,rk are integers and 0<=rk<ak. if rk=0, return gcd(a0,a1)=r↓(k-1), otherwise proceed to step k+1

Question 8

bezout’s lemma:

Answer 8

let a,b be integers with at least one nonzero, there exists integers s,t such that as+bt=gcd(a,b)

Question 9

linear diophantine equation:

Answer 9

the form is a1x1+…+anxn=c, where ai,c are integers and we are solving for x1,…,xn. when there’s only one variable, a solution only exists if a|c and the solution is unique

Question 10

2 variable linear diophantine equations:

Answer 10

a,b,c are integers with at least one of a,b nonzero, and d=gcd(a,b)
ax+by=c has a solution iff d|c
if c=de, then a particular solution of ax+by=c is x0=se, y0=te, where s,t are integers satisfying d=as+bt
if (x0,y0) is a particular solution, then there’s infinitely many solutions, each of which has the form (x0+k(b/d), y0-k(a/d)), where k is an integer
imagine all this when x and y are real to have (x0,y0) be a point on a line, so you get the rest of the integer solutions by looking at the points on the line where x and y are both integers (like grid marks on the graph) - notice you can rearrange the original equation to a straight line graph

Question 11

euclid’s lemma:

Answer 11

let p be a prime and a,b be integers, if p|ab then p|a or p|b (it can be both)

Question 12

fundamental theorem of arithmetic:

Answer 12

every integer greater than 1 has a prime factorisation and this factorisation is unique up to reordering the factors

Question 13

euclid’s theorem:

Answer 13

there are infinitely many primes